Sunday, February 14, 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. The Synthesis and Analysis of Stochastic Switching Circuits Stochastic switching circuits are relay circuits that consist of stochastic switches called pswitche...
  2. Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms The ability to store data in the DNA of a living organism has applications in a variety of areas inc...
  3. Secure RAID Schemes for Distributed Storage We propose secure RAID, i.e., low-complexity schemes to store information in a distributed manner th...
  4. Explicit MDS Codes for Optimal Repair Bandwidth MDS codes are erasure-correcting codes that can correct the maximum number of erasures for a given n...
  5. Efficiently Extracting Randomness from Imperfect Stochastic Processes We study the problem of extracting a prescribed number of random bits by reading the smallest possib...

Otros recursos de la misma colección

  1. Observation of Gravitational Waves from a Binary Black Hole Merger On September 14, 2015 at 09:50:45 UTC the two detectors of the Laser Interferometer Gravitational-Wa...
  2. Water content of a granite magma deduced from the sequence of crystallization determined experimentally with water-undersaturated conditions The sequence of crystallization in a biotite-granite from the Bohus batholith of Norway and Sweden, ...
  3. Data Report for the 1993 Los Angeles Region Seismic Experiment (LARSE93), Southern California: a passive study from Seal Beach northeastward through the Mojave Desert This report contains a description of the first part of the Los Angeles Region Seismic Experiment (L...
  4. The 1997 Los Angeles Basin Passive Seismic Experiment – a dense, urban seismic array to investigate basin lithospheric structures In 1997, 18 seismic stations were installed in the Los Angeles basin to record teleseismic, regional...
  5. ShakeNet: A portable wireless sensor network for instrumenting large civil structures We report our findings from a U.S. Geological Survey (USGS) National Earthquake Hazards Reduction Pr...

Valoración de los usuarios

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

Busque un recurso