How to turn loaded dice into fair coins
- 1 May 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 46 (3), 911-921
- https://doi.org/10.1109/18.841170
Abstract
We present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Sequences of random numbers are of pervasive importance in cryptography and vital to many other computing applications. Many sources of randomness, such as radioactive or quantum-mechanical sources, possess the property of stationarity. In other words, they produce independent outputs over fixed probability distributions. The output of such sources may be viewed as the result of rolling a biased or loaded die. While a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. For this reason, von Neumann (1951) presented a now well-known and extensively investigated technique for using a biased coin to simulate a fair coin. We describe a new generalization of von Neumann's algorithm distinguished by its high level of practicality and amenability to analysis. In contrast to previous efforts, we are able to prove our algorithm optimally efficient, in the sense that it simulates the maximum possible number of fair coin flips for a given number of die rolls. In fact, we are able to prove that in an asymptotic sense our algorithm extracts the full entropy of its input. Moreover, we demonstrate experimentally that our algorithm achieves a high level of computational and output efficiency in a practical setting.Keywords
This publication has 23 references indexed in Scilit:
- Simulating Fair Dice with Biased CoinsInformation and Computation, 1996
- The Biased Coin ProblemSIAM Journal on Discrete Mathematics, 1996
- Efficient simulations by a biased coinInformation Processing Letters, 1995
- On Dice and Coins: Models of Computation for Random GenerationInformation and Computation, 1993
- Making a fair roulette from a possibly biased coinInformation Processing Letters, 1990
- Concept for a High Performance Random Number Generator Based on Physical Random PhenomenaFrequenz, 1985
- Tree Algorithms for Unbiased Coin Tossing with a Biased CoinThe Annals of Probability, 1984
- On the generation of cryptographically strong pseudorandom sequencesACM Transactions on Computer Systems, 1983
- The Efficient Construction of an Unbiased Random SequenceThe Annals of Mathematical Statistics, 1972
- Unbiased Coin Tossing with a Biased CoinThe Annals of Mathematical Statistics, 1970