A Fair Coin from a Biased One

The problem
a biased coin · P(H) = p, unknownHP(H) = pTP(T) = 1 − psimulate a perfect 50/50 outcome — how?

You have a single coin that lands heads with some unknown probability p∈(0,1)p \in (0, 1). You need to generate one fair coin flip — a single bit that is exactly 50/5050/50 — using only this biased coin.

Can you do it exactly, with no knowledge of pp?

Tempting (but wrong)
"flip 1000 times, calibrate, correct"THHTHHTHHTbut you never know p exactlyno amount of calibration gives an exact 50/50 flip

The instinctive plan: calibrate first.

Flip the coin a thousand times, estimate p^\hat p, then use p^\hat p to "correct" future flips. But:

  • You can never know pp exactly — only an estimate.
  • Even with exact pp, there's no straightforward map from a single biased flip into a fair one.
  • Any procedure based on an estimate gives an approximately fair bit, not an exactly fair one.

You can do exactly 50/5050/50 with no estimation at all.