Making fairness from bias

You have a coin that's biased, but you don't know the bias. It could favor heads or tails by any amount. Can you use this coin to generate a fair 50/50 outcome?

What do you think?

Can you generate a fair outcome from an unfair coin?

Von Neumann's trick

Let $p$ be the probability of heads. The four possible outcomes of two flips:

Pair	Probability
HH	$p^2$
HT	$p(1-p)$
TH	$(1-p)p$
TT	$(1-p)^2$

Since multiplication is commutative, $P(\text{HT}) = p(1-p) = (1-p)p = P(\text{TH})$ .

Von Neumann extractor

To generate a fair bit from a biased coin: flip twice. If the results differ (HT or TH), output the first flip's result. If the results match (HH or TT), discard and try again. This works for any bias $p \in (0,1)$ .

Why HT and TH have equal probability

P(\text{HT}) = p \cdot (1-p)

First flip is heads (probability p), second is tails (probability 1-p). The flips are independent.

Step 1 of 4

Fair from Unfair

Flip an unfair coin twice. Keep only HT and TH results (discard HH and TT). These two outcomes have equal probability regardless of bias.

Coin bias: P(H) = 0.70P(HT) = P(TH) = 0.2100

0.050.500.95

Slide the bias to extreme values like 0.05 or 0.95. The HT and TH counts stay equal even when the coin is heavily biased.

The cost of fairness

The method discards HH and TT pairs, so it wastes some flips. The probability that a pair is useful is:

$P(\text{useful}) = P(\text{HT}) + P(\text{TH}) = 2p(1-p)$

This is maximized at $p = 1/2$ (where $P(\text{useful}) = 1/2$ ) and drops toward 0 as $p$ approaches 0 or 1. With a heavily biased coin, you need many attempts to get a usable pair.

What do you think?

If P(heads) = 0.9, what fraction of flip pairs will be useful?

This problem tests whether you can work with unknowns. The bias $p$ is unknown, but the solution works for every $p$ . In interviews, the question checks if you can find structure that doesn't depend on the specific parameter value.

Practice

If the coin has P(heads) = 0.3, what's P(a pair is useful)? (decimal like 0.42)

1/2