Suppose you want a fair coin, one that yields heads and tails with equal probability, but only have a bizarre coin that yields a side more often than the other. Can we remove the bias?

John von Neumann gave us a surprisingly simple procedure to remove bias from a coin and yield a fair toss.

Suppose you have a “coin” yielding a 0 with probability , and 1 with probability , with , possibly different from ½. Von Neumann gives the following procedure to yield 0 and 1 with an equal probability:

- Toss the coin twice, record the two results in and .
- If , discard observations, goto step 1.
- Return .

In C, the procedure would look something like

int fair_toss() { int x,y; do { x=Coin(); y=Coin(); } while (x==y); return x; }

How does it work? If we look at the probability of various combinations, we find that

- 00 is observed with probability ,
- 01 is observed with probability ,
- 10 is observed with probability ,
- 11 is observed with probability .

We can verify what the sum of the probabilities of all occurrences sum to 1, as expected. We reject the tosses with probability (we can sum the probabilities directly because the events they represent are disjoint). Now, we accept the tosses with probability , but the most interesting point is that 01 and 10 are drawn *with the same probability*, half of the time with 0 first, half of the time with 1 first. Therefore, we get 0 and 1 with equal probability, *if* we don’t reject tosses. Awesome!

*

* *

Let’s verify this procedure empirically. Using *Mathematica* it’s easy to get a biased random source and draw nice plots.

This procedures simulates an unfair coin yielding 0 with probability :

UnfairCoin[p_] := If[RandomReal[] <= p, 0, 1]

This one unbiases it:

vonDraw[p_] := Module[{t1 = 0, t2 = 0}, While[t1 == t2, t1 = UnfairCoin[p]; t2 = UnfairCoin[p]; ]; Return[t1] ]

Let’s see how good it works by making 100 experiments of 10000 unbiased draws:

z = Table[Fold[Plus, 0, Table[vonDraw[0.3], {10000}]], {100}]

…and look at them using a box-plot:

It shows a bit of variance, but on average, we’re very close to the ideal, equal probability!

*

* *

The procedure uses rejection, that is, it draws until a favorable outcome is met, and necessarily will repeat a number of times before a favorable outcome is found. But how many times on average?

A plot of rejection probability, looks like:

The procedure draws until a favorable outcome is met with probability . That’s a geometric distribution, with parameter , with expectation . The smaller gets, the greater the number of retries is. If , the expected number of retries is close to 1.

*

* *

Von Neumann’s original paper can be found here.