Randomness
Named by 16 essays across 8 fields — each of them below, with the objects they name alongside it.
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.
One table, two lotteries
A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.
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.
Matching as they arrive
Applicants arrive one at a time, and each must be given a post or turned away on the spot. Any sensible rule matches at least half as many as the best assignment chosen with hindsight, and an adversary arranging the arrivals can hold every fixed rule to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post: the guarantee rises to 1 − 1/e, about 63%, and no rule of any kind can do better.
An error bar for points that are not random
Evenly spread points integrate far better than random ones and give no error bar; random points give an error bar and integrate badly. Randomise the even points themselves — shift a lattice by a random vector, or scramble the digits of a Sobol' sequence — and both are kept: an unbiased estimate, a confidence interval from a handful of repeats, and an error that falls faster than any deterministic set's.
A jam that comes from nowhere
Give cars on a ring road a top speed of five cells a step, let each slow to the gap ahead, and add one more rule: now and then, at random, a driver eases off by one. That is the whole of the Nagel–Schreckenberg model, and it produces what the exactly solvable rule 184 could not — jams that form in free traffic with no obstacle, drift backwards against the flow, and cost the road more than a third of its capacity. Set the top speed to one and remove the chance, and it is rule 184 again, cell for cell.
A cube root that looks like chance
The continued fraction of √61 repeats after eleven terms, and every square root's must. The cube root of 2 obeys no such law. Computed exactly, by a method of Lagrange's that never leaves the whole numbers, its terms run 1, 3, 1, 5, 1, 1, 4 … and throw up a 534 at the thirty-fifth place and a 7,451 at the 571st — and in every statistic anyone has measured, they look like the terms of a number picked at random.
Almost none of the roots are real
Pick the coefficients of a polynomial of degree a thousand at random, each one an independent draw from the bell curve, and ask how many of its thousand roots are real. The answer is about five. Mark Kac found in 1943 that the average grows only like (2/π) ln n, and the reason can be read off the real line itself: the real roots crowd towards +1 and −1 and spread evenly on a logarithmic scale of distance from them.
Random roots crowd onto the circle
The roots of a random polynomial are not scattered across the plane. They gather within about 1/n of the unit circle, and their directions spread evenly round it. Paul Erdős and Pál Turán proved in 1950 that this is not a fact about randomness at all: any polynomial whose coefficients are all of roughly one size has roots whose directions are nearly even, and the inequality says exactly how nearly, in terms of nothing but the coefficients.
The diamond that freezes its corners
A square board's domino tilings grow like 1.3385 choices per square. Arrange the same squares in a staircase-edged diamond and the count is exactly 2 to the n(n+1)/2 — only 1.1892 choices per square, at every size. The boundary has reached into the middle. Pick one of the diamond's tilings at random and the reason is visible: outside the circle inscribed in the diamond the dominoes are frozen into solid brickwork, and only inside it is the tiling free.
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.
The shape of a cell around a random point
Scatter points at random and give each the region nearer to it than to any other. The cells come in every shape from triangles to twelve-sided polygons, and almost nothing about them is fixed by a formula — except one thing: on a closed surface they have exactly six sides on average, every time, because three cells meet at every corner. Two hundred thousand cells measure the rest: 29.5 per cent hexagons, Lewis's law, and small cells surrounded by large ones.
Named alongside it
The objects these essays reach for when they reach for this one.
PseudorandomnessExpectationFinite fieldModular arithmeticPolynomialAlgorithmBinaryComplex numbersCryptographyLinear recurrenceMatchingRoots