Order out of noise — page 4

Probability

Evidence measured in decibans

Write a probability as odds and take the logarithm, and every piece of evidence becomes a length. A positive result on a good test is thirteen decibans; a negative one is minus twenty. Lay the lengths end to end from the prior and the posterior is where they stop, in any order. The rule fails in exactly one way — when two pieces of evidence share a cause — and Turing built a code-breaking method on the arithmetic.

Discrete

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.

Number

The patterns primes are allowed to make

Primes two apart are twin primes; primes six apart are about twice as common; three primes two apart happen exactly once, at 3, 5, 7. Which patterns of primes can recur for ever is decided by remainders alone — a pattern must leave some remainder free modulo every prime — and how often each one recurs is predicted, to within a few per cent, by a constant computed from nothing else.

Probability

Points on a lattice that see almost nothing

Average a function over the points of a carefully tilted lattice and the error can fall like one over the square of the number of points — far faster than random sampling, and faster than the most evenly spread sequences. The reason is that a lattice rule is blind to only a thin set of frequencies, its dual lattice, and a smooth periodic function has almost nothing there.

Probability

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.

Discrete

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

Dynamics

Where the time goes on an attractor

A chaotic orbit's position is unpredictable within a few dozen steps. How it divides its time is not — start anywhere, follow long enough, and the fraction of time spent in each region comes out the same. That distribution lives on a set of no area, and among the infinitely many ways an orbit could spend its time, typical starts pick exactly one.

Logic

The graph that coin tosses always make

Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

Probability

The narrowest door sets the pace

How fast a chain forgets is an eigenvalue, and nobody can compute the eigenvalues of a chain worth studying. Cheeger's inequality trades the eigenvalue for a picture — the narrowest door in the state space — and pins the one between the square of the other and twice it. Both ends of that range are reached, on graphs small enough to search completely.

Probability

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

Discrete

The crossings a graph cannot avoid

Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.

Discrete

Every point at the average of its neighbours

A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.

Number

How often two generates every remainder

For some primes p, the powers of 2 run through every non-zero remainder before repeating; for others they get stuck in a smaller cycle. Among the primes up to two million the first kind make up 37.43% — and Artin predicted 37.40% in 1927 by treating each way of getting stuck as an independent accident. For the base 5 the same prediction is wrong, because two of the accidents are secretly the same one, and nobody can yet prove that 2 works for infinitely many primes at all.

Probability

When every value comes from the same hat

A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.

Algebra

The sums of primitive roots are always whole

Take the roots of unity of order exactly q, raise each to the power n and add them. The answer is always a whole number, it depends on n only through what n shares with q, and as n varies the sums behave like the sines and cosines of a Fourier series — so well that Ramanujan could rebuild the sum of the divisors of any number from them, and prove that their weighted total is nought, a fact that at n = 1 is the prime number theorem.

Dynamics

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.

Dynamics

A rule that remembers one row back

Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.

Number

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.

Topology

Almost every long loop is knotted

Close a random walk into a loop and ask whether it is knotted. With ten steps almost never; with a hundred, more than one time in five it can be proved knotted by a single number; with two hundred and fifty, more than half. The chance of staying unknotted falls exponentially with length — Frisch, Wasserman and Delbrück guessed it for polymer rings around 1961, and it was proved in 1988 — because a knot needs only one small tangle somewhere, and a long loop has room for many.

Algebra

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.

Algebra

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.

Dynamics

Two numbers in one jagged record

A measured record comes with no rule, so its dimension has to be estimated from a finite stretch of samples — and two things go wrong that never trouble a graph built from a formula. The popular estimator depends on the units the record is written in, and the dimension, which describes the record up close, turns out to be independent of its memory, which describes it from far away. For a self-affine path the two are tied by D = 2 − H; for a record, they are two numbers.

Logic

A walk that beats trying everything

To decide whether clauses of three letters can all be satisfied, the obvious method tries all 2ⁿ assignments. Uwe Schöning's method, from 1999, starts at a random assignment and wanders: pick a clause that is false, flip one of its letters at random, and repeat three times as many times as there are letters. A single try usually fails, but it succeeds with chance at least about (3/4)ⁿ, so about (4/3)ⁿ tries are enough — and the reason is a walk on a line that goes the wrong way two times in three.

Probability

Two constants that do not walk at random

Pollard's factoring method trusts x² + c modulo a prime to repeat as soon as a random function would, after about √p steps. For c = 1 and c = 3 it does. For c = 0 and c = −2 it runs twelve to eighteen times longer on average, with almost no tail and enormous cycles, because those two maps are multiplication in disguise and their cycles are set by the order of 2 rather than by chance. Every other constant walks at random — including in the one respect in which x² + c is plainly not random, that it is two-to-one.