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. Patterned cells for phase change memories Phase-change memory (PCM) is an emerging nonvolatile memory technology that promises very high perfo...
  2. Content-assisted file decoding for nonvolatile memories Nonvolatile memories (NVMs) such as flash memories play a significant role in meeting the data stora...
  3. Sequence reconstruction for Grassmann graphs and permutations The sequence-reconstruction problem was first proposed by Levenshtein in 2001. This problem studies ...
  4. Noise and Uncertainty in String-Duplication Systems Duplication mutations play a critical role in the generation of biological sequences. Simultaneously...
  5. Optimal Rebuilding of Multiple Erasures in MDS Codes Maximum distance separable (MDS) array codes are widely used in storage systems due to their computa...

Otros recursos de la mismacolección

  1. A Synthetic DNA Walker for Molecular Transport Inspired by kinesin movement along a microtubule, we demonstrate a processive bipedal DNA walker. Po...
  2. NUPACK: Analysis and design of nucleic acid systems The Nucleic Acid Package (NUPACK) is a growing software suite for the analysis and design of nucleic...
  3. Programming biomolecular self-assembly pathways In nature, self-assembling and disassembling complexes of proteins and nucleic acids bound to a vari...
  4. All-sky search for short gravitational-wave bursts in the first Advanced LIGO run We present the results from an all-sky search for short-duration gravitational waves in the data of ...
  5. Assessing the Effect of Stellar Companions from High-resolution Imaging of Kepler Objects of Interest We report on 176 close (<2'') stellar companions detected with high-resolution imaging near 170 host...

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.