Fair bits from an unfair coin

Every generator on this path so far has needed a seed — a starting state nobody can guess — and has treated the seed as given. Randomness that has to be earned made the point sharply: a cryptographic generator stretches a short unpredictable seed into a long unpredictable stream, and all of its security is borrowed from the seed. Where the seed comes from was named there as a debt.

It comes from the physical world, and the physical world does not produce fair coins. A diode’s noise, the timing of keystrokes, the jitter of a clock: each yields bits that are unpredictable in part, biased towards one value, often correlated with their neighbours, and never exactly what a formula says. Turning such a source into bits that are exactly fair and independent is randomness extraction, and its first and most famous method is a two-line trick of John von Neumann’s from 1951.

The rule, and why it needs no knowledge of the coin #

The rule is the whole method. Read the flips two at a time. If the pair is $01$, output $0$; if it is $10$, output $1$; if it is $00$ or $11$, output nothing and move on.

Suppose the coin lands $1$ with probability $p$ and the flips are independent. Then

$$P(01) = (1 - p)\,p, \qquad P(10) = p\,(1 - p).$$

The two are the same number, because multiplication does not care about order. So among the pairs that produce output, $01$ and $10$ are exactly equally likely, and every output bit is exactly fair. Successive output bits come from different pairs, which are independent, so the output bits are independent as well.

What makes the trick remarkable is what it does not need. The bias $p$ appears in both probabilities and cancels, so the rule works without anyone knowing $p$ — without estimating it, measuring it, or even knowing that it is stable from day to day, so long as it is the same for the two flips in each pair. A method that corrected bias by first measuring it would inherit every error of the measurement; this one inherits none, because it never measures anything. The fairness comes from a symmetry, the same kind of symmetry that makes a needle dropped at random produce $\pi$ without anybody knowing where it will land.

The figure shows the rule working on a visible stretch — most pairs are $11$ and vanish, and the few mixed ones give the output — and on a long run, where the input is $70\%$ ones and the output is within sampling error of one half.

What the fairness costs #

Exact fairness is bought with waste, and the waste depends heavily on the bias.

A pair is kept with probability $2p(1 - p)$, and each kept pair yields one bit from two flips, so the rule produces $p(1 - p)$ output bits per input flip on average. For a fair coin that is a quarter: three-quarters of a perfectly good random stream are thrown away. For a coin with $p = 0.7$ it is $0.21$, which is what the first figure measured.

For a heavily biased coin the waste is severe. At $p = 0.95$ almost every pair is $11$, and the rule keeps under one pair in ten; the output is exactly as fair as before and arrives at less than a twentieth of the input rate. The question the figure raises is whether that is the price of fairness or merely the price of this rule — whether a cleverer method could get more fair bits out of the same coin.

The ceiling set by entropy #

There is a hard limit, and it is Shannon’s. The amount of unpredictability in one flip of a coin with bias $p$ is its entropy,

$$h(p) = -p \log_2 p - (1 - p)\log_2(1 - p)$$

bits. A fair coin has $h = 1$: each flip is one full bit of surprise. A coin with $p = 0.95$ has $h \approx 0.29$: most flips are predictable, and their average surprise is under a third of a bit. No procedure can extract, on average, more fair bits than the source contains, because a fair output bit carries one full bit of unpredictability and the unpredictability has to come from somewhere.

The figure puts the rule against the ceiling. At a fair coin, von Neumann’s yield of $0.25$ sits far below the ceiling of $1$; at $p = 0.95$ its $0.0475$ is a sixth of the ceiling’s $0.29$. At every bias the rule wastes most of what is there, and the gap is widest exactly where the coin is fairest — the rule throws away three-quarters of a coin that needed no correcting at all.

Recycling what was thrown away #

The waste is not inevitable, because the discarded pairs still contain information that nobody has used. Yuval Peres showed in 1992 how to recycle it, and the argument is a small masterpiece of seeing independence where it is not obvious.

A pair of flips produces three things. Whether it was mixed or matched — its exclusive or. If mixed, which way round — the von Neumann output. If matched, which value it matched on — $00$ or $11$. Von Neumann’s rule uses only the second. But the other two are streams of bits in their own right:

• The mixed-or-matched stream is a sequence of independent biased bits: each is $1$ with probability $2p(1 - p)$.
• The matched-value stream, one bit per matched pair, is another: each is $1$ with probability $p^2/(p^2 + (1 - p)^2)$.

Both are independent of the von Neumann output, because knowing which way round a mixed pair fell says nothing about which pairs were mixed or what the matched ones matched on. So the rule can be applied to each of them again, and to the by-products of those, and so on. Each level extracts more fair bits from what the level below discarded.

The yield obeys a recurrence that can be written down directly from that description, and as the number of levels grows it converges to the entropy. The curves in the figure are the recurrence at two, three and six levels: at six the yield at a fair coin is already over $0.8$, where von Neumann alone gave $0.25$, and the dots measured on actual seeded streams sit on the curves. So the ceiling is not merely a bound. It is reachable, by a procedure no more complicated than the original rule applied to its own leftovers, and like the original it never needs to know $p$.

The same ceiling reached by counting #

There is a second route to the ceiling, older than Peres’s and entirely combinatorial, and it shows where the entropy formula comes from.

Take a block of $n$ flips and look only at how many of them are $1$ — say $k$. Every sequence with exactly $k$ ones has the same probability, $p^k (1 - p)^{n-k}$, whatever the order of its flips. So once $k$ is known, the actual sequence is a uniformly random choice among $\binom{n}{k}$ equally likely possibilities, and its position in that list — counting the sequences in dictionary order — is a uniformly random number below $\binom{n}{k}$. A uniform number in a range of that size can be turned into about $\log_2 \binom{n}{k}$ fair bits.

That is Peter Elias’s extractor of 1972, and von Neumann’s rule is its smallest case: a block of two flips with one $1$ has $\binom{2}{1} = 2$ equally likely orders, and choosing between them is one fair bit. With longer blocks the count $\binom{n}{k}$ is an entry of Pascal’s triangle, and for the typical $k$, near $np$, its logarithm is almost exactly $n\,h(p)$ — which is the reason the entropy has the formula it does. Entropy is the logarithm of the number of equally likely arrangements, per flip, and extraction is simply reading off which arrangement occurred.

The price of Elias’s method is only the block length: the yield approaches the entropy as $n$ grows, at a rate governed by how much $\log_2\binom{n}{k}$ falls short of $n\,h(p)$ for moderate $n$. The same logarithm of a binomial count appears wherever the probability of an atypical frequency is estimated — the whole histogram deviating is priced by it — and there it measures how rare a lopsided sample is, where here it measures how much choice a typical one contains.

Balanced is not the same as independent #

Everything so far assumed that successive flips are independent. Physical sources rarely oblige, and the most common failure is stickiness: a bit tends to repeat the one before it.

The output is balanced, and the reason is a small surprise. For any source that switches between two states with fixed probabilities — a two-state Markov chain — the long-run frequency of the transition $0 \to 1$ equals that of $1 \to 0$, because every run of $0$s that starts must end. That is detailed balance, the property that makes a chain run the same backwards, and every two-state chain has it. So $01$ and $10$ are equally common, and von Neumann’s output is exactly balanced even from a sticky source.

But balanced is all it is. The output bits are no longer independent, because the end of one pair predicts the start of the next: a pair ending in $0$ makes the next pair likely to start with $0$, and a pair starting with $0$ that is kept outputs $0$. The figure measures the damage — a correlation of about $-0.24$ between neighbouring output bits, where a fair independent stream would show a number within about $0.02$ of zero. A test that checked only the frequency of ones would pass this output. A test that looked at pairs would fail it at once.

A frequency count cannot certify randomness, and this is the smallest possible demonstration of why. Manuel Blum showed in 1986 how to extract exactly fair independent bits from any Markov source by applying the rule separately to the flips that follow each state — the flips after a $0$ are an independent biased coin, and so are the flips after a $1$ — but that repair only works if the source really is a Markov chain of known order, which is again an assumption about the source.

No single function works for every source #

The sticky source raises the general question: is there one procedure that extracts fair bits from every source with enough unpredictability in it, whatever its structure?

For independent flips, simpler functions than von Neumann’s already help. The exclusive or of $k$ independent flips of a coin with bias $p$ is $1$ with probability $\tfrac12\big(1 - (1 - 2p)^k\big)$ — the piling-up lemma — so its bias shrinks geometrically with $k$.

The dashed line is the same function on a source with plenty of unpredictability — every block of $k$ bits is one fair-ish flip, copied — and it fails completely, because the function’s usefulness depended on independence the source does not have. That is not a defect of exclusive or in particular. Miklos Santha and Umesh Vazirani proved in 1986 that for every fixed function from $n$ bits to one bit, there is a source with a guaranteed amount of unpredictability per bit on which that function’s output is badly biased. No deterministic extractor works for every weak source.

The two ways round are the ones the subject now uses. A seeded extractor adds a short truly random seed to the weak source, and with it can distil almost all the source’s unpredictability — a small amount of perfect randomness leverages a large amount of imperfect randomness. A two-source extractor takes two independent weak sources, each individually untrustworthy, and combines them; with two sources, deterministic extraction becomes possible again. Both are theorems with constructions, and both are about sources described by how much unpredictability they contain rather than by what kind.

How the theory meets a real source #

A physical random-bit generator is built in three layers, and each of the ideas above has a place in one of them.

At the bottom is the noise source itself — thermal noise across a resistor, the timing jitter of a free-running oscillator sampled by a slower clock, the arrival times of radioactive decays. Its raw bits are biased and correlated in ways that drift with temperature and age, and nobody pretends otherwise.

Above it sit health tests, which watch the raw stream for gross failures: a run of identical bits far longer than the source’s estimated entropy allows, or a pattern repeating too often. They cannot certify randomness, for the reason the sticky source makes plain — a stream can pass a frequency test and still be predictable — but they can catch a source that has failed outright, such as an oscillator that has locked to the sampling clock and begun emitting the same pattern for ever.

At the top is conditioning, which is extraction by another name. Von Neumann’s rule is sometimes used here, precisely because it needs no estimate of the bias; more often the raw bits are fed through a cryptographic hash function or a block cipher, which acts as a seeded extractor whose seed is fixed in the design. The standards that govern such generators require the designer to estimate the source’s entropy per sample and to feed the conditioner at least as much entropy as it is asked to output — the ceiling from the third figure, turned into a rule of engineering. Everything above the conditioner is a deterministic generator seeded by its output, and every guarantee it offers is conditional on that seed having been as unpredictable as the estimate claimed.

What the pictures cannot show #

Where the entropy is. Every figure uses a source whose structure is known — a coin of stated bias, a chain of stated stickiness — and computes its entropy from the formula. A real source comes with no formula, and estimating how much unpredictability it contains is the hard practical problem: a sequence can pass every frequency test and still be the output of a predictable process, as the recoverable generators showed from the other side.

Independence. The measured correlations in the fourth figure test one kind of dependence — between output bits a few places apart — and find it or fail to. An output that passes that test may still be dependent in some other way, and no finite set of measurements can establish independence. The claim that von Neumann’s output is independent for an independent source is a proof; the figure only fails to contradict it.

The adversary. The Santha–Vazirani theorem is about a source chosen after the function, to defeat it, and no figure depicts such an adversary. The copied-flips source in the last figure is the simplest possible illustration of a function defeated by a source’s structure, not a construction of the adversary the theorem guarantees for every function.

Still open: two weak sources, and how weak they may be #

Two-source extraction is where the frontier is. The question is how little unpredictability two independent sources may carry and still be combined, by an explicit formula, into nearly fair bits. Chor and Goldreich gave a construction in 1988 that needs each source to be more than half unpredictable; for nearly thirty years nobody could go much below one half. Chattopadhyay and Zuckerman broke through in 2016, with sources whose unpredictability can be as small as a polylogarithmic amount in their length, and subsequent work has pushed the requirement lower still — but explicit constructions matching what a random choice of function achieves are not known.

The practical question is just as open in its own way. Operating systems pool bits from many physical sources into a buffer, estimate the entropy that has gone in, and hand out seeds when the estimate is high enough. The estimates are heuristic. The step after this one is the generator that consumes those seeds — a twenty-thousand-bit linear state whose outputs are then passed through a final filter, tempering, that improves how evenly they spread without changing anything else about them.

A symmetry, a ceiling and an assumption #

Von Neumann’s rule turns a biased coin into a fair one by a symmetry: $01$ and $10$ are equally likely because the two probabilities are the same product in a different order. The symmetry needs no knowledge of the bias, which is why the rule is still taught and still used.

Its waste can be measured against a ceiling, the source’s entropy, and recycling the discarded pairs climbs to that ceiling without ever learning the bias either. What neither the rule nor its recycling can do is supply the assumption they rest on. They need the flips to be independent, and when the flips remember one another the output is balanced and still predictable — a warning that the property a simple test measures is not the property that matters.