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. Cyclic Low-Density MDS Array Codes We construct two infinite families of low density MDS array codes which are also cyclic. One of thes...
  2. Shortening Array Codes and the Perfect 1-Factorization Conjecture The existence of a perfect 1-factorization of the complete graph K n, for arbitrary n, is a 40-year ...
  3. Anti-Jamming Schedules for Wireless Data Broadcast Systems Modern society is heavily dependent on wireless networks for providing voice and data communications...
  4. On the Capacity of Precision-Resolution Constrained Systems Arguably, the most famous constrained system is the (d, k)-RLL (run-length limited), in which a stre...
  5. Codes for Multi-Level Flash Memories: Correcting Asymmetric Limited-Magnitude Errors Several physical effects that limit the reliability and performance of Multilevel Flash memories ind...

Otros recursos de la mismacolección

  1. Mechanism for Unimolecular Decomposition of HMX (1,3,5,7-Tetranitro-1,3,5,7-tetrazocine), an ab Initio Study To improve the mechanistic understanding of the possible decomposition in the gas phase of the energ...
  2. An Electron Energy-Loss Spectrometry Study of Charge Compensation in LiNi_(0.8)Co_(0.2)O_2 Changes in the electronic structure of Li_(1-x)Ni_(0.8)Co_(0.2)O_2 during delithiation (charge) are ...
  3. Correlation Analysis of Chemical Bonds (CACB) II: Quantum Mechanical Operators for Classical Chemical Concepts We apply correlation analysis of chemical bonds (CACB) to simple organic reaction paths. CACB, an op...
  4. The Astrophysics of Star Formation Across Cosmic Time at ≳10 GHz with the Square Kilometre Array In this chapter, we highlight a number of science investigations that are enabled by the inclusion o...
  5. Olefin Hydroarylation Catalyzed by (Pyridyl-Indolate)Pt(II) Complexes: Catalytic Efficiencies and Mechanistic Aspects A series of Pt(II) complexes of the type (N–N)PtPh(SR2) (N-N = 2,2′-pyridyl-indolate) wer...

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.