Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2012 | Submitted
Journal Article Open

Efficient Generation of Random Bits From Finite State Markov Chains

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 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.

Additional Information

© 2012 IEEE. Manuscript received December 23, 2010; revised June 02, 2011; accepted October 04, 2011. This work was supported in part by the National Science Foundation's Expeditions in Computing Program under Grant CCF-0832824. This paper was presented in part at the 2010 IEEE International Symposium on Information Theory.

Attached Files

Submitted - 1012.5339.pdf

Files

1012.5339.pdf
Files (320.9 kB)
Name Size Download all
md5:e55183836ea4eb6ad71e568aef6f4c31
320.9 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023