Question
Given a biased coin with probability of heads $p \neq \tfrac12$, how can we simulate a fair coin?
Solution

Naive method (Von Neumann trick).

Consider pairs of tosses. The outcomes $TH$ and $HT$ have equal probability: $$ \mathbb{P}[TH] = p(1-p), \qquad \mathbb{P}[HT] = p(1-p). $$

But $$ \mathbb{P}[HH] = p^2, \qquad \mathbb{P}[TT] = (1-p)^2, $$ which are not equal unless $p=\tfrac12$.

So we define:

  • $TH \mapsto H$
  • $HT \mapsto T$
  • discard $HH$ and $TT$

This produces a fair coin.

Solution

Expected number of tosses.

One fair outcome occurs when the pair is either $TH$ or $HT$, whose total probability is $$ \mathbb{P}[TH] + \mathbb{P}[HT] = 2p(1-p). $$

Each attempt uses $2$ tosses, so the expected number of tosses is $$ 2 \times \frac{1}{2p(1-p)} = \frac{1}{p(1-p)}. $$