Streaming Algorithms for Optimal Generation of Random Bits
- Creators
- Zhou, Hongchao
- Bruck, Jehoshua
Abstract
Generating random bits from a source of biased coins (the biased is unknown) is a classical question that was originally studied by von Neumann. There are a number of known algorithms that have asymptotically optimal information efficiency, namely, the expected number of generated random bits per input bit is asymptotically close to the entropy of the source. However, only the original von Neumann algorithm has a 'streaming property' - it operates on a single input bit at a time and it generates random bits when possible, alas, it does not have an optimal information efficiency. The main contribution of this paper is an algorithm that generates random bit streams from biased coins, uses bounded space and runs in expected linear time. As the size of the allotted space increases, the algorithm approaches the information-theoretic upper bound on efficiency. In addition, we discuss how to extend this algorithm to generate random bit streams from m-sided dice or correlated sources such as Markov chains.
Additional Information
This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.Attached Files
Submitted - 1209.0730.pdf
Files
Name | Size | Download all |
---|---|---|
md5:203f45996ce9a0b283ebbe41aba61745
|
295.5 kB | Preview Download |
Additional details
- Eprint ID
- 63796
- Resolver ID
- CaltechAUTHORS:20160120-102504919
- CCF-0832824
- NSF
- Created
-
2016-01-20Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field