Unfair Coin Tossing

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 $p$, and 1 with probability $(1-p)$, with $0, possibly different from ½. Von Neumann gives the following procedure to yield 0 and 1 with an equal probability:

1. Toss the coin twice, record the two results in $x$ and $y$.
2. If $x=y$, discard observations, goto step 1.
3. Return $x$.

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 $p^2$,
• 01 is observed with probability $p(1-p)$,
• 10 is observed with probability $(1-p)p$,
• 11 is observed with probability $(1-p)^2$.

We can verify what the sum of the probabilities of all occurrences sum to 1, as expected. We reject the tosses with probability $p^2+(1-p)^2$ (we can sum the probabilities directly because the events they represent are disjoint). Now, we accept the tosses with probability $2p(1-p)$, 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 $p$:

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, $p^2+(1-p)^2$ looks like:

The procedure draws until a favorable outcome is met with probability $2p(1-p)$. That’s a geometric distribution, with parameter $a=2p(1-p)$, with expectation $\frac{1}{a}$. The smaller $a$ gets, the greater the number of retries is. If $a\approx{1}$, the expected number of retries is close to 1.

*
* *

Von Neumann’s original paper can be found here.