Coin flipping game: how to make a fair toss from an unfair coin

Alice and Bob play a game as follows.

Alice spins a coin on a table and waits for it to land on one side.

If the result is heads, Alice wins $1 from Bob; if tails, Alice pays $1 to Bob.

While the game sounds fair, Bob suspects the coin may be biased to land on heads more. The problem is he cannot prove it.

Being diplomatic, Bob does not accuse Alice of trickery. Instead, Bob introduces a small change in the rules to make the game fair to both players.

What rule could Bob have come up with?

The answer

Bob worries the coin may be biased to land on heads more often than tails. The trick Bob comes up with is a way to turn a biased coin into having fair tosses.

The technique is referred to as the von Neumann procedure, and it works as follows:

1. Spin the coin twice.

2. If the two results are different, use the first spin (HT becomes “heads”, and TH becomes “tails”).

3. If the two results are the same (HH or TT), then discard the trial and go back to step one.

In other words, Bob has redefined the payout rule to ensure the odds are fair to both parties.

Why does the von Neumann procedure works? The procedure takes advantage that HT and TH are symmetrical outcomes and will thus have equal probability.

To see this, suppose the outcome heads occurs with probability 0.6 and tails with probability 0.4. Then we can directly calculate the probability of the pairs as:

–HT occurs (0.6)(0.4) = 0.24
–TH occurs (0.6)(0.4) = 0.24

These events are equally likely, and hence both players have an even chance of winning the game.

The von Neumann procedure takes advantage that each coin flip is an independent event, and so both mixed pairs of tosses will have equal chances.

Appendix: spinning vs tossing

Observant readers may have noticed the game is about coin spinning rather than coin tossing.

Why the distinction? It’s a small bit of trivia that coin tossing is not easily biased:

“The law of conservation of angular momentum tells us that
once the coin is in the air, it spins at a nearly constant rate
(slowing down very slightly due to air resistance). At any rate
of spin, it spends half the time with heads facing up and half the
time with heads facing down, so when it lands, the two sides
are equally likely (with minor corrections due to the nonzero
thickness of the edge of the coin)”

via Teacher’s Corner: You Can Load a Die, But You Can’t Bias a Coin

The theory is only slightly modified in real-life. In practice, there is still a small bias towards one side of a coin.

I will refer you to this article which summarizes the results from an academic paper that points out coin flipping is almost always slightly biased.

A few of the results are:

If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads)…

If the coin is spun, rather than tossed, it can have a much-larger-than-50% chance of ending with the heavier side down. Spun coins can exhibit “huge bias” (some spun coins will fall tails-up 80% of the time)…

A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.

The lesson is that coin flips are better than coins being spun.

But a coin flip will still exhibit some bias, so to be fair, it may be best to use the von Neumann procedure or another choice mechanism (like a computer random number generator).