Tuesday, September 2, 2014



Soy un nuevo usuario

Olvidé mi contraseña

Entrada usuarios

Lógica Matemáticas Astronomía y Astrofísica Física Química Ciencias de la Vida
Ciencias de la Tierra y Espacio Ciencias Agrarias Ciencias Médicas Ciencias Tecnológicas Antropología Demografía
Ciencias Económicas Geografía Historia Ciencias Jurídicas y Derecho Lingüística Pedagogía
Ciencia Política Psicología Artes y Letras Sociología Ética Filosofía

Efficient Generation of Random Bits From Finite State Markov Chains

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

Detalles del recurso

Pertenece a: Caltech Authors  

Descripción: 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.

Autor(es): Zhou, Hongchao -  Bruck, Jehoshua - 

Id.: 55239736

Versión: 1.0

Estado: Final

Tipo de recurso: Article  -  PeerReviewed  - 

Tipo de Interactividad: Expositivo

Nivel de Interactividad: muy bajo

Audiencia: Estudiante  -  Profesor  -  Autor  - 

Estructura: Atomic

Coste: no

Copyright: sí

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: 04-may-2012


* 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. Synthesis of Stochastic Flow Networks A stochastic flow network is a directed graph with incoming edges (inputs) and outgoing edges (outpu...
  2. Guest Editorial: Communication Methodologies for the Next-Generation Storage Systems This issue consists of 22 high-caliber papers with contributions from both academia and industry. Th...
  3. Access Versus Bandwidth in Codes for Storage Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (n...
  4. The Capacity of String-Replication Systems It is known that the majority of the human genome consists of repeated sequences. Furthermore, it is...
  5. Rate-Distortion for Ranking with Incomplete Information We study the rate-distortion relationship in the set of permutations endowed with the Kendall t-metr...

Otros recursos de la misma colección

  1. Quasi Two-Dimensional Flows Through a Cascade A thin airfoil theory is developed for airfoils spanning a slowly diverging or converging channel, t...
  2. Production of Accelerated Cavitation Damage by an Acoustic Field in a Cylindrical Cavity A convenient and economical method for the production of cavitation damage is described. Cavitation ...
  3. Pressure Distributions on the Vanes of a Radial Flow Impeller Theoretical approaches give very little guide to the design of radial arrays of vanes for the additi...
  4. From neuronal populations to behavior: a computational journey Cognitive behaviors originate in the responses of neuronal populations. We have a reasonable underst...
  5. Herschel SPIRE FTS relative spectral response calibration Herschel/SPIRE Fourier transform spectrometer (FTS) observations contain emission from both the Hers...

Valoración de los usuarios

No hay ninguna valoración para este recurso.Sea el primero en valorar este recurso.

Busque un recurso