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. Communication Efficient Secret Sharing A secret sharing scheme is a method to store information securely and reliably. Particularly, in a t...
  2. Error Characterization and Mitigation for 16nm MLC NAND Flash Memory under Total Ionizing Dose Effect This paper studies the system-level reliability of 16nm MLC NAND flash memories under total ionizing...
  3. Data archiving in 1x-nm NAND flash memories: Enabling long-term storage using rank modulation and scrubbing The challenge of using inexpensive and high-density NAND flash for archival storage was posed recent...
  4. Explicit Minimum Storage Regenerating Codes In distributed storage, a file is stored in a set of nodes and protected by erasure-correcting codes...
  5. Error correction through language processing There are two fundamental approaches for error correction. One approach is to add external redundanc...

Otros recursos de la misma colección

  1. Starvation and recovery in the deep-sea methanotroph Methyloprofundus sedimenti In the deep ocean, the conversion of methane into derived carbon and energy drives the establishment...
  2. Homogenization and Path Independence of the J-Integral in Heterogeneous Materials The J-integral that determines the driving force on a crack tip is a central concept of fracture mec...
  3. Unstable neurons underlie a stable learned behavior Motor skills can be maintained for decades, but the biological basis of this memory persistence rema...
  4. SOXE neofunctionalization and elaboration of the neural crest during chordate evolution During chordate evolution, two genome-wide duplications facilitated acquisition of vertebrate traits...
  5. Microresonator soliton dual-comb spectroscopy Rapid characterization of optical and vibrational spectra with high resolution can identify species ...

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.