Unbiased Coin from a Biased Coin
You have a coin whose probability of landing heads is some unknown $p \in (0,1)$. You don't know $p$, and you can't measure it.
Design a procedure that uses only this biased coin to produce outcomes that are exactly fair -- each outcome should have probability exactly $\frac{1}{2}$, regardless of the value of $p$.
Once you have a procedure, derive the expected number of coin flips needed to generate one fair outcome, as a function of $p$.
Hints
- You can't correct for the bias if you don't know $p$. Look for events whose probabilities don't depend on $p$ at all -- or at least events that have equal probability regardless of $p$.
- Flip the coin twice and compare the two outcomes. What can you say about $P(HT)$ vs $P(TH)$?
- Since $P(HT) = P(TH) = p(1-p)$, map one to Heads and the other to Tails. Discard same-outcome pairs and repeat. The number of rounds is geometric.
Worked Solution
How to Think About It: The challenge is that you don't know $p$, so you can't "correct" for the bias directly. You need a trick that makes the bias cancel out. The key observation: if you flip the coin twice, the probability of getting HT is $p(1-p)$, and the probability of getting TH is $(1-p)p$. Those are identical -- the unknown bias appears symmetrically and cancels. So any time you see HT vs TH, you are looking at two equally likely events, regardless of $p$. That is your source of fairness.
Key Insight: Symmetry kills the bias. The pair HT and the pair TH always have the same probability, so mapping one to "heads" and the other to "tails" gives you a perfect fair coin.
The Method (Von Neumann's Trick):
- Flip the coin twice.
- If the result is HT, output "Heads."
- If the result is TH, output "Tails."
- If the result is HH or TT, discard both flips and go back to step 1.
Why it works: The four possible outcomes of two flips have probabilities:
$$P(HH) = p^2, \quad P(HT) = p(1-p), \quad P(TH) = (1-p)p, \quad P(TT) = (1-p)^2$$
Since $P(HT) = P(TH)$, conditioning on a "usable" pair (one where we don't discard) gives:
$$P(\text{output Heads} \mid \text{usable}) = \frac{p(1-p)}{p(1-p) + (1-p)p} = \frac{1}{2}$$
This holds for every $p \in (0,1)$. The bias cancels exactly.
Expected Number of Flips:
The probability of getting a usable pair on any given round is:
$$P(\text{usable}) = P(HT) + P(TH) = 2p(1-p)$$
Each round that fails (HH or TT) is independent, so the number of rounds until the first usable pair is geometric with success probability $2p(1-p)$. Each round costs 2 flips, so:
$$E[\text{flips}] = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}$$
Quick Estimate: For a mildly biased coin with $p = 0.6$: $E[\text{flips}] = 1/(0.6 \times 0.4) = 1/0.24 \approx 4.2$. For a heavily biased coin with $p = 0.9$: $E[\text{flips}] = 1/(0.9 \times 0.1) \approx 11.1$. The closer $p$ is to 0 or 1, the more flips you waste on same-outcome pairs. At $p = 0.5$ (already fair), you need $E = 4$ flips -- which is the best case, and also the least useful since the coin is already fair.
Practical Considerations:
- The method is simple but wasteful for extreme biases. When $p$ is near 0 or 1, almost all pairs are discarded.
- Peres (1992) showed you can recycle the discarded pairs: apply the same trick recursively to the sequence of discards. This extracts more fair bits per flip, approaching the information-theoretic limit of $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$ fair bits per biased flip.
- In practice, if you know $p$ approximately, there are more efficient schemes. Von Neumann's trick is the go-to when $p$ is truly unknown.
Answer: Flip the coin in pairs: HT maps to Heads, TH maps to Tails, and same-outcome pairs are discarded. This produces an exactly fair coin for any $p \in (0,1)$. The expected number of flips per fair outcome is $\frac{1}{p(1-p)}$.
Intuition
The deep principle here is that symmetry can eliminate unknown parameters. You don't need to know $p$ or estimate it -- you just need to find events where $p$ appears the same way on both sides. Flipping twice and comparing gives you exactly that: HT and TH are mirror images of each other, so whatever $p$ does to one, it does identically to the other. This idea -- using symmetry to cancel unknowns -- shows up constantly in quantitative work. In market making, you might pair off symmetric exposures to cancel out an unknown parameter. In Monte Carlo simulation, antithetic variates use the same trick: pair a random draw with its mirror to reduce variance without knowing the distribution's details.
The efficiency question is also instructive. Von Neumann's trick throws away information (the discarded HH/TT pairs still carry entropy about $p$). Peres's recursive improvement shows that you can squeeze out nearly all the randomness, but the basic trick is already good enough for most practical purposes. The takeaway: a simple, provably correct method that wastes some efficiency is almost always better than a clever method that might be subtly wrong.