Suppose you have a crooked coin. It lands heads with a probability $p$ that you do not know, perhaps $0.7$, perhaps $0.55$. Can you use it for a perfectly fair, fifty-fifty draw?

In the same 1951 paper in which he spoke of the “state of sin” of those who manufacture random numbers, von Neumann gave a short and surprising answer.

The trick

Toss the coin twice:

  • if it comes up heads, tails, say “heads”;
  • if it comes up tails, heads, say “tails”;
  • if it comes up heads, heads or tails, tails, forget it and toss twice more.

Why is it fair? The two tosses are independent, so

$$P(\text{heads, tails}) = p\,(1-p), \qquad P(\text{tails, heads}) = (1-p)\,p.$$

They are the same number, whatever $p$ is. Ties are thrown away, and among the results that remain, heads and tails have exactly the same chance. There is no need to know how biased the coin is, only that the tosses do not influence one another.

What it costs

The price is throwing away pairs. The chance that a pair is usable is $2p(1-p)$. With a fair coin, $p = \frac12$, a pair is usable with probability $\frac12$: on average $2$ pairs, or $4$ tosses, for each result. With a very crooked coin the cost rises sharply: if $p = 0.9$, a pair is usable only with probability $2 \times 0.9 \times 0.1 = 0.18$, and on average about $11$ tosses are needed per result.

Von Neumann’s method is the grandfather of randomness extractors, which turn imperfect sources of chance, such as the electrical noise of a circuit or the movements of a mouse, into the uniform bits cryptography demands.

Exercise: a 70% coin

With $p = 0.7$, compute the probability of each kind of pair and the average number of tosses per result.

$P(\text{heads, heads}) = 0.49$, $P(\text{tails, tails}) = 0.09$, $P(\text{heads, tails}) = P(\text{tails, heads}) = 0.21$. A pair is usable with probability $0.42$. The number of pairs until the first usable one has mean $\frac{1}{0.42} \approx 2.4$, or about $4.8$ tosses per result.

Exercise: why not a single toss?

Someone proposes: “toss once; if it’s heads, toss again and use the second result”. Is that fair?

No. The second toss is still biased: it comes up heads with probability $p$, whatever the first was. No rule that looks at one toss at a time can correct the bias without knowing $p$. Von Neumann’s trick works because it compares two tosses and uses the symmetry between the orders “heads, tails” and “tails, heads”.

Sources: John von Neumann, “Various techniques used in connection with random digits”, National Bureau of Standards Applied Mathematics Series 12 (1951) · Persi Diaconis, Susan Holmes and Richard Montgomery, “Dynamical bias in the coin toss”, SIAM Review (2007).

All topics on John von Neumann · ← The Monte Carlo method: calculating by rolling dice · Self-reproducing automata →

Image credits.