Pseudorandomness
Named by 16 essays across 3 fields — each of them below, with the objects they name alongside it.
Points too even to be random
Independent random points clump, and the clumping is what makes the error fall only as the square root. Points chosen to be evenly spread rather than independently beat that rate, and the price is that nothing about them is random at all.
A memory of four bits
A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.
The test that ranks the generators
Every linear generator's output lies on a family of parallel planes. Which generator is better is decided by how far apart those planes are, and that distance is the length of the shortest whole-number vector the modulus annihilates — a quantity that can be computed exactly rather than estimated by testing.
Four numbers and the rule is yours
A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.
Randomness that has to be earned
A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.
Nineteen thousand bits of state
The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.
Fair bits from an unfair coin
Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.
A filter that changes only the spread
The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.
The column rule 30 will not explain
Start rule 30 from one live cell and read down the middle. The column has passed every test of randomness tried on it, and three plain questions about it are open: whether it ever repeats, whether its 1s make up half of it, and whether its n-th cell can be had without n steps of work. What can be measured says something about each — and the diagonals beside it are periodic, with periods that double going inwards.
A rotation that hides the lattice
A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.
Square it and keep the middle
John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.
Four lists find a collision sooner
Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.
A grid of bits whose rank stops at the state
Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.
Three hundred thousand outputs of nearly nothing
Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.
A seed is a deck
A shuffle that is perfectly correct, driven by a generator that passes every statistical test, can still deal almost none of the possible decks. A shuffle program is a function from the generator's starting state to an ordering of the cards, so it can never produce more orderings than the generator has states: a 32-bit seed reaches one deck in about 10⁵⁸. On nine cards and a 16-bit generator every case can be checked — 62,616 of the 362,880 orders are ever dealt — and on a full deck, six cards on the table are enough to name the seed and every card still to come.
Birthdays spaced too evenly
Scatter n birthdays through a year of k days, sort them, and count how many of the gaps between neighbours repeat an earlier gap. For random birthdays the count is close to a Poisson variable with mean n³/4k. A linear congruential generator with m states, read in pairs, matches that law until the grid has as many cells as the generator has states, and then leaves it at once: at sixteen times as many cells, every run of the spacings count rejects it. The sample that catches it is about five times the cube root of the period — 8,192 outputs for a 32-bit generator, thirteen million for a 64-bit one — and the same states, scrambled before they are read, pass.
Named alongside it
The objects these essays reach for when they reach for this one.
RandomnessFinite fieldPeriodBirthday problemEquidistributionLinear recurrenceModular arithmeticBinaryCollisionState spaceUniform distributionConvergence rate