Unbiased Coin from a Biased Coin

Expectation · Medium · Free problem
You have a coin whose probability of landing heads is some unknown $p \in (0,1)$. You don't know $p$, and you can't measure it. Design a procedure that uses only this biased coin to produce outcomes that are exactly fair -- each outcome should have probability exactly $\frac{1}{2}$, regardless of the value of $p$. Once you have a procedure, derive the expected number of coin flips needed to generate one fair outcome, as a function of $p$.

Open the full interactive solver, hints, and worked solution →