Birthdays spaced too evenly

The planes a recurrence cannot leave showed that the successive outputs of a linear congruential generator, taken in pairs or triples, lie on a small family of parallel lines or planes, and the test that ranks the generators turned the distance between those planes into a single computable number. Both essays look at the structure directly: they know the multiplier and they solve for the lattice. A statistical test does not know the multiplier. It is handed a stream of numbers and asked whether they behave like independent uniform draws, and the question this essay asks is how many numbers it needs before a linear generator gives itself away.

For one particular test the answer turns out to be strikingly small, and it has a clean form. George Marsaglia’s birthday spacings test, part of the battery he published in the 1990s, catches a linear congruential generator with $m$ states once its sample reaches roughly five times $m^{1/3}$. For a 32-bit generator that is about eight thousand outputs; for a 64-bit generator, about thirteen million — a fraction of a second of computation. Other tests need samples comparable to $\sqrt{m}$, or to $m$ itself. The cube root comes from the test’s design, and the failure comes from the lattice, as the computations below show by running the same states through a scrambling step that leaves the period unchanged and makes the failure disappear.

The test counts coincidences among the gaps #

The birthday problem, in its classical form, asks how many people must be in a room before two of them share a birthday; fourteen people within a day worked through the answer, 23 for a 365-day year, and the near-miss versions of it. Marsaglia’s test asks a second-order question about the same room. Take $n$ birthdays in a year of $k$ days, sort them, and look at the $n - 1$ gaps between consecutive birthdays. Count how many of those gaps are equal to some other gap. Formally, sort the gaps too and count the positions at which a gap equals the one before it; that number, written $Y$ here, is the test statistic.

For independent uniform birthdays $Y$ has, to a good approximation, a Poisson distribution with mean

$$\lambda = \frac{n^3}{4k}.$$

The reasoning is a birthday argument one level up. With $n$ points in $k$ cells, a typical gap is about $k/n$ cells long, and two gaps drawn independently from a spread of that width coincide with probability about $n/2k$. There are roughly $n^2/2$ pairs of gaps, so the expected number of coincident pairs is about $n^3/4k$, and when that number is small the coincidences are nearly independent rare events, which is the situation the Poisson law describes. The constant is not exact for small samples — the gaps are not independent, since they must add up to the span of the sample — but the approximation is good at the sizes used in practice.

The test is run with $n$ and $k$ chosen to make $\lambda$ a small fixed number. Marsaglia’s own version put 512 birthdays in a year of $2^{24}$ days, which gives $\lambda = 2$, and that is the value used throughout this essay. A count of seven or more then has probability under half a percent; a count of twenty is effectively impossible.

The small sample above is drawn to be legible rather than representative, but the arithmetic is the same at every size. Sixteen points in 512 cells give $\lambda = 16^3 / (4 \cdot 512) = 2$, and this sample has exactly two repeated gaps, a gap of 2 and a gap of 8 each occurring twice. A generator under test produces a few thousand such samples at a few thousand points each; the counts are compared with the Poisson law, and either their distribution matches or it does not.

Where a generator’s numbers go in the grid #

To feed a generator to the test, its outputs have to become birthdays. The natural way, and the one that makes the test strong, is to take successive outputs in groups of $t$, cut each to its top $B$ bits, and treat the group as one cell in a $t$-dimensional grid of $k = 2^{tB}$ cells, read off in a fixed order. With $t = 2$ a pair of outputs $(u, v)$ becomes the cell $u \cdot 2^B + v$: row $u$, column $v$ of a square grid, with the rows laid end to end. Only the top bits of each output are used, which matters, since the low bits of a generator modulo a power of two are known to be weak and a test that relied on them would prove nothing new.

Consider what this does to a linear congruential generator, $x \mapsto ax + 1$ modulo $m = 2^e$. A pair of successive states is $(x, ax + 1 \bmod m)$, and as $x$ runs over all $m$ states those pairs form a translate of a lattice in the $m \times m$ square — the lattice that the earlier essays studied. Cutting each coordinate to $B$ bits shrinks the square to a $2^B \times 2^B$ grid and maps every lattice point to the cell containing it. However the generator is started and however long it runs, it can only ever reach those cells.

The figure at the top of this essay draws exactly this map for a toy generator with $m = 256$ states and multiplier $a = 229$, a multiplier chosen as the best of its size by the two-dimensional spectral test. Cut to six bits, the outputs fall into a $64 \times 64$ grid of 4,096 cells, sixteen times as many cells as the generator has states. The reachable cells are, unmistakably, a tilted lattice: 256 of them, evenly spread, with the regularity the spectral test measures.

Beside it is the same recurrence with one change. Before each state is read, it is passed through a fixed scrambling bijection — three rounds of a shift-and-exclusive-or followed by multiplication by an odd constant, an invertible map on eight-bit words. The sequence of states is identical, the period is identical, and the number of reachable cells can be no larger; it is 252, slightly fewer, because a few scrambled pairs land in the same cell. What has changed is where those cells are, and they are now scattered with no visible order.

A lattice offers only a few gap lengths #

The test does not look at the grid as a picture. It sees the cell numbers as points on one long line of $k$ positions and asks about the gaps between neighbours. So the question about the two panels of the hero figure is how many different gaps occur between consecutive reachable cells in reading order. For the lattice the answer is ten. For the scrambled cells it is forty-six.

That difference widens rapidly with size, and it is the whole mechanism of the failure.

Read directly, the generator with $2^{16}$ states never offers more than 33 different gap lengths between its reachable cells, on any grid from $2^{14}$ to $2^{24}$ cells. Scrambled, the same states offer more than a thousand once the grid is fine. A sample of $n$ points drawn from the reachable cells has $n - 1$ gaps, each of which is a sum of consecutive gaps between reachable cells; when the reachable cells are sparse compared with the sample, most sample gaps cover only a few of them, and if those come from a short list then the sample gaps are drawn from a short list too. Repeats are then forced, the way two of fourteen people must share a birthday in a year of thirteen days. It is the same lever that four lists find a collision sooner pulled in the other direction: there, structure among the candidates made coincidences cheaper to find on purpose; here, structure among the outputs makes them appear unbidden.

Why a lattice offers so few lengths can be seen one row at a time. In row $u$ of the grid the first output of each pair is fixed to its top $B$ bits, so the states in that row are a run of consecutive integers $x, x + 1, x + 2, \dots$; their successors are $ax + 1, ax + 1 + a, ax + 1 + 2a, \dots$ modulo $m$, which are the points of a rotation of a circle by the angle $a/m$. Three gaps and no more proved the theorem that governs such points: however many multiples of an angle are marked round a circle, the gaps between neighbours take at most three different lengths. Cutting to cells blurs each of the three lengths by at most one cell, and the computation confirms that within a single row of the $2^{20}$-cell grid the reachable cells have at most four different gaps. The rows are themselves related to each other by the same rotation, and the overall count stays in the tens.

The scrambling destroys exactly this. The scrambled successor of a run of consecutive states is not a run of multiples of anything, and the reachable cells look, to every test considered here, like a random subset of the grid.

The count leaves its law when the cells outnumber the states #

The prediction is then sharp. While the grid has fewer cells than the generator has states, the reachable cells cover the grid many times over, and a lattice that dense is indistinguishable from uniform at the resolution of the cells. Once the grid has more cells than the generator has states, the reachable set is a sparse lattice, its gaps come from a short list, and repeats among the sample gaps should run far above $\lambda$.

That is what happens, and the change is abrupt. The generator here has $m = 2^{20}$ states and a multiplier whose two-dimensional figure of merit is 0.996, as good as any multiplier of its size. With pairs cut to between four and fifteen bits, the grid runs from $m/256$ to $1{,}024\,m$ cells, and at each size the sample is chosen to keep $\lambda = 2$. Read directly, the mean count sits near 2 as long as $k \le m$. At $k = 4m$ it is 4.5; at $16m$ it is 16.9; at $1{,}024\,m$ it is 774, from samples of a few thousand points, almost every gap a repeat. Scrambled, the mean count stays between 1.8 and 2.3 across the whole range.

The scrambled curve is what rules out the obvious explanation. A generator with $m$ states can reach at most $m$ cells, so on a grid of $16m$ cells fifteen-sixteenths of the grid is unreachable for both versions; if the test were detecting that — the period, or the finite state — it would catch both. That kind of failure exists, and it is a different one: square it and keep the middle found von Neumann’s generator repeating a value within a third of what the birthday bound allows, which is a statement about the period, and no scrambling of the output would have hidden it. It catches only the one whose reachable cells form a lattice.

One detail in the curve is worth recording because it runs the other way. Just before the cliff, at $k = m/4$ and $k = m$, the generator read directly repeats fewer gaps than random points do: a mean of 1.5 or so against 2, measured over 3,000 runs at 1.55 and 1.73 against random points’ 1.91 and 1.99 at the same sizes. At that scale the lattice spreads the sample slightly too evenly to produce the coincidences chance would. The deficit is real but small, and a test looking only at the upper tail does not see it.

The distribution, run by run #

The mean is a summary; the test itself compares the whole distribution of counts with the Poisson law, and the separation is total.

On a grid of $m/16$ cells the generator’s counts match random points’ to within the sampling noise of 1,500 runs — 5.7% in total variation against 3.0% for random points themselves, with the small extra difference the deficit described above. On a grid of $16m$ cells, with samples of 512 points, the generator averages 17.3 repeats, and 99.9% of its runs reach seven, a count that random points reach about once in 220 runs. One run is enough to reject it; a battery that runs the test a few dozen times rejects it with a $p$-value too small to print.

This is also the regime Marsaglia’s own parameters probe. His 512 birthdays in a year of $2^{24}$ days is precisely the $k = 16m$ test for a generator with $2^{20}$ states, and so any linear congruential generator with a period of about a million or less, read in pairs, fails the original test at its original settings.

The sample grows as the cube root of the period #

Since the failure begins when the grid has about as many cells as the generator has states, and the sample size is tied to the grid by $\lambda = n^3/4k$, the sample at which a generator is caught follows at once. At $k = 16m$ and $\lambda = 2$,

$$n = (4 \lambda k)^{1/3} = (128\, m)^{1/3} \approx 5.04\, m^{1/3}.$$

The cube root is not a property of the generator; it is the price of keeping $\lambda$ fixed while the grid grows. What the generator contributes is the location of the cliff, at $k \approx m$, and the cliff’s location does not move with the period.

The measurement confirms it across ten periods from $2^{12}$ to $2^{30}$, each with a multiplier picked as the best of four thousand candidates by the two-dimensional spectral test, all with a figure of merit above 0.97. At $k = 16m$ every period’s generator is rejected by one run in at least 98% of runs, and in 100% from $2^{14}$ upwards. The sample sizes run from 81 points for $2^{12}$ states to 5,161 for $2^{30}$, every one within half a percent of $(128\,m)^{1/3}$.

Two other lines on the figure show what this is being compared with. A generator that outputs its whole state never repeats an output until it has been through its full period $m$, and a random sequence of values from $m$ possibilities repeats one after about $\sqrt{\pi m/2}$ draws — the classical birthday bound. A test counting repeated outputs therefore catches a full-state generator at about $\sqrt{m}$, by the absence of repeats; but that test is defeated by the simplest precaution, discarding the low half of each output, which most practical generators do. The spacings test reads only the top bits by design, and needs only the cube root.

The extrapolation is unforgiving. A generator with 32 bits of state is caught by about 8,200 outputs. One with 64 bits is caught by about thirteen million, a fraction of a second on a laptop, provided the test reads pairs of 34-bit values from each 64-bit output. A 128-bit state takes about $3.5 \times 10^{13}$ outputs, which is large but no longer out of reach of a dedicated computation.

Fewer bits of each output, the same threshold #

Pairs are not special. With triples of outputs, a grid of $k$ cells needs only $\tfrac13 \log_2 k$ bits from each output, and with quadruples a quarter; the reachable set is still a lattice image, and its cells still offer few gaps.

For a generator with $2^{24}$ states the cliff sits at $k \approx m$ in every case. At $k = m$ a pair reads 12 bits of each output, a triple 8 and a quadruple 6. Beyond the cliff the climb is a little slower in higher dimension — at $k = 2^6 m$ the mean is 79 for pairs and 23 for triples — so the constant in front of $m^{1/3}$ grows slowly with $t$; but the threshold is where the cells outnumber the states, and the catching sample is still a few times $m^{1/3}$.

The trade is what makes the test so effective in practice. A generator that hides its low bits, or outputs only a slice of its state, still has every output determined by a lattice point, and grouping more outputs lets the test reach the cliff while reading fewer bits of each. Truncating outputs does not delay the failure; it only changes which grouping catches it first.

What scrambling buys, and what it does not #

The scrambled generator in every figure here is the same recurrence with an invertible map applied to each state before it is read, and it passes every version of the test computed: pairs on grids up to $1{,}024\,m$ cells, all the way out where the plain generator averages 774 repeats. That is the design behind the generators of the PCG family. A rotation that hides the lattice looked at one of them, which keeps a linear congruential generator’s state exactly as it is and shows only a few bits of each state, rotated by an amount the state’s top bits choose. The output function is cheap, and what it removes is precisely the lattice structure this test detects.

What it does not remove is the finite state. The scrambled generator still has $m$ states and reaches at most $m$ cells of any grid. It passes here because the reachable cells, though few, are spread with no arithmetic regularity; a test that could find which $m$ cells are reachable would still separate it from random. And it does not remove predictability: recovering the rule from four outputs solved the plain generator from a few of them, and a fixed, public scrambling function only adds a step to that solution. The same distinction runs through a grid of bits whose rank stops at the state, where a generator built from shifts and exclusive-ors is caught by a test sized to its state rather than to its period. Statistical quality and unpredictability remain different properties, as they were for the nineteen thousand bits of state of the Mersenne twister.

What the computations show and assume #

Every count in this essay is measured, not estimated from a formula. The reachable-cell censuses in the hero figure and the gap figure enumerate every state of the generator. The repeat counts come from independent runs of the test, each started at a uniformly chosen state, with the random points drawn from a separate counter-based generator whose state is far larger than any grid used. The numbers of runs — 60 to 3,000 — are stated beside each figure; the means for the plain generator past the cliff are so far from 2 that run-to-run noise is irrelevant, while the means near the cliff, and the deficit before it, carry noise of a few hundredths.

What the computations assume is a particular way of turning outputs into birthdays: groups of $t$ successive outputs, top bits, rows laid end to end. Other conventions exist — L’Ecuyer and Simard, who worked out how the test interacts with linear generators and included it in their TestU01 library, studied several — and they move the constant in front of $m^{1/3}$ without moving the exponent. The multipliers were chosen to be as good as possible by the spectral test, so that the failure cannot be blamed on a careless choice; a careless choice would only blur the comparison. The scrambling function is one fixed example, not a recommendation, and its success here says only that the spacings test cannot see it.

Still open: which tests a lattice cannot hide from #

The birthday spacings test catches every linear congruential generator at a sample of order $m^{1/3}$, and the reason is structural: once the grid has more cells than the generator has states, the reachable cells form a lattice image with few gap lengths. Several things around that statement are not settled.

What is the smallest sample at which any feasible test distinguishes a linear generator from random? The spectral test needs no sample at all once the multiplier is known, and recovering the rule from four outputs showed how to recover the multiplier from a handful of outputs, so against an adversary who suspects linearity the answer is tiny. Against a generic statistical test that does not know what it is looking for, $m^{1/3}$ is the best known scale for the spacings family, and whether some other generic test reaches a linear generator at a smaller power of $m$ is not known.

What exactly does the deficit before the cliff measure? Just below $k = m$ the plain generator repeats gaps between an eighth and a fifth less often than chance in the runs measured here. The excess above the cliff is explained by the few gap lengths; the deficit below it presumably reflects the lattice’s evenness at a scale where its cells are still shared, but no calculation here predicts its size, and a two-sided test built on it would catch the generator at a smaller sample than the upper tail does, if its size could be pinned down.

And for the scrambled generators the question is the same one the rotated outputs left: no theorem says which statistical tests a given output function defeats, and each is checked against batteries one test at a time.

A lattice has a short list of gaps #

The birthday spacings test counts how many of the gaps between sorted random points repeat, and expects about $n^3/4k$. A linear congruential generator with $m$ states, read as pairs or triples of top bits, matches that law exactly as long as the grid has fewer cells than it has states. Past that point its reachable cells are the image of a lattice, which by the three-distance theorem offers only a handful of gap lengths, and the count runs far above its law: from 2 to 17 at sixteen times as many cells, to 774 at a thousand times. The sample that catches it is $(128\,m)^{1/3}$, about five times the cube root of the period, for every period measured from $2^{12}$ to $2^{30}$ and for multipliers as good as the spectral test can select. The same states scrambled before they are read pass the test at every size — so what the test detects is not the period but the lattice.