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

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.

Pertenece a

Caltech Authors  

Autor(es)

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

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. 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 ...
  2. A consistent history link connectivity protocol Given the prevalence of powerful personal workstations connected over local area networks, it is onl...
  3. Distributed broadcasting and mapping protocols in directed anonymous networks In this work we study the fundamental problems of broad- casting and mapping (label assignment and t...
  4. Is there a new way to correct errors The classic approach for error correction is to add controlled external redundancy to data. This app...
  5. Duplication Distance to the Root for Binary Sequences We study the tandem duplication distance between binary sequences and their roots. In other words, ...

Otros recursos de la mismacolección

  1. Rapid Assessment of Earthquake Source Characteristics Recent studies emphasize the rapid assessment of earthquake source properties, such as moment magnit...
  2. Molecular Control of Flower Development The last decade has been an exciting period in plant molecular biology in general and in molecular s...
  3. Modeling the organization of the WUSCHEL expression domain in the shoot apical meristem Motivation: The above-ground tissues of higher plants are generated from a small region of cells sit...
  4. Contrasting cloud composition between coupled and decoupled marine boundary layer clouds Marine stratocumulus clouds often become decoupled from the vertical layer immediately above the oce...
  5. Colour formation on the wings of the butterfly Hypolimnas salmacis by scale stacking The butterfly genus Hypolimnas features iridescent blue colouration in some areas of its dorsal wing...

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.