You have a biased coin with P(heads)=p. How can you simulate a fair coin using this biased coin?

You have a biased coin with P(heads)=p. How can you simulate a fair coin using this biased coin?

Approach: Flip coin twice until outcomes differ, then take first result.

Flip the coin twice. If outcomes are HT, output H. If TH, output T. If HH or TT, repeat. P(H)=P(T)=p(1-p)/[2p(1-p)]=1/2.

Follow-up: What is the expected number of flips needed?

Key concepts: von Neumann extractor, randomness extraction, independent trials.