Matpic
mathematics, in pictures
Concept

Randomness

The property of a sequence that no shorter description of it exists, or that no efficient procedure predicts it — two definitions that do not coincide. What a generator provides is neither; it is a short description arranged so that finding it is hard or unnecessary.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

The same modulus, four multipliers, four qualities. 4 linear generators at modulus 1021, drawn as scatters of consecutive pairs and ranked by the spacing of the lines their points fall on. The spacings differ by more than a factor of two.

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.

computation · Pseudorandomness Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly.

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.

computation · Pseudorandomness A scatter with no lines in it. 900 consecutive pairs from a generator that squares modulo a product of two primes. The points show no family of parallel lines, and an exhaustive search for a short relation between consecutive outputs finds none.

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.

computation · Pseudorandomness Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row.

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.

computation · Pseudorandomness One table of shares, two different lotteries. A doubly stochastic table decomposed into whole assignments twice, by two different orders, giving two mixtures that reconstruct the same shares.

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.

applied · Assignment

Named alongside it

The objects these essays reach for when they reach for this one.

PseudorandomnessModular arithmeticCryptographyAssignmentComplexityConvexityCounting-two waysDimensionEquidistributionFactoringFairnessFinite field

All concepts