Abstract: Suppose you have a coin and want to flip it to generate a random bit. However, it may not be a fair coin, i.e., it may be that "heads" and "tails" are not equally likely. How can you use this potentially biased coin to generate an unbiased result? In particular, how can you do this when you don't know what, if any, the coin's bias is?

Von Neumann gave a simple solution: flip the coin twice. If it comes up heads followed by tails, then call the outcome HEAD. If it comes up tails followed by heads, then call the outcome TAIL. Otherwise (i.e., two heads or two tails occured) repeat the process. Throughout we assume that the flips are independent, and in this case it is easy to show that von Neumann's procedure simulates an unbiased coin, in that one is exactly as likely to get a HEAD outcome as a TAIL outcome, no matter what the coin's bias is. Further, no matter what the bias is (as long as it is not 0 nor 1), in finite expected time an unbiased outcome will be achieved.

Can one be more efficient, i.e., not flip the coin as often on average? For example, suppose the coin came up heads heads and then tails tails. The von Neumann procedure would be to try yet again. However, this outcome is exactly as likely as tails tails heads heads, and hence we may as well call the first one HEAD and the second TAIL. I.e., one can do a bit better, and in fact would need more than 4 flips only if they were all heads or all tails. Further, it is clear we can extend this, so that 4 heads followed by 4 tails is called HEAD and 4 tails followed by 4 heads is called TAIL, and so on. This raises a natural question: is this extension of von Neumann's algorithm the best possible?

Here we give new algorithms for simulating a flip of an unbiased coin by flipping a coin of unknown bias. We are interested in efficient algorithms, where the expected number of flips (as a function of the bias) is our measure of efficiency. Other authors have represented algorithms as lattices, but by representing them instead as trees we are able to produce an algorithm more efficient than any previously appearing. This algorithm is quite easy to implement.

We also prove a conjecture of Hoeffding and Simons that there is no optimal algorithm, i.e., there is no algorithm that is best for all possible values of the bias. We do this in a very strong sense by giving a specific tree T such that if T' is the same tree with the roles of heads and tails reversed, then there is a bias probability p such that for any algorithm A for unbiasing coins, the expected number of flips required by A is more than the expected number required by the better of T and T'.

We also consider generalizations where the input is a sequence of iid discrete random variables and the output is a uniform random variable with N possible outcomes. In this setting we provide an algorithm significantly superior to those previously published.

Keywords: biased coin, random bit, unbiased coin, randomization, random number generator, uniform distribution,

Complete paper:   This paper appears in Annals of Probability 12 (1984), pp. 212-222. It was digitized and placed on JSTOR.

Copyright © 2005-2024 Quentin F. Stout