Alice wants to pick one of three desserts, each with equal probability, using only a coin. We consider two versions:

  1. The coin is fair.
  2. The coin is biased, but the bias is unknown.

Part 1: Using a Fair Coin

A fair coin gives two outcomes: H (heads) or T (tails). Here’s one strategy:

Step 1: Encode the outcomes

  • Toss the coin twice:
    • HT → choose dessert 1
    • TH → choose dessert 2
    • HH → choose dessert 3
    • TT → discard and retry

Why it works:

  • Each of HT, TH, HH, TT has probability 14 \frac{1}{4} .
  • By discarding TT and re-tossing, you ensure that each valid outcome has equal probability 13 \frac{1}{3} .

Expected number of tosses:

  • Probability of success per trial = 34 \frac{3}{4}
  • Expected tosses per success ≈ 23/4=83 \frac{2}{3/4} = \frac{8}{3}

Part 2: Using a Biased Coin (Bias Unknown)

Now the coin is biased, with unknown p=P(H) p = P(H) , 0<p<1 0 < p < 1 . We need a method that’s unbiased regardless of p p .

Von Neumann’s Trick:

  • Toss the coin twice:
    • HT → output 1
    • TH → output 0
    • HH or TT → discard and retry

This gives a fair bit.

Step-by-Step:

  1. Generate fair bits using Von Neumann’s method.
  2. Use two fair bits to generate numbers 0–3:
    • 00 → dessert 1
    • 01 → dessert 2
    • 10 → dessert 3
    • 11 → discard and retry

Now each dessert has probability 13 \frac{1}{3} , using only a biased coin with unknown bias.

Conclusion

  • With a fair coin: Use 2 tosses; map 3 outcomes, reject the 4th.
  • With a biased coin: Use Von Neumann’s method to extract fair bits, then proceed as above.

Both strategies ensure each dessert has probability:

13 \boxed{\frac{1}{3}}

Reference