Streaming Algorithms for Optimal Generation of Random Bits

arXiv1209.0730MaRDI QIDQ6235440FDOQ6235440

Authors: Hongchao Zhou, Jehoshua Bruck 

Publication date: 4 September 2012

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.

This page was built for publication: Streaming Algorithms for Optimal Generation of Random Bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235440)