Concept

Fluctuations

How far a random quantity typically strays from its expected value. For sums of independent terms the spread grows like the square root of their number; for growth processes and random matrices it can grow at other rates.

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

400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0.

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.

discrete · Ramsey theory

A ball of the square grid with random travel times. A ragged roughly round region of grid cells shaded in bands by the time a signal from the centre first reaches them.

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.

algebra · Cayley graph

Named alongside it

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

Limit shape Cayley graph Convexity First-passage percolation Longest increasing subsequence Monte Carlo Percolation Random graph Random matrix Random permutation Robinson schensted Subadditivity

All concepts