Simulating a Fair Coin Using a Biased Coin

Suppose we have a coin that lands Heads with some unknown probability p, where

0 < p < 1

We do not need to know what p is. We can still generate a perfectly fair 50/50 result.

The Trick

  1. Flip the biased coin twice.
  2. If the result is HT, output Heads.
  3. If the result is TH, output Tails.
  4. If the result is HH or TT, ignore those flips and start again.

HH

Discard

HT

Output Heads

TH

Output Tails

TT

Discard

Why Does This Work?

Let

P(H) = p
P(T) = 1 - p

Because the two flips are independent:

P(HT) = p(1-p)

and

P(TH) = (1-p)p

But multiplication is commutative:

p(1-p) = (1-p)p

Therefore,

P(HT) = P(TH)

So whenever we get one of the two usable outcomes HT or TH, they are equally likely.

Pair Probability Action
HH p² Discard
HT p(1-p) Output Heads
TH (1-p)p Output Tails
TT (1-p)² Discard

Conditional Probability

Given that the two flips are different, the only possibilities are HT and TH.

P(HT | different) = p(1-p) / [p(1-p) + (1-p)p] = 1/2

Similarly,

P(TH | different) = 1/2

Therefore the final output is a perfectly fair 50/50 coin.

Example

Suppose the original coin is extremely biased:

P(H) = 0.8
P(T) = 0.2

Then:

P(HT) = 0.8 × 0.2 = 0.16

P(TH) = 0.2 × 0.8 = 0.16

Even though Heads itself occurs 80% of the time, the patterns HT and TH occur with exactly the same probability.

Algorithm

while true:

    flip coin twice

    if result == HT:
        return Heads

    if result == TH:
        return Tails

    # HH or TT
    # throw them away and repeat

Intuition

Don't try to make a single biased flip fair.

Instead, look for two events that are guaranteed to have equal probability.

The two sequences

HT and TH

contain exactly one Head and one Tail, just in opposite orders.

Therefore both have probability

p(1-p)

and we can use them as our two equally likely outcomes.

Important Assumption

The flips must be independent and must use the same fixed probability p each time.

Also, if p = 0 or p = 1, the method cannot work because the coin never produces both Heads and Tails.

This method is known as the von Neumann extractor.