A Fair Coin from a Biased One
You are handed a coin that lands heads with some unknown probability , where . You may flip it as many times as you like.
Describe a procedure that produces a perfectly fair binary outcome — one that is heads with probability exactly — without knowing . Then compute the expected number of flips your procedure uses.
Solution
The procedure. Flip the coin twice and look at the ordered pair:
HT→ output headsTH→ output tailsHHorTT→ discard and repeat
Why it is fair. The two flips are independent, so
These are equal for every . Conditioning on the event that we stopped — that is, on — gives
The bias cancels because it appears identically in both surviving outcomes. This is von Neumann's trick.
Expected number of flips. Each round costs 2 flips and succeeds with probability
The number of rounds is geometric with mean , so
Sanity check. At this gives 4 flips — we waste half of our rounds on HH/TT. As or the cost blows up, which is right: a nearly deterministic coin rarely produces a mixed pair.
> What the interviewer is listening for. State the procedure, then prove fairness by showing the cancels — candidates who assert symmetry without writing the conditional probability usually get pushed. Expect a follow-up on how to avoid discarding flips (Peres's iterated extractor gets you close to the entropy bound ).