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. Floating Codes for Joint Information Storage in Write Asymmetric Memories Memories whose storage cells transit irreversibly between states have been common since the start of...
  2. Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms The ability to store data in the DNA of a living organism has applications in a variety of areas inc...
  3. Data movement in flash memories NAND flash memories are the most widely used non-volatile memories, and data movement is common in f...
  4. Universal rewriting in constrained memories A constrained memory is a storage device whose elements change their states under some constraints. ...
  5. Switch Codes: Codes for Fully Parallel Reconstruction Network switches and routers scale in rate by distributing the packet read/write operations across m...

Otros recursos de la mismacolección

  1. Identifying the Presence of a Disulfide Linkage in Peptides by the Selective Elimination of Hydrogen Disulfide from Collisionally Activated Alkali and Alkaline Earth Metal Complexes We report a new method for identifying disulfide linkages in peptides using mass spectrometry. This ...
  2. Three-dimensional Boltzmann-Hydro Code for Core-collapse in Massive Stars. II. The Implementation of Moving-mesh for Neutron Star Kicks We present a newly developed moving-mesh technique for the multi-dimensional Boltzmann-Hydro code fo...
  3. The Broadband Spectral Variability of Holmberg IX X-1 We present results from four new broadband X-ray observations of the extreme ultraluminous X-ray sou...
  4. New probe of magnetic fields in the pre-reionization epoch. II. Detectability In the first paper of this series, we proposed a novel method to probe large–scale intergalactic mag...
  5. New probe of magnetic fields in the prereionization epoch. I. Formalism We propose a method of measuring extremely weak magnetic fields in the intergalactic medium prior to...

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.