1) La descarga del recurso depende de la página de origen
2) Para poder descargar el recurso, es necesario ser usuario registrado en Universia

Opción 1: Descargar recurso

Detalles del recurso


The problem of random number generation from an uncorrelated random source (of unknown probability distribution) dates back to von Neumann's 1951 work. Elias (1972) generalized von Neumann's scheme and showed how to achieve optimal efficiency in unbiased random bits generation. Hence, a natural question is what if the sources are correlated? Both Elias and Samuelson proposed methods for generating unbiased random bits in the case of correlated sources (of unknown probability distribution), specifically, they considered finite Markov chains. However, their proposed methods are not efficient or have implementation difficulties. Blum (1986) devised an algorithm for efficiently generating random bits from degree-2 finite Markov chains in expected linear time, however, his beautiful method is still far from optimality on information-efficiency. In this paper, we generalize Blum's algorithm to arbitrary degree finite Markov chains and combine it with Elias's method for efficient generation of unbiased bits. As a result, we provide the first known algorithm that generates unbiased random bits from an arbitrary finite Markov chain, operates in expected linear time and achieves the information-theoretic upper bound on efficiency.

Pertenece a

Caltech Authors  


Zhou, Hongchao -  Bruck, Jehoshua - 

Id.: 55239736

Versión: 1.0

Estado: Final

Tipo:  application/pdf - 

Tipo de recurso: Article  -  PeerReviewed  - 

Tipo de Interactividad: Expositivo

Nivel de Interactividad: muy bajo

Audiencia: Estudiante  -  Profesor  -  Autor  - 

Estructura: Atomic

Coste: no

Copyright: sí

Formatos:  application/pdf - 

Requerimientos técnicos:  Browser: Any - 

Relación: [References] http://resolver.caltech.edu/CaltechAUTHORS:20120503-095551724
[References] http://authors.library.caltech.edu/31292/

Fecha de contribución: 24-ago-2016


* Zhou, Hongchao and Bruck, Jehoshua (2012) Efficient Generation of Random Bits From Finite State Markov Chains. IEEE Transactions on Information Theory, 58 (4). pp. 2490-2506. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20120503-095551724

Otros recursos del mismo autor(es)

  1. Reliability and Hardware Implementation of Rank Modulation Flash Memory We review a novel data representation scheme for NAND flash memory named rank modulation (RM), and d...
  2. Systematic Error-Correcting Codes for Permutations and Multi-Permutations Multi-permutations and in particular permutations appear in various applications in an information t...
  3. The capacity of some Pólya string models We study random string-duplication systems, called Pólya string models, motivated by certain random ...
  4. On the duplication distance of binary strings We study the tandem duplication distance between binary sequences and their roots. This distance is ...
  5. Secure RAID Schemes for Distributed Storage We propose secure RAID, i.e., low-complexity schemes to store information in a distributed manner th...

Otros recursos de la misma colección

  1. Exposing the Three-Dimensional Biogeography and Metabolic States of Pathogens in Cystic Fibrosis Sputum via Hydrogel Embedding, Clearing, and rRNA Labeling Physiological resistance to antibiotics confounds the treatment of many chronic bacterial infections...
  2. Measurement of tt production with additional jet activity, including b quark jets, in the dilepton decay channel using pp collisions at √s = 8 TeV Jet multiplicity distributions in top quark pair (tt) events are measured in pp collisions at a cent...
  3. Robust Ambulance Allocation Using Risk-based Metrics This paper focuses on robust location strategies for a fleet of ambulances in cities in order to max...
  4. VIP: Joint Traffic Engineering and Caching in Named Data Networks Emerging information-centric networking architectures seek to optimally utilize both bandwidth and s...
  5. A study of polar codes for MLC NAND flash memories The increasing density of NAND flash memories makes data more prone to errors due to severe process ...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.