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: 21-ene-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. Asymmetric Error Correction and Flash-Memory Rewriting using Polar Codes We propose efficient coding schemes for two communication settings: 1) asymmetric channels and 2) ch...
  2. Constructions and Decoding of Cyclic Codes Over b-Symbol Read Channels Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols...
  3. Liver Regeneration and Energetic Changes In Rats Following Hepatic Radiation Therapy and Hepatocyte Transplantation by 31P MRSI
  4. Codes Correcting Erasures and Deletions for Rank Modulation Error-correcting codes for permutations have received considerable attention in the past few years, ...
  5. Multiple Threshold Neural Logic We introduce a new Boolean computing element related to the Linear Threshold element, which is the B...

Otros recursos de la misma colección

  1. The effect of time on optical coating mechanical loss and implications for LIGO-India We report on the persistence of mechanical loss with time of ion beam sputtered dielectric coatings ...
  2. Efficient microwave to optical photon conversion: an electro-optical realization Linking classical microwave electrical circuits to the optical telecommunication band is at the core...
  3. Uniqueness, universality, and homogeneity of the noncommutative Gurarij space We realize the noncommutative Gurarij space NG defined by Oikhberg as the Fraïssé limit of the class...
  4. Kinetic-energy systems, density scaling, and homogeneity relations in density-functional theory We examine the behavior of the Kohn-Sham kinetic energy T_s[ρ] and the interacting kinetic energy T[...
  5. Optimized Lieb-Oxford bound for the exchange-correlation energy Using the ideas of Lieb and Oxford [Int. J. Quantum Chem. 19, 427 (19810], we show that the exchange...

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.