Puzzle 3 : Biased Coin to Fair Coin
A coin lands HEADS with probability p and TAILS with probability 1-p, where the coin is biased.
We can still generate a fair result using the Von Neumann trick: flip twice, keep only HT or TH, and ignore HH and TT.
HT → return HEADS
TH → return TAILS
HH / TT → retry
1) Generate one fair result
Choose any biased probability p. The simulator uses the biased coin internally but outputs a fair answer.
★ ★ ★ ★ ★ ★
€
2002
★ ★ ★ ★ ★ ★
Realistic euro-style coin with distinct heads and tails faces, metallic depth, ridged edge, and a full 3D landing flip.
2) Why this is fair
- Flip the biased coin two times.
- If the result is
HT, output HEADS.
- If the result is
TH, output TAILS.
- If the result is
HH or TT, discard and repeat.
P(HT) = p(1-p)
P(TH) = (1-p)p
These are equal, so the accepted outcomes are perfectly balanced.
3) Run many trials
This repeatedly uses the algorithm above and shows that the accepted output approaches 50/50 even though the source coin is biased.
4) Commented Python Code
import random
# Simulate one flip of the biased coin.
# Returns H with probability p and T otherwise.
def biased_flip(p):
if random.random() < p:
return "H"
return "T"
# Use Von Neumann's method to remove the bias.
# Keep flipping in pairs until we see HT or TH.
def fair_flip(p):
while True:
first = biased_flip(p) # First biased flip
second = biased_flip(p) # Second biased flip
# HT and TH have the same probability p(1-p).
# So we map them to opposite fair outputs.
if first == "H" and second == "T":
return "HEADS"
if first == "T" and second == "H":
return "TAILS"
# If we get HH or TT, ignore that pair and try again.
# Example usage
p = 0.8 # The original coin is biased toward heads
print(fair_flip(p))
Pseudocode
function fairFlip():
while true:
a = biasedFlip()
b = biasedFlip()
if a == HEADS and b == TAILS:
return HEADS
if a == TAILS and b == HEADS:
return TAILS
// otherwise HH or TT, ignore and retry