Difficulty: Medium · Puzzle 1 of 6 · Topic: Probability Puzzles
Given a biased coin with unknown P(H)=p, generate an unbiased bit and compute expected tosses per fair bit.
Use two-toss ordered pairs and keep only anti-symmetric outcomes.
1) Toss twice; outcomes are HH, HT, TH, TT.
2) Emit 1 for HT, emit 0 for TH, reject HH and TT.
3) Fairness: P(HT)=p(1-p) and P(TH)=(1-p)p, so both outputs are equiprobable.
4) Acceptance probability per 2-toss trial is P(HT or TH)=2p(1-p).
5) Expected accepted-trial count is 1/[2p(1-p)].
6) Multiply by 2 tosses per trial => expected tosses = 1/[p(1-p)].Answer: Use HT/TH mapping; expected tosses per unbiased bit are 1/(p(1-p)).
Checked by running a model of the rule in a Python model. A computational check: exact fractions show HT and TH are equally likely and the expected tosses equal 1/(p(1-p)); a fixed-seed simulation shows the Peres extractor yields about 0.85 fair bits per toss versus 0.21 for plain von Neumann at p = 0.3.
Applying a single toss plus a threshold: with unknown p there is no threshold that yields 50/50. The pair trick works because HT and TH have the same probability p(1-p) for every p.
Can you design a streaming variant that wastes fewer tosses on average? Model answer: yes, the Peres (iterated von Neumann) extractor. Besides the HT/TH bit it also feeds the discarded information back in: the sequence of 'pair was equal or not' and the values of the equal pairs (HH->H, TT->T) are recursively extracted again. It gets close to the entropy limit H(p) bits per toss instead of p(1-p) bits per toss.
I toss the coin twice, and I keep the pair only if the two tosses differ. Heads then tails has probability p times one minus p, and tails then heads has the same probability, so I output one for head-tail and zero for tail-head, and the bit is fair for every p. Each pair is accepted with probability two p times one minus p, and each pair costs two tosses, so the expected number of tosses per fair bit is one over p times one minus p. The trap is using a single toss with a threshold, which cannot give fifty-fifty when p is unknown.