Tuesday, May 31, 2016

 

 



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


  Descargar recurso

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:  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: 21-ene-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. Constructions and Decoding of Cyclic Codes Over b-Symbol Read Channels Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols...
  2. Liver Regeneration and Energetic Changes In Rats Following Hepatic Radiation Therapy and Hepatocyte Transplantation by 31P MRSI
  3. Codes Correcting Erasures and Deletions for Rank Modulation Error-correcting codes for permutations have received considerable attention in the past few years, ...
  4. Multiple Threshold Neural Logic We introduce a new Boolean computing element related to the Linear Threshold element, which is the B...
  5. On Neural Networks with Minimal Weights Linear threshold elements are the basic building blocks of artificial neural networks. A linear thre...

Otros recursos de la misma colección

  1. When Heavy-Tailed and Light-Tailed Flows Compete: The Response Time Tail Under Generalized Max-Weight Scheduling This paper focuses on the design and analysis of scheduling policies for multi-class queues, such as...
  2. Visible and ultraviolet light scattering by tobacco mosaic virus nucleic acid 1. The apparent particle weight of TMV RNA prepared by the heat method is sensitive to the condition...
  3. A high-resolution speleothem record of western equatorial Pacific rainfall: Implications for Holocene ENSO evolution The El Niño-Southern Oscillation (ENSO) is the primary driver of interannual climate variability in ...
  4. Relativistic reflection: Review and recent developments in modeling Measuring relativistic reflection is an important tool to study the innermost regions of the an accr...
  5. Studies upon DNA synthesis during multiplicity reactivation of T2r^+ bacteriophage Studies of the synthesis of bacteriophage T2r^+ deoxyribonucleic acid (DNA) in bacterial cells multi...

Valoración de los usuarios

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

Busque un recurso