Suppose a coin lands heads with an unknown probability \(p\), which need not equal \(1/2\). Can repeated tosses of that coin still produce unbiased random bits? Estimating \(p\) first is unnecessary. A method due to John von Neumann removes the bias exactly by comparing tosses in pairs.
The method needs a sequence of independent, identically distributed tosses and a non-degenerate coin, \(0<p<1\). It does not need to know the value of \(p\).
The Pairing Argument
Write \(H\) for heads and \(T\) for tails. If \(P(H)=p\), then \(P(T)=1-p\). For two independent tosses, the four possible ordered pairs have probabilities
\[ \begin{array}{c|cc} & H & T\\ \hline H & p^2 & p(1-p)\\ T & (1-p)p & (1-p)^2 \end{array}. \]
The equal pairs \(HH\) and \(TT\) generally have different probabilities, so they cannot represent fair outcomes. The mixed pairs, however, always have the same probability:
\[ P(HT)=p(1-p)=(1-p)p=P(TH). \]
Discard equal pairs and repeat until a mixed pair appears. Then use its first toss as the result:
- Toss the biased coin twice.
- If the pair is \(HH\) or \(TT\), discard it and start again with a fresh pair.
- If the pair is \(HT\), return heads. If it is \(TH\), return tails.
Conditioning on the event that the two tosses differ gives
\[ \begin{aligned} P(HT\mid HT\text{ or }TH) &=\frac{P(HT)}{P(HT)+P(TH)}\\ &=\frac{p(1-p)}{2p(1-p)}\\ &=\frac12. \end{aligned} \]
The same calculation gives \(P(TH\mid HT\text{ or }TH)=1/2\). Rejected pairs affect only how long the procedure runs; they do not change the distribution of the accepted result.
Example with \(p=0.6\)
For a coin with \(P(H)=0.6\), the pair probabilities are
\[ \begin{array}{c|cc} & H & T\\ \hline H & P(HH)=0.36 & P(HT)=0.24\\ T & P(TH)=0.24 & P(TT)=0.16 \end{array}. \]
Although heads is more likely on every individual toss, the accepted pairs \(HT\) and \(TH\) occur with equal probability. Given that a pair is accepted, each one therefore accounts for exactly half of the outcomes.
Expected Number of Tosses
A pair is accepted when its two tosses differ. Its acceptance probability is
\[ a=P(HT)+P(TH)=2p(1-p). \]
Let \(N\) be the number of pairs examined up to and including the first accepted pair. Because each pair is an independent trial with success probability \(a\), \(N\) follows a geometric distribution:
\[ P(N=n)=(1-a)^{n-1}a, \qquad n=1,2,\ldots \]
Its expected value is \(E[N]=1/a\). Each round consumes two tosses, so the total number of tosses is \(T=2N\):
\[ \boxed{ E[T]=2E[N]=\frac{2}{2p(1-p)}=\frac{1}{p(1-p)} }. \]
The same result follows from the recurrence \(E[T]=2+(1-a)E[T]\): every attempt costs two tosses, and after a rejection the expected remaining work is again \(E[T]\).
The variance follows from \(\operatorname{Var}(N)=(1-a)/a^2\):
\[ \operatorname{Var}(T) =4\operatorname{Var}(N) =\frac{4(1-a)}{a^2} =\frac{1-2p(1-p)}{p^2(1-p)^2}. \]
Even for a fair input coin, half of all pairs are equal, so the procedure needs four tosses per output on average. For \(p=0.6\), the expectation is
\[ E[T]=\frac{1}{0.6\cdot0.4}=\frac{25}{6}\approx4.17. \]
As \(p\) approaches \(0\) or \(1\), mixed pairs become rare and the expected running time diverges. At either endpoint the algorithm never terminates because the source contains no randomness to extract.
Expected input tosses per fair output, \(E[T]=1/(p(1-p))\), for \(0<p<1\).
Implementation
The implementation follows the pairing rule directly. Here true represents heads and false represents tails.
function fairCoin(toss) {
while (true) {
const first = toss();
const second = toss();
if (first !== second) {
return first;
}
}
} A biased source can be used to verify the result experimentally:
function biasedCoin(p) {
if (!(p >= 0 && p <= 1)) {
throw new RangeError("p must lie between 0 and 1");
}
return () => Math.random() < p;
}
const toss = biasedCoin(0.6);
let heads = 0;
const samples = 100000;
for (let i = 0; i < samples; i++) {
if (fairCoin(toss)) {
heads++;
}
}
console.log(heads / samples); // Approximately 0.5 The finite simulation fluctuates around \(1/2\), while the pairing argument proves that the exact output probability is \(1/2\). Simulation is useful as a check, but it is not what removes the bias.
Assumptions and Limitations
The equality \(P(HT)=P(TH)\) depends on the two tosses having the same bias and being independent. If the bias changes between tosses or successive results are correlated, the equality can fail and the output need not be fair. Non-overlapping pairs are also essential; reusing one toss in two adjacent pairs changes the dependence structure.
The method is exact but not maximally efficient because every equal pair is discarded. Elias showed how blocks of biased tosses can be converted more efficiently, and Peres later gave an iterative procedure that recycles information discarded by the von Neumann method. These refinements approach the entropy limit while preserving unbiased output under the same IID model.
References
- [vonNeumann1951]J. von Neumann, “Various Techniques Used in Connection with Random Digits,” Monte Carlo Method, National Bureau of Standards Applied Mathematics Series 12, pp. 36–38, 1951.
- [Elias1972]P. Elias, “The Efficient Construction of an Unbiased Random Sequence,” The Annals of Mathematical Statistics, vol. 43, no. 3, pp. 865–870, 1972. doi:10.1214/aoms/1177692552
- [Peres1992]Y. Peres, “Iterating von Neumann's Procedure for Extracting Random Bits,” The Annals of Statistics, vol. 20, no. 1, pp. 590–597, 1992. doi:10.1214/aos/1176348543