Sunday, March 1, 2015

 

 



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

Contacto:

Localización:
* 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. Systematic Error-Correcting Codes for Rank Modulation The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile me...
  2. Logic operations in memory using a memristive Akers array In-memory computation is one of the most promising features of memristive memory arrays. In this pap...
  3. Entanglement-based quantum communication secured by nonlocal dispersion cancellation Quantum key distribution (QKD) enables participants to exchange secret information over long distanc...
  4. Approximate Sorting of Data Streams with Limited Storage We consider the problem of approximate sorting of a data stream (in one pass) with limited internal ...
  5. A simple class of efficient compression schemes supporting local access and editing In this paper, we study the problem of compressing a collection of sequences of variable length that...

Otros recursos de la misma colección

  1. MORC1 represses transposable elements in the mouse male germline The Microrchidia (Morc) family of GHKL ATPases are present in a wide variety of prokaryotic and euka...
  2. COMBINE archive and OMEX format: one file to share all information to reproduce a modeling project Background: With the ever increasing use of computational models in the biosciences, the need to sha...
  3. Microwave Measurements of Carbon Monoxide on Titan The ratio of the flux density of Titan was measured in two 200-megahertz bands, one centered on the ...
  4. Nucleotide sequence of yellow fever virus: implications for flavivirus gene expression and evolution The sequence of the entire RNA genome of the type flavivirus, yellow fever virus, has been obtained....
  5. On the Intermediate-redshift Central Stellar Mass-Halo Mass Relation, and Implications for the Evolution of the Most Massive Galaxies Since z ~ 1 The stellar mass-halo mass relation is a key constraint in all semi-analytic, numerical, and semi-em...

Valoración de los usuarios

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

Busque un recurso