CaltechAUTHORS
  A Caltech Library Service

Streaming Algorithms for Optimal Generation of Random Bits

Zhou, Hongchao and Bruck, Jehoshua (2012) Streaming Algorithms for Optimal Generation of Random Bits. , Pasadena, CA. (Submitted) http://resolver.caltech.edu/CaltechAUTHORS:20160120-102504919

[img] PDF - Submitted Version
See Usage Policy.

288Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160120-102504919

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1209.0730arXivDiscussion Paper
Additional Information:This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.
Funders:
Funding AgencyGrant Number
NSFCCF-0832824
Subject Keywords:Random Number Generation, Biased Coins, Markov Chains, Streams
Record Number:CaltechAUTHORS:20160120-102504919
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160120-102504919
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:63796
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Jan 2016 20:25
Last Modified:20 Jan 2016 20:25

Repository Staff Only: item control page