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)).
Using single toss plus threshold is impossible when p is unknown.
Can you design a streaming variant that wastes fewer tosses on average?