Order out of noise — page 5

Algebra

The shape a random ball grows into

Give every road of the square grid a random travel time and ask what can be reached from one point in time t. The region is ragged, and rescaled it converges to a fixed convex shape — but which shape is unknown for every natural law. Computing it shows a curve within a few per cent of a circle for continuous travel times, a flat side where fast roads percolate along a diagonal, a time per step that is still drifting at a hundred and twenty-eight steps, and fluctuations that grow like the distance to the power one third rather than one half.

Discrete

Coins hidden in the roots

The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.

Discrete

The longest wait for a prime

Near a number x the primes are on average log x apart, and the longest stretch without one below x is much longer: about the square of log x, if the primes behave like random numbers with the right density. Sieving to thirty million finds twenty-four record gaps, all climbing in the shape of that square and all below it. A random model of the primes gets the scale right and the details wrong, and the correction for what it gets wrong predicts gaps larger still — larger than any anyone has found.

Dynamics

A growth rate no step contains

Start with 1, 1 and at every step either add the last two numbers or subtract them, choosing by a coin. The sequence wanders, shrinks, even returns near zero — and grows, almost surely, like 1.13198824 to the power of the step. That number is a Lyapunov exponent of a product of random matrices, and it cannot be found by averaging anything about a single step: the two steps do not commute, and the rate depends on which way the vector is pointing when each one is applied.

Dynamics

Fractions repeat and roots look random

Almost every number between 0 and 1 has base-φ digits with the frequencies Parry's measure predicts. Which particular numbers do? Every fraction, provably, does not: its expansion repeats from the first digit, with a period equal to the period of the Fibonacci numbers modulo its denominator. And √2 − 1 and 1/π, computed exactly to twelve thousand digits, match every predicted frequency to within sampling error — which proves nothing about them at all.

Logic

The squares that answer every request

Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.

Number

Class groups drawn at random

The class number of an imaginary quadratic field measures how badly unique factorisation fails there, and it looks arbitrary: 1, 2, 4, 3, 5, 12, 1. Count how often 3 divides it and the answer is not one time in three but noticeably more — heading, by a conjecture of Cohen and Lenstra, for 44 per cent. The reason is that class groups behave like finite groups chosen at random with each group weighted by one over its number of symmetries, so groups with few symmetries, like the cyclic group of order 3, turn up more often than the naive count suggests.

Algebra

How rarely a walk on a group comes home

Walk at random on the picture of a group, one generator at a time, and ask for the chance of standing at the start after 2n steps. On the line, the plane and three-dimensional space it falls like a power of n. On the tree that pictures the free group it falls by the factor √3/2 every step, exponentially. Kesten proved in 1959 that this is no accident of two examples: the chance falls exponentially exactly when the group's balls are mostly boundary, so a probabilistic rate and a geometric ratio are the same measurement.

Probability

A walk that follows its own footsteps

Let a walk step up with probability equal to the share of up-steps it has taken so far, and every count of up-steps after twenty steps is exactly equally likely. The walk leaves along a straight line at a speed chosen by its first few steps, and although it is expected to come back to its start infinitely often, almost every run comes back only a few times.

Number

How many primes a typical number has

A typical number near N has about log log N different prime factors, and the count is spread around that in a bell curve whose variance is log log N as well. Both facts are theorems. Neither is visible at any size anyone can count: up to ten million the average is right and the spread is less than half what the limit says.

Dynamics

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.

Number

Is the partition count even half the time?

The number of partitions of n is even for 50.0% of the n up to half a million, its runs of one parity are as long as a coin's, and nothing proves that the share is a half — the best theorems only show there are at least about √n of each. Modulo 5 and 7 the zeros carry Ramanujan's congruences and something more: an excess that follows whether 1 − 24n is a square.

Probability

An urn forgets its start only below one half

Let each draw from an urn add balls of both colours in fixed amounts, and the long run depends on a single ratio of two eigenvalues. Below one half the urn behaves like a coin, its fluctuations spread like the square root of the draws and settle into a bell. Above one half the first few draws decide most of the outcome, the spread grows faster, and the shape that results is not a bell and depends on how the urn began.

Probability

What a jump costs evenly spread points

Scrambled Sobol' points integrate a smooth function with an error that falls like N to the power −3/2. Put a jump in the integrand along a tilted line and the exponent halves, to −3/4, because about √N of the N boxes the points fill are cut by the jump and each of those is left to chance. A jump along an axis costs almost nothing, the cost grows with the length of the jump and the dimension, and integrating across the jump before sampling gives the whole rate back.

Topology

Counting targets when the sensors make mistakes

Add up the Euler characteristics of the regions where sensor counts are high and the answer is exactly the number of targets — until one sensor misreads. Each wrong reading is a new piece or a new hole, so the error grows with the number of sensors instead of averaging away. Smooth the readings and count each piece and hole by how long it survives as the threshold is lowered, and the count comes back exactly, with half the readings wrong, at the price of having to know how small a real feature can be.

Discrete

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

Probability

Multiplying makes the digit one common

Multiply a few random numbers together and the product starts with 1 about 30 per cent of the time and with 9 under 5 per cent — Benford's law, which no factor contains. The logarithm of a product is a sum, the central limit theorem spreads that sum across many powers of ten, and once it is spread its fractional part is uniform. The approach is geometric, at a rate fixed by a single number for each kind of factor; sums never get there, and the powers of two get there with no randomness at all.

Topology

Pieces minus holes on a random surface

Cut a random landscape at some height and the region above it breaks into pieces with holes in them. How many pieces, and how many holes, has no formula. Their difference does: the average Euler characteristic of the region above height u is a constant times u multiplied by the bell curve at u, exactly, for every smooth Gaussian surface — because the Euler characteristic is a sum of peaks, pits and saddles, and the average number of those can be computed point by point.

Computation

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.

Algebra

Regression is a square completed halfway

A bell in two variables, sliced at a fixed x, is a bell in y — and completing the square in y alone says where it is centred: at ρx, on a line flatter than the ellipse's own axis. That gap is regression to the mean, and the same completion says it runs backwards in time just as well as forwards.

Computation

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.

Dynamics

A threshold no average can see

Damp the random Fibonacci sequence — add or subtract β times the term before last, by a coin — and somewhere between β = 0.6 and β = 0.8 almost every run stops shrinking and starts growing. The switch is at β ≈ 0.70258. The average of the squares, which can be computed exactly, grows for every β there is, so the one number that decides the sequence's fate is invisible to the one number anybody can compute.

Probability

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.

Probability

Counting a population by its repeats

The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.