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?

coin-obverse-small

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<p<1, 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:

vn-10000-100

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:

prob-rejections

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.

expected-retries

*
* *

Von Neumann’s original paper can be found here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: