# Getting a fair result with an unfair coin

Source: https://www.techinterview.org/post/3233458616/getting-a-fair-result-with-an-unfair-coin/
Updated: 2026-07-05 · techinterview.org

How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?

## 2026 Update: Von Neumann's Fair Coin Trick — Bias-Free Sampling

Classic puzzle: You have a biased coin (P(heads) = p, unknown). How do you generate a fair 50/50 outcome?

**Von Neumann's solution:** Flip twice. If HT → call it heads. If TH → call it tails. If HH or TT → repeat. Both HT and TH have probability p(1-p) — equal regardless of p!


```
import random

def fair_from_biased(biased_prob: float) -> str:
    """Generate fair 0/1 using a biased coin with probability p of heads."""
    while True:
        flip1 = random.random() < biased_prob
        flip2 = random.random() < biased_prob
        # Keep only the mixed outcomes: HT and TH each occur with prob p(1-p)
        if flip1 and not flip2:
            return 'H'
        if not flip1 and flip2:
            return 'T'
        # HH or TT: ambiguous, discard and flip again

def expected_flips_von_neumann(p: float) -> float:
    """Expected number of flips per fair output."""
    # P(accept) = P(HT) + P(TH) = 2p(1-p)
    # E[rounds] = 1/P(accept), each round uses 2 flips
    p_accept = 2 * p * (1 - p)
    return 2 / p_accept

# For p=0.3: expected flips = 2 / (2*0.3*0.7) = 2/0.42 ≈ 4.76
print(f"Expected flips (p=0.3): {expected_flips_von_neumann(0.3):.2f}")

# Verify fairness empirically
def test_fairness(p, n_trials=100000):
    heads = sum(1 for _ in range(n_trials) if fair_from_biased(p) == 'H')
    return heads / n_trials

for p in [0.1, 0.3, 0.7, 0.9]:
    fairness = test_fairness(p, 20000)
    print(f"p={p}: fair output heads fraction = {fairness:.3f} (target ~0.500)")

# Mathematical proof it works:
# P(output H) = P(HT) / (P(HT) + P(TH)) = p*(1-p) / (p*(1-p) + (1-p)*p) = 0.5
print("nMath: P(output H) = p*(1-p) / [p*(1-p) + (1-p)*p] = 0.5 for all p")
```

**Real-world applications:**

- **Cryptography:** Hardware RNGs have bias; von Neumann debiasing is a standard step before use

- **A/B testing:** When assignment mechanism is suspected biased, use rejection sampling

- **Load balancing:** Generating uniform random server selections from a non-uniform source

- **Machine learning:** Rejection sampling underlies MCMC algorithms and importance sampling

**Efficiency note:** Von Neumann's method is inefficient when p is near 0 or 1 (most flips are discarded). Elias (1972) and Peres (1992) algorithms extract more entropy per flip sequence. For p=0.01, von Neumann uses ~200 flips per fair bit; Peres uses ~20.