riddle of the day

One of the minimal gems of randomness: extracting perfect justice from a biased source without knowing the bias.

The fair coin

Strategist
Chance and uncertainty

Riddle statement

You have a skewed coin, but you don't know how much.

It can come up heads more times than tails, or the other way around; all you know is that its bias is fixed.
You can toss it as many times as you want, but you cannot use any other coin or any other random mechanism.

You must ultimately produce a perfectly fair result: heads or tails, each with probability exactly 1/2.

How would you do it?

Show solution

Solution

Suppose that the probability of heads is \(p\) and that of tails is \(1-p\).

We observe that:

  • the probability of heads-tails is \(p(1-p)\)

  • the probability of tails-heads is \((1-p)p\)

They are exactly equal, whatever \(p\).

If we limit ourselves to those two cases and discard the others, we obtain two perfectly balanced results.

The procedure is:

  • flip the coin twice;

  • if heads-tails, declare heads;

  • if tails-heads, declare tails;

  • if heads-heads or tails-tails, discard the attempt and repeat.

The final result is exactly fair, regardless of the bias of the coin.