Three hundred thousand outputs of nearly nothing

A grid of bits whose rank stops at the state found the price of linearity in a generator’s output: fill a grid with bits from a generator built of shifts and exclusive-ors, and its rank over the two-element field stops at the size of the generator’s state, with certainty, however good the generator otherwise is. That essay looked at the generators in their steady running, far from their starting point. This one looks at the start, and finds a second price of the same linearity, visible to anyone and needing no linear algebra to detect.

A linear generator’s update is a matrix over the two-element field applied to its state. The all-zero state is therefore fixed — the matrix carries nought to nought — and the generator must never be started there. A state with a single 1 is not fixed, and the generator runs from it through its full period like from any other non-zero state. But a matrix built from a few shifts and exclusive-ors carries a state with few 1s to a state with few 1s, and the output, a linear function of the state, is mostly zeros until the 1s have had time to spread. The region around the zero state where that happens has a name, from François Panneton, Pierre L’Ecuyer and Makoto Matsumoto’s paper of 2006: zeroland. The figures here measure how long four generators take to escape it, and why the most widely used of them, the Mersenne twister, takes longest by far.

Four generators from one bit #

The four generators span a range of designs. xorshift128, George Marsaglia’s of 2003, keeps four 32-bit words and makes each new word from two old ones with three shifts. WELL512, from Panneton, L’Ecuyer and Matsumoto, keeps sixteen words and mixes four of them at every step with shifts and masks chosen to spread changes quickly. TT800, Matsumoto and Yoshiharu Kurita’s twisted generator of 1994, keeps twenty-five words. MT19937, Matsumoto and Takuji Nishimura’s Mersenne twister of 1998 and the default generator of a great many programming languages, keeps 624 words, and nineteen thousand bits of state explained what it buys with them: a period of $2^{19937} - 1$ and output that is equidistributed in 623 dimensions.

Each recurrence was implemented from its publication and, for the twister, checked against the outputs that its reference code and the C++ standard require for the seed 5489: the first output is 3,499,211,612 and the ten-thousandth 4,123,659,995. Then each was started sixty-four times, from states with a single 1 at sixty-four different places, and the share of 1s in its output was averaged over the starts. A good source’s output is half 1s from the first bit; these start near nought and climb. The smaller generators climb almost at once: xorshift128’s average share passes $0.45$ after 37 outputs and WELL512’s after 44. TT800 takes 4,500. The twister takes about 374,000 by this measure, and its curve sits near nought for the first ten thousand outputs.

How a lone 1 spreads #

The twister’s slowness is a property of its recurrence, and its own state shows it directly. The next figure counts the 1s among the twister’s 19,937 state bits after each twist — the operation that rewrites all 624 words, and that is followed by 624 outputs.

Each new word of the twister is built from three old ones: word $k$ is replaced by word $k + 397$, exclusive-ored with a shifted combination of the top bit of word $k$ and the low 31 bits of word $k + 1$, plus a fixed constant when the lowest of those bits is 1. A 1 can therefore move to at most a few new places per word per twist, and most of the twist’s work is copying zeros onto zeros. After one twist the three single-bit starts in the figure hold 2 to 4 ones; after ten twists, 13 to 15; after twenty, about 20. The growth then accelerates as the 1s begin to interact — about 300 after fifty twists, about 850 after a hundred, about 2,500 after two hundred — and the state reaches half its bits, the density of a random state, only after six to eight hundred twists. In outputs, that is three to five hundred thousand.

The other generators spread faster for one of two reasons. xorshift128 is tiny: its state is 128 bits, so even a slow spread reaches everything quickly. WELL512 is designed to spread: each step combines four words, each through a shift or a mask that moves bits across the word, and a single 1 reaches every word of its 512-bit state within a few dozen steps. Panneton, L’Ecuyer and Matsumoto made that their design goal, and their larger generators, with states as big as the twister’s, escape zeroland far faster than the twister does.

What the output looks like on the way out #

The share of 1s is an average. The output itself, drawn bit by bit, shows how the escape proceeds.

The first 48 outputs are entirely blank. After a hundred thousand outputs the 1s come in bands: rows that look random alternate with rows that are nearly empty, because the twister’s outputs are its state words in order, and by then the spreading has reached some regions of the state and not others. After two hundred and fifty thousand the bands are wider and still separated by nearly blank rows. After four hundred thousand the panel is indistinguishable from noise. A program that drew random numbers from a twister started this way would get, for its first hundred thousand draws, numbers that are mostly zero, then numbers that are random in some draws and zero in others — no test is needed to see the problem, only a glance.

Where the 1 starts barely matters #

The single 1 could be placed anywhere in the state, and one might expect a 1 placed near the words the twist reads first to escape sooner. The next figure measures the escape time — the number of outputs before the share of 1s in the latest thousand outputs reaches 0.45 — for two hundred starting positions spread through the state.

Every start escapes between 332,231 and 370,486 outputs, with median 343,029, and the times fall into two narrow bands rather than spreading out. Where the 1 begins hardly matters, because each twist sweeps through the whole state, so a 1 anywhere is carried through every word within a twist or two, and the escape is then set by how many twists the recurrence needs to multiply the 1s. The two bands are a detail of the twist’s structure that the figure records without explaining; the gap between them, about twenty-five thousand outputs, is some forty twists.

This figure also explains why the hero’s averaged curve reaches 0.45 later, at about 374,000. Averaging the share over sixty-four starts and then asking when the average reaches 0.45 waits for the slower band, which is what an average of curves does when a minority of them rise later. Both measures say the same thing: the twister spends roughly a third of a million outputs in zeroland from any single-bit start.

Escape against the size of the state #

The four generators have state sizes from 128 bits to 19,937, and one could suspect that the twister is slow merely because it is large. The next figure separates size from design.

The dashed line is the least time in which a change could reach every word of the state, one output per word. xorshift128 and WELL512 escape within ten times that bound. TT800, with twenty-five words, takes 4,500 outputs, about 180 times its size; the twister, with 624 words, takes about 374,000, about 600 times its size. The difference is the twist. Both TT800 and the twister build each new word from only three old ones, and of one of those three they use only a single bit. The twister keeps most of its state for the sake of the period and the equidistribution, and pays for it in mixing speed. A large state needs no more than a large number of taps to escape quickly, and the WELL family showed that the extra taps cost almost nothing in speed.

Zeroland is a stretch of one long cycle #

It would be wrong to picture zeroland as a trap the generator falls into. A linear generator with a primitive characteristic polynomial passes through every non-zero state in a single cycle, which is the property the planes a recurrence cannot leave and every element is a power of one traced to finite fields: the twister’s period, $2^{19937} - 1$, is the number of non-zero states, all visited in turn. The single-bit states are on that cycle like any others. Somewhere in the twister’s period there is a stretch where it passes through a single-bit state, and the third of a million outputs that follow are the sparse ones measured here; everywhere else the output is as good as the twister ever is.

So zeroland is a short stretch of an enormous cycle, and a start chosen at random lands in it with a chance so small it has no practical meaning. The states within a few hundred thousand steps of a single-bit state number about $19{,}937 \times 400{,}000$, a little under $10^{10}$, out of about $10^{6001}$. The danger is not chance but choice: a state set by hand, by a short seed copied into a long array, or by a bug that zeroes most of the state, is exactly the kind of state that lies in zeroland, and none of those is a random start. Four outputs that give away the whole rule made the same point about guessing a generator’s rule from a few outputs: the trouble with a deterministic generator is always in the states that a person, rather than chance, is likely to produce.

The oldest test catches it #

The measure used throughout, the share of 1s in a block of output, is the simplest statistical test there is: the frequency or monobit test, the first entry in every battery of tests for random bits, which the test that ranks the generators placed at the bottom of a hierarchy of increasingly demanding tests. A generator that fails it fails as visibly as a generator can. The twister started from a single bit would fail it, at any reasonable threshold, on every block of its first hundred thousand outputs, and on a fair share of blocks until about three hundred and seventy thousand.

That is the strangeness of zeroland. The twister passes the most demanding tests applied to it — equidistribution in 623 dimensions is a far stronger property than an even share of 1s — and yet from certain states it fails the weakest one for hundreds of thousands of outputs. The resolution is that the strong properties are averages over the whole period, or over all starting states, and say nothing about particular stretches. Randomness that has to be earned put the general point as a definition: a sequence is random only relative to the tests it has passed, and a guarantee about the whole cycle is not a guarantee about the part a program actually uses.

The seeding routine is the defence #

A user does not normally start a generator from a single bit, and the twister’s authors supplied a routine that makes it hard to. The last figure compares three ways of filling the state.

Writing the seed 12,345 into one word of the state and leaving the rest at nought — an easy mistake when a generator’s state is exposed as an array — gives a state with six 1s, and it behaves exactly like the single bit: it starts at a share of $0.006$ and spends hundreds of thousands of outputs climbing. The twister’s own routine fills every word from the seed by a multiplication by 1,812,433,253 and an addition, which spreads the seed’s bits across all 624 words before the first output, and its share is $0.499$ from the first block of two thousand. That routine is not cosmetic. It is the only thing standing between the user and zeroland, and code that sets the twister’s state directly — to restore a saved state, or to seed from a short key without using the provided routine — needs the same care.

What the averages cannot show #

The figures measure one symptom of zeroland, the share of 1s, and a generator can escape that measure and still be in trouble. The share is a single number per block; a generator whose 1s had spread to half its bits but in a structured pattern would pass it and fail a finer test. For the twister the raster figure suggests that once the share reaches a half the output is unremarkable to the eye, but nothing here tests the escaped output against the full batteries of statistical tests, and the rank test of the earlier essay would fail it at any point, in zeroland or out, because that failure is a property of linearity rather than of the start.

Nor do the figures cover the many generators not drawn. The share-of-1s escape is a property of the recurrence’s sparsity, so generators with sparse recurrences and large states — lagged Fibonacci generators with exclusive-or, and other twisted designs — have long zerolands, and generators with a nonlinear step, such as those that multiply, have essentially none, because multiplying by a large odd constant spreads a single bit into every higher bit of the word at once. Which particular generators in current use have zerolands long enough to matter is a question about each one, answered by running it.

Still open: mixing against equidistribution #

Panneton, L’Ecuyer and Matsumoto measured a generator’s speed of escape by a quantity they could compute from its recurrence, and designed the WELL generators to make it large while keeping the equidistribution that a filter that changes only the spread described. What is not known is how the two goals trade against each other in general: for a given state size, period and speed, what is the best combination of equidistribution and escape speed a linear recurrence can achieve? The WELL generators sit near the best known points, but the space of linear recurrences of a given size is far too large to search, and no bound says how much better a recurrence could do.

The other open direction concerns what the escape measures. Zeroland is the neighbourhood of one special state, but every linear generator has, for every state, a neighbourhood of states differing from it in a few bits, whose futures differ from its own by a sum that starts sparse. Two runs of the twister from seeds that differ in a single bit of state are, for the first few hundred thousand outputs, nearly identical except in a sparse pattern of bits — the same slowness viewed as a lack of sensitivity to the starting state. How much that matters for the uses to which such generators are put, especially parallel simulations seeded with nearby states, is a question about practice rather than mathematics, and it is studied one application at a time.

A price paid at the start #

A linear generator is a matrix raised to ever higher powers, and from a nearly-zero vector that matrix’s powers produce nearly-zero vectors for as long as the matrix takes to mix. For xorshift128 and WELL512 that is a few dozen outputs and no user would notice. For the Mersenne twister, the most widely deployed generator of its generation, it is a third of a million outputs of nearly nothing, a consequence of the same sparse twist that makes it fast and gives it its famous period. The defence is its seeding routine, which never leaves the state sparse, and the lesson is the one a memory of four bits taught with the smallest shift register: a linear generator’s behaviour is the behaviour of its matrix, and the matrix does not know which states a user would consider unusual.