Optimal random number generation from a biased coin
Pages 1079 - 1088
Abstract
We study the optimal generation of random numbers using a biased coin in two cases: first, when the bias is unknown, and second, when the bias is known. In the first case, we characterize the functions that use a discrete random source of unknown distribution to simulate a target discrete random variable with a given rational distribution. We identify the functions that minimize the ratio of source inputs to target outputs. We show that these optimal functions are efficiently computable. In the second case, we prove that it is impossible to construct an optimal tree algorithm recursively, using a model based on the algebraic decision tree. Our model of computation is sufficiently general to encompass virtually all previously known algorithms for this problem.
References
[1]
J. Abrahams. Generation of discrete distributions from biased coins. IEEE Transactions on Information Theory, 42(5):1541--1546, 1996.
[2]
L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer Verlag, 1998.
[3]
M. Blum. Independent unbiased coin flips from a correlated biased source: A finite state Markov chain. Combinatorica, 6(2):97--108, 1986.
[4]
B. A. Cipra. Tossed coins and troubled marriages: Mathematical highlights from AAAS 2004. SIAM News, 37(4), May 2004.
[5]
T. M. Cover. Enumerative source encoding. IEEE Transactions on Information Theory, 19(1):73--77, January 1973.
[6]
P. Diaconis. The search for randomness. American Association for the Advancement of Science annual meeting. Feb. 14., 2004. Seattle.
[7]
E. W. Dijkstra. Making a fair roulette from a possibly biased coin. Information Processing Letters, 36:193, 1990.
[8]
P. Elias. The efficient construction of an unbiased random sequence. The Annals of Mathematical Statistics, 43(3):865--870, 1972.
[9]
T. S. Han and M. Hoshi. Interval algorithm for random number generation. IEEE Transactions on Information Theory, 43(2):599--611, 1997.
[10]
W. Hoeffding and G. Simons. Unbiased coin tossing with a biased coin. The Annals of Mathematical Statistics, 41:341--352, 1970.
[11]
E. Klarreich. Toss out the toss-up: Bias in heads-or-tails. Science News, 165:131--132, 2004. Available at http://www.sciencenews.org/articles/20040228/fob2.asp.
[12]
D. Knuth. The Art of Computer Programming, volume 4A. Addison-Wesley, 2004. Pre-fascicle 3a, Generating all combinations, available at http://www-cs-faculty.stanford.edu/~knuth/taocp.html.
[13]
D. E. Knuth and A. C.-C. Yao. The complexity of nonuniform random number generation. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results. Proceedings of a Symposium, pages 357--428, New York NY, 1976. Carnegie-Mellon University, Computer Science Department, Academic Press.
[14]
S. Pae. Entropy bound for random number generation. manuscript, 2003.
[15]
S. Pae. The optimality of random number generation from biased coin. 2004. submitted.
[16]
Y. Peres. Iterating von Neumann's procedure for extracting random bits. Annals of Statistics, 20(1):590--597, 1992.
[17]
J. P. M. Schalkwijk. An algorithm for source coding. IEEE Transactions on Information Theory, 18(3):395--399, May 1972.
[18]
Q. F. Stout and B. Warren. Tree algorithms for unbiased coin tossing with a biased coin. Annals of Probability, 12(1):212--222, 1984.
[19]
J. von Neumann. Various techniques for use in connection with random digits. Notes by G. E. Forsythe. In Monte Carlo Method, Applied Mathematics Series, volume 12, pages 36--38. U.S. National Bureau of Standrads, Washington D.C., 1951. Reprinted in von Neumann's Collected Works5 (Pergammon Press, 1963), 768--770.
Recommendations
Bit-Wise Behavior of Random Number Generators
In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Von Neumann's Biased Coin Revisited
LICS '12: Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer ScienceSuppose you want to generate a random sequence of zeros and ones and all you have at your disposal is a coin which you suspect to be biased (but do not know the bias). Can "perfect" randomness be produced with this coin? The answer is positive, thanks ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2005
1205 pages
ISBN:0898715857
Sponsors
- SIAM Activity Group on Discrete Mathematics
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 23 January 2005
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 791Total Downloads
- Downloads (Last 12 months)19
- Downloads (Last 6 weeks)1
Reflects downloads up to 09 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in