Probability & Statistics

Fair Odds from an Unfair Coin

A coin is biased by an unknown amount. Can you still extract a perfectly fair flip from it?

solvedmedium1 min

You have a coin biased toward heads or tails by some unknown amount. Can you use it to generate an even-odds outcome, a genuinely fair flip?

Reveal solutionHide solution

#Pair the flips

Yes. Flip the coin twice and read the ordered pair. Treat HTHT as one outcome and THTH as the other, and throw away HHHH and TTTT, flipping a fresh pair until a mismatch appears.

Whatever the bias pp toward heads, the two mismatched pairs are equally likely,

P(HT)=p(1−p)=P(TH),(1)\PP(HT) = p(1-p) = \PP(TH), \tag{1}

because each is one head and one tail in some order. Conditioning on a kept pair, each output has probability exactly one half, and the bias cancels.

The two kept pairs, HT and TH, always carry the same probability, 21.0 percent each, so the output bit is fair however biased the coin. Discarding HH and TT costs yield, only 42 percent of pairs produce a bit, and that shrinks as the bias grows.

#The cost

The discarded HHHH and TTTT are the price. A kept pair appears with probability 2p(1−p)2p(1-p), largest at a fair coin and shrinking toward zero as the bias grows, so a very lopsided coin needs many flips per fair bit.

#A note on efficiency

Discarding both equal pairs is simple but not the most efficient extractor, since those pairs still carry usable randomness. Tree-based schemes recover much of it. See Stout and Warren, Tree Algorithms for Unbiased Coin Tossing with a Biased Coin, Annals of Probability 12 (1984), pp. 212-222.