Making a Fair Coin From a Biased One

You're handed a coin that lands heads with some unknown probability $p \ne 1/2$ — you don't know $p$, and it could be close to 0 or 1. Using only this coin, produce a perfectly fair 50/50 outcome. It looks like you need to know $p$ to correct for it. You don't.

The puzzle and the trick

Given a biased coin with unknown bias $p$, construct a procedure using only flips of that coin that outputs "heads" or "tails" with probability exactly $1/2$ each.

The move. Flip the coin twice. If the two flips come out the same (HH or TT), discard the pair and flip twice again. If the two flips disagree (HT or TH), stop and output "heads" if the result was HT, or "tails" if it was TH.

Why it's exactly fair. The probability of HT is $p(1-p)$, and the probability of TH is $(1-p)p$ — the same expression, in either order, because flips are independent. These two probabilities are always equal, for any $p$ whatsoever, even though you don't know what $p$ is. Conditioning on "the pair disagreed" (i.e., throwing away the HH and TT pairs and only looking at HT/TH), the two remaining outcomes each have probability exactly $\dfrac{p(1-p)}{2p(1-p)} = \dfrac12$.

Numerical check. Say $p = 0.9$ (a very biased coin). $P(\text{HT}) = 0.9 \times 0.1 = 0.09$. $P(\text{TH}) = 0.1 \times 0.9 = 0.09$. Identical, as promised — the bias cancels because it appears once as $p$ and once as $(1-p)$ in each ordered pair, regardless of which one plays which role.

This is a real technique, not just a puzzle: hardware random-number generators built from physically biased sources (thermal noise, jitter) use exactly this von Neumann de-biasing step before the output is trusted for cryptographic or simulation use.