Pick 1 of 3 Desserts Using Only a Coin
Alice wants Cake, Ice Cream, and Pudding to each be chosen with probability exactly 1/3.
Toss the fair coin twice
HH
🍰 Cake
Probability 1/4
HT
🍦 Ice Cream
Probability 1/4
TH
🍮 Pudding
Probability 1/4
TT
↻ Retry
Probability 1/4
We keep only HH, HT, TH. Since those three outcomes are equally
likely, conditioning on acceptance gives
(1/4) / (3/4) = 1/3
for each dessert.
Step 1: Extract a fair bit
Let the unknown probability of heads be p. Toss the biased coin twice.
HH
Discard
p²
HT
Fair bit 0
p(1-p)
TH
Fair bit 1
(1-p)p
TT
Discard
(1-p)²
The key observation is
P(HT) = p(1-p) = (1-p)p = P(TH)
so when the two tosses differ, HT and TH are equally likely.
This is the von Neumann extractor.
Step 2: Use two extracted fair bits
00
🍰 Cake
01
🍦 Ice Cream
10
🍮 Pudding
11
↻ Retry
The extracted bits are fair, so the same 3-out-of-4 rejection method gives each
dessert probability exactly 1/3.
LATEST RESULT
—
Press “Pick once”.
0 accepted picks
Target: 33.33% each
How to discover the solution in an interview
1. Notice the mismatch
One fair coin gives 2 states, but you need 3 equally likely choices.
One fair coin gives 2 states, but you need 3 equally likely choices.
2. Create a power of two
Two fair tosses give 4 equally likely states. Assign 3 and reject 1.
Two fair tosses give 4 equally likely states. Assign 3 and reject 1.
3. Remove unknown bias
For a biased coin, HT and TH have equal probability, so use them as fair bits.
For a biased coin, HT and TH have equal probability, so use them as fair bits.