Algorithms for the Masses by Julian M Bucknall

This is a very handy algorithm that I came across today, which is, according to this paper, due to John von Neumann.

Suppose you have a coin which you suspect to be biased. You're not sure whether it's biased to heads or to tails, you just know it's biased. Actually, according to the wikipedia article on coin flipping, coins tend to be slightly biased naturally and it's possible to train yourself to flip a coin slightly more predictably than pure chance. So there you are with a biased coin. Nevertheless, can you use it to produce unbiased tosses?

Von Neumann came up with a remarkable idea: use tosses in pairs. If the first toss of a pair comes up heads and the second tails, call the result of the pair heads. If the first comes up tails and the second heads, call it tails. If both tosses produce the same result (heads/heads or tails/tails), ignore that pair, and start over.

In mathematical terms, we assume that all the individual flips are independent. So if the probability of getting heads is p and the probability of getting tails is q, where p + q = 1, then the probability of heads followed by tails is exactly the same as the reverse result, namely pq. Since we ignore all other pairs of tosses, it means that the overall "coin pair toss" is unbiased. Note that the algorithm doesn't require you to know what the probabilities are (though obviously if it's a two-headed coin, you'll never get any unbiased tosses!).

Posts on similar topics...

• I find these attitudes scary
• Converting data from Passwords Plus to SplashID
• Someone is wrong on the internet — the lock-free stack edition