Two weak sources make one fair bit

Von Neumann’s trick turns a biased coin into fair bits by reading its flips in pairs, and it needs only one assumption: that the flips are independent. Real sources of randomness — the timing of keystrokes, the noise in a sensor, the jitter of a clock — do not satisfy it. Their bits are correlated with one another in ways nobody can write down, and the most that can honestly be said about them is a lower bound on how unpredictable they are: that no outcome is more likely than, say, one in $2^{k}$ for strings of $n$ bits. That quantity, $k$, is the source’s min-entropy, and a source with $k$ near $n$ is nearly uniform while one with $k$ much less than $n$ is badly defective.

This is a different problem from the one the rest of this subject has been about. A linear generator and the twister stretch a short seed into a long sequence that looks random; a cryptographic generator does the same with a guarantee that nobody can tell the difference. All of them need a seed that is genuinely unpredictable to begin with, and the seed has to come from the physical world, defects and all. Turning a defective physical source into a few truly fair bits — extraction — is the step before any of them runs, and it is the one that cannot be done by cleverness alone.

The essay on fair bits ended with the fact that for such sources no single function works. This essay is about what does: two independent sources, combined by a rule so simple that its success looks accidental — and is not.

Why one source is never enough #

The obstruction is a counting argument, a pigeonhole principle with two boxes. Take any rule $f$ that turns an $n$-bit string into one bit. One of its two outputs is produced by at least half of all strings — at least $2^{n-1}$ of them. A source that is uniform on those strings has min-entropy at least $n - 1$, almost as unpredictable as a string can be, and yet $f$ gives the same bit on every one of its outputs. So for every fixed rule there is a nearly perfect source that the rule turns into a constant.

The defect is not in any particular rule; it is that a single source, however unpredictable, can be arranged against the rule after the rule is fixed. The same thing is visible in the simplest rule of all, exclusive-or.

XOR of many independent biased bits is nearly fair — each further XOR multiplies the distance from one half by the same factor, 0.6 for this coin. But XOR of dependent bits can be anything: a source whose bits are copies of one flip has a lot of min-entropy per block if the flip is fair, and its XOR tells the copying and not the flip. A rule that relies on independence within a source fails as soon as the source is correlated.

The rule for two sources #

Take two sources, independent of each other, each producing $n$-bit strings $x$ and $y$. Output

$$\langle x, y \rangle = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n \pmod 2,$$

the parity of the number of positions where both strings have a 1. Benny Chor and Oded Goldreich showed in 1988 that if the two sources’ min-entropies add up to more than $n$, this bit is nearly unbiased, with a bias that shrinks exponentially in the excess. Nothing is assumed about either source beyond its min-entropy and the independence of the two.

The whole argument lives in one picture.

Write the output as $\pm1$ instead of $0/1$, and lay all possible pairs $(x, y)$ in a table, $2^n$ rows by $2^n$ columns, entry $(-1)^{\langle x, y\rangle}$. A source for $x$ that is uniform on a set $A$ of strings picks a row from $A$; a source for $y$ uniform on $B$ picks a column from $B$. The output’s bias is the imbalance of the rectangle $A \times B$: the number of $+1$ entries minus the number of $-1$ entries, divided by twice its size. In the figure the rectangle of 210 entries has 109 of one sign and 101 of the other, so the output is fair to within two percent.

The rectangle that does not cancel #

Not every rectangle is balanced, and the exceptions show exactly how much entropy the sources need.

If $x$ only ever uses the first half of the positions and $y$ only the second half, their inner product is always zero, and the output is constant. Each source can have min-entropy up to $n/2$ this way — half of all possible unpredictability — and together they carry exactly $n$ bits, not more. So the condition “together more than $n$” cannot be weakened: at exactly $n$, arranged adversarially, the rule fails completely.

This is the two-source version of the one-source obstruction. A single source can be aligned against any fixed rule; two sources, each constrained only by min-entropy, can be aligned against each other, and the inner product is defeated precisely when their alignment is perfect. Min-entropy above $n$ in total makes perfect alignment impossible.

The block example is the only way to fail completely, but it is not the only way to fail partly. Sources uniform on two subspaces that are nearly perpendicular — whose inner products vanish on most pairs — give a rectangle that is mostly one sign, and the output is biased without being constant. Lindsey’s lemma, below, is the statement that no arrangement of sets does much better than the perpendicular subspaces at unbalancing the table: the extreme case is the linear one.

Lindsey’s lemma #

The theorem behind the picture is a statement about the table alone.

Lindsey’s lemma: for any sets $A$ and $B$ of rows and columns of the $N \times N$ table, $N = 2^n$, the rectangle’s sum satisfies

$$\left| \sum_{a \in A,\, b \in B} (-1)^{\langle a, b \rangle} \right| \le \sqrt{|A|\,|B|\,N}.$$

The proof is one application of the Cauchy–Schwarz inequality, using the fact that the rows of the table are orthogonal: any two distinct rows agree in exactly half their entries, which is the fact that makes the table a Hadamard matrix and its rows the codewords of a code with the largest possible distances. A rectangle’s sum is the inner product of a combination of rows with a combination of columns, and orthogonality stops the rows from reinforcing each other.

Divide by $2|A||B|$ and the bias of the output is at most $\tfrac12\sqrt{N/(|A||B|)}$. A source of min-entropy $k_1$ can be taken to be uniform on a set of size $2^{k_1}$ — more general sources are mixtures of those, and a mixture cannot be more biased than its worst component — so the bias is at most $\tfrac12 \cdot 2^{(n - k_1 - k_2)/2}$. When $k_1 + k_2$ exceeds $n$, that is less than one half, and every further bit halves it by a factor of $\sqrt2$.

The dots are sources built from blocks of coordinates — $x$ using the first $k$ positions and $y$ the last $k$ — which overlap in $2k - n$ positions once $k$ passes $n/2$, and then the inner product is a parity of that many independent fair bits’ products, with bias exactly $\tfrac12 \cdot 2^{-(2k - n)}$. They sit below the general bound, which also covers every unstructured source, and they show that the bound’s threshold at $n/2$ is real.

Defective sources, simulated #

The theorem is about the worst case; the practical point is that it asks so little of the sources.

The sticky source has strong correlations between neighbouring bits and a bias at the start; the lumpy source is sparse, most of its bits zero. Neither is anywhere near uniform, and simple rules inherit their defects: the sticky source’s first bit is 1 almost seven times in ten, and XORing it with the lumpy source’s first bit barely helps, because that bit is usually 0. The inner product of the whole blocks is within two percentage points of fair. It uses nothing about how either source is defective, only that the two are independent and that between them there is enough unpredictability.

The remaining 1.7 percentage points of bias are what the bound allows for these sources. Each 16-bit block of the sticky source has far less than 16 bits of min-entropy — its likeliest block, all ones, occurs about one time in forty, so it carries only about five and a half bits — and the lumpy source’s likeliest blocks, those with a single 1, each occur one time in sixty-four, which is six bits. Their sum is below the sixteen the theorem asks for, so no guarantee applies, and the rule still does well: the worst case is rare, and these sources are not arranged against each other.

Why independence is the whole assumption #

Everything above leans on one assumption, that the two sources are independent, and it is worth seeing how completely the rule fails without it. If the second source simply copies the first, $y = x$, then $\langle x, x \rangle$ is the parity of the number of 1s in $x$ — a single fixed function of one source, and so defeated by a single source arranged against it, as the counting argument showed. A partial dependence gives a partial failure: the rectangle picture no longer applies, because the pair $(x, y)$ is no longer uniform on a product $A \times B$ but on some set that can be shaped to follow the table’s signs.

So independence is not a technical convenience. It is what turns the adversary’s single choice — a source aligned against the rule — into two choices that must be made separately, neither knowing the other. The table’s balance on rectangles is exactly the statement that two separate choices cannot coordinate to find a region of one sign. In practice that is also the assumption hardest to certify, because physical sources that look unrelated often share a hidden cause.

More than one bit #

A single fair bit is rarely enough; a seed is hundreds of bits. The inner product generalises. Treat each $n$-bit string as an element of the field with $2^n$ elements, multiply $x$ by $y$ there, and keep several bits of the product instead of one. Each output bit is an inner product of $x$ with a string that depends linearly on $y$, and the same rectangle argument, applied to every combination of output bits at once, shows that the output is close to uniform on all its bits together, provided the sources carry enough more than $n$ bits between them. The price is that each extra output bit costs some of the excess entropy, so the number of fair bits extracted is limited by how far above $n$ the sources are. Two sources of 1,000 bits each with 600 bits of min-entropy carry 200 bits more than the length, and a multiplication in the field of $2^{1000}$ elements can extract dozens of nearly fair bits from them — enough to seed any generator in this collection, with the error in each bit smaller than anything that could ever be measured.

Two sources and a colouring nobody can draw #

The two-source problem has a twin in combinatorics that makes its difficulty vivid. A function $f(x, y)$ of two $n$-bit strings is a colouring of the edges of a complete bipartite graph with $2^n$ vertices on each side. A good two-source extractor for min-entropy $k$ says that every $2^k \times 2^k$ rectangle — every complete bipartite subgraph of that size — contains edges of both colours, in nearly equal numbers. That is a bipartite Ramsey graph: a colouring with no large monochromatic rectangle.

The finite version of the question is the one six people at a party began: how large can a colouring be with no large one-coloured structure? Random colourings have this property for $k$ as small as about $\log n$ — Erdős’s counting argument — and nobody can write one down. The inner product is an explicit colouring that works for $k$ just above $n/2$, and for decades that was the best any explicit construction could do. Jean Bourgain pushed the threshold slightly below one half in 2005. In 2016 Eshan Chattopadhyay and David Zuckerman constructed explicit two-source extractors for min-entropy polylogarithmic in $n$, and with them explicit Ramsey graphs far better than any known before — the same problem, solved from the randomness side, with tools from pseudorandomness that no graph theorist had used.

What the figures establish #

Every rectangle sum is exact. The tables have 32 or 64 rows, the sums are whole numbers computed entry by entry, and every one is checked against Lindsey’s bound. The bound itself is a theorem; the 599 random rectangles are a check that it is never violated, not a proof that it never is.

Sources uniform on sets stand in for all sources. The figures use sources that are uniform on a set of strings. A general source of min-entropy $k$ is a mixture of such flat sources, and a mixture’s bias is at most the largest bias among its components, so the flat case is the worst case — a standard reduction the figures assume rather than show.

The simulation measures a share, not a bias bound. Twenty thousand blocks give a share of 1s accurate to about a third of a percentage point, so the 48.3% is distinguishable from 50% and the difference is real. It is a property of these two sources, not a guarantee about others.

The simulated sources are two examples. The sticky and lumpy sources were chosen to be defective in ways that defeat simple rules, and the inner product handles both. That is illustration; the theorem is what guarantees it for every pair with enough min-entropy.

Still open: how little entropy two sources need #

Random functions are excellent two-source extractors down to min-entropy about $\log n$. Explicit ones — rules anyone can write down and compute quickly — now work down to min-entropy polylogarithmic in $n$, after the breakthrough of 2016 and a series of improvements since, but the output they give has only constant error, not the exponentially small error the inner product achieves in its range, and they extract only one or a few bits rather than many. An explicit two-source extractor matching what random functions achieve — logarithmic min-entropy, tiny error, many output bits — is not known, and constructing one would, by the Ramsey connection, also give explicit Ramsey graphs as good as random ones, a problem open since Erdős posed it in 1947.

There is also the question of independence, which every theorem here assumes and no physical system guarantees. Two noise sources on one chip share a power supply and a temperature. Extractors for sources that are only approximately independent, or for many sources of which some unknown few are adversarial, are an active area, and the models themselves — what kind of weak independence real hardware provides — are still being argued.

Randomness from two directions #

A single weak source can always be defeated by a rule fixed in advance, because the source can be chosen afterwards. Two independent weak sources cannot both be aligned against the inner product unless they have too little unpredictability between them, and Lindsey’s lemma says exactly how much is too little: half the length each, $n$ in all. Above that, the parity of the bitwise product is nearly fair, and the table of those parities — a pattern of pluses and minuses that is balanced on every large rectangle — is what does it. The same table is a colouring with no large one-coloured rectangle, which is why the best random-number extractors and the best explicit Ramsey graphs have turned out to be the same objects, found from two different sides.

It is also the end of the line this subject has been following. Linear generators were fast and predictable; the twister was fast, long-periodic and still linear; cryptographic generators bought unpredictability with an assumption about hard problems. All of them began from a seed. Extraction is where the seed comes from, and it is the one step at which no generator, however clever, can substitute for a physical source — only combine two of them in a way that no defect in either can defeat.