A Fair Toss From a Biased Coin

Question

A coin lands heads with unknown probability p (strictly between 0 and 1). Using only this coin, generate a decision that is exactly 50/50, not approximately. How, and what does it cost in flips?

Accepted Answer

Von Neumann's trick. Flip twice: - HT → output "A" - TH → output "B" - HH or TT → discard the pair and flip twice again. P(textHT) = p(1-p) = P(textTH) for every p, so conditional on the procedure stopping, each output has probability exactly tfrac12. Rounds are independent, so the conditioning is clean, no approximation anywhere. The idea has a name: symmetrization. You can't fix the coin's asymmetry between H and T, but the two orderings of a mixed pair are exchangeable, swap the roles of the flips and HT becomes TH. Building an event and its mirror image with identical probability is the move (the same one behind permutation tests). Cost: a round succeeds with probability 2p(1-p), so the expected number of flips is frac22p(1-p) = frac1p(1-p), at p = tfrac12 that's 4 flips; at p = 0.3, about 4.76; as p to 0 or 1 it blows up (a nearly-deterministic coin carries almost no randomness to extract). Trap: "flip once, call heads A" with any post-hoc correction, without knowing p, no deterministic relabeling of single flips can be fair. Pairing is essential.

A Fair Toss From a Biased Coin

Problem

Your answer

Hints

More Brainteasers & Logic to train on