Zhou, Hongchao and Bruck, Jehoshua (2010) Generalizing the Blum-Elias Method for Generating Random Bits from Markov Chains. In: 2010 IEEE International Symposium on Information Theory. IEEE International Symposium on Information Theory . IEEE , New York, NY, pp. 1248-1252. ISBN 978-1-4244-7891-0. https://resolver.caltech.edu/CaltechAUTHORS:20110331-095348080
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110331-095348080
Abstract
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 Samueleson 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 (Samueleson) or have implementation difficulties (Elias). 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. 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.
Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
Additional Information: | © 2010 IEEE. Issue Date: 13-18 June 2010, Date of Current Version: 23 July 2010. This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824. | |||||||||
Funders: |
| |||||||||
Other Numbering System: |
| |||||||||
Series Name: | IEEE International Symposium on Information Theory | |||||||||
Record Number: | CaltechAUTHORS:20110331-095348080 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20110331-095348080 | |||||||||
Official Citation: | Hongchao Zhou; Bruck, J.; , "Generalizing the Blum-Elias method for generating random bits from Markov chains," Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on , vol., no., pp.1248-1252, 13-18 June 2010 doi: 10.1109/ISIT.2010.5513679 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5513679&isnumber=5513230 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 23188 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Benjamin Perez | |||||||||
Deposited On: | 31 Mar 2011 18:30 | |||||||||
Last Modified: | 22 Nov 2019 09:58 |
Repository Staff Only: item control page