A old problem, due to von Neumann goes as follows:
You have a biased coin that produces heads (H) with probability , and tails (T) with probability You don’t know . How can you use this coin to simulate an unbiased coin?
The next paragraph contains a solution, so if you want to solve the problem yourself, stop reading now!
von Neumann’s solution was as follows*:
- Flip the coin twice
- If the outcome is HT, output H
- If the outcome is TH, output T
- Otherwise, go to 1.
A nice solution, but you can see that you might need to flip the coin many times. In particular, the probability of getting either HH or TT in any particular round is , which could be really big for highly biased coins.
Is there a more efficient method?
Today I found a beautiful paper examining this question. The insight is that the von Neumann scheme is based on symmetry– picking pairs of output strings that have equal probability, then outputting heads for one and tails for the other.
You can draw an (infinitely large) tree, with branches corresponding to random coin flip outcomes, and leaf nodes for an output. The expected number of coin flips for an output is the expected depth in the tree that one reaches before outputting a result and quitting. Viewed in this light, one can think of ways to create more efficient algorithms. The paper contains trees illustrating this wonderfully.
* Incidentally, when starting a paragraph with the name of a person whose first name is not capitalized, should the first character of the paragraph be capitalized? Which convention takes precedence?