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. Stash in a Flash Encryption is a useful tool to protect data confidentiality. Yet it is still challenging to hide the...
  2. Stopping Set Elimination for LDPC Codes This work studies the Stopping-Set Elimination Problem, namely, given a stopping set, how to remove ...
  3. Probabilistic switching circuits in DNA A natural feature of molecular systems is their inherent stochastic behavior. A fundamental challeng...
  4. Attaining the 2nd Chargaff Rule by Tandem Duplications Erwin Chargaff in 1950 made an experimental observation that the count of A is equal to the count of...
  5. The Robustness of Stochastic Switching Networks Many natural systems, including chemical and biological systems, can be modeled using stochastic swi...

Otros recursos de la mismacolección

  1. The 1.5 Ms observing campaign on IRAS 13224−3809 – I. X-ray spectral analysis We present a detailed spectral analysis of the recent 1.5 Ms XMM–Newton observing campaign on the na...
  2. Measurements of differential cross sections of top quark pair production as a function of kinematic event variables in proton-proton collisions at √s = 13 TeV Measurements of differential tt production cross sections are presented in the single-lepton decay c...
  3. Broadband sensitization of lanthanide emission with indium phosphide quantum dots for visible to NIR downshifting Semiconductor quantum dot sensitized lanthanide ions hold great promise in producing a broadly absor...
  4. On fundamental diffraction limitation of finesse of a Fabry–Perot cavity We perform a theoretical study of finesse limitations of a Fabry–Perot (FP) cavity occurring due to ...
  5. Impact of node geometry on the effective stiffness of non-slender three-dimensional truss lattice architectures Three-dimensional (3D), lattice-based micro- and nano-architected materials can possess desirable me...

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.