Biased Coin to Fair Bit (Von Neumann)

Puzzle

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.

Hint

Use two-toss ordered pairs and keep only anti-symmetric outcomes.

Step-by-step solution

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

Answer: Use HT/TH mapping; expected tosses per unbiased bit are 1/(p(1-p)).

Why candidates get it wrong

Using single toss plus threshold is impossible when p is unknown.

Interviewer follow-up

Can you design a streaming variant that wastes fewer tosses on average?

Related topics

• Back to Probability Puzzles

• Logic & Aptitude Puzzles section