Concept

Central limit theorem

The statement that a standardised sum of many independent contributions is approximately bell-shaped. It describes a window of width one over the square root of the count around the mean, and says nothing about probabilities further out than that.

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

One set of sums, two scalings, two different limits. The exact distribution of a sum of n independent copies, scaled two ways. Divided by n it collapses onto the mean; divided by the square root of n it holds a fixed width and settles into a shape.

The average settles and the wobble does not

Two theorems are usually met a page apart and sound as though one is a sharper version of the other. They are the same sums looked at through two different magnifying glasses: divide by the number of them and everything collapses to a point, divide by its square root and a shape appears.

probability · Central limit
The chance the average clears 0.75, against the number of draws. The exact probability that the average of n draws exceeds a fixed level, on a logarithmic scale, falling along a straight line whose slope is the rate function, with the normal approximation drawn beside it and diverging.

The tail is not a bell

The limit theorem describes a window of width one over the root of n around the mean; ask instead for the chance that an average lands a fixed distance away and the answer falls exponentially, at a rate computed from the summand before any n is chosen.

probability · Central limit
The 91 histograms 12 draws can produce. A triangle whose points are the possible histograms of a fixed number of draws over three faces, each drawn as a dot shaded by how far it is from the true distribution.

When the whole histogram deviates

A rare average has a price, an exponent that grows with the number of trials. Ask instead for the chance that the whole tally of outcomes comes out wrong, and the exponent is no longer a function of one number — it is a distance between two distributions, and every rare-average rate is a shadow of it.

probability · Central limit
How fast each way of averaging closes in, as the dimension grows. Relative error against the number of points, both on logarithmic scales, for a regular grid in 1, 4, 8 dimensions and for random points in 8; the grid's lines steepen or flatten with the dimension and the random one does not move from a slope of a half.

The error that does not care how many dimensions

A grid gets rapidly better in one dimension and hopelessly worse in twenty. Random points get better at the same slow rate whatever the dimension, which is why a method that is bad everywhere ends up being the only one that works.

probability · Monte Carlo
Descents of 10 as a sum of 9 hidden coins. Bars of 9 coin probabilities beside a bar chart of the descents distribution for n = 10, with dots giving the coin-sum distribution landing on every bar.

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 · Generating functions
How many different primes divide a number up to ten million. The share of numbers up to 10⁷ with each count of distinct prime factors (6.7%, 25.4%, 36.4%, 23.9%, 6.9%, 0.7%, 0.0%, 0.0%), against the Erdős–Kac normal curve with mean and variance 2.78.

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.

number · Unique factorisation
Five urns, each drawn as walks. Simulated walks of 2000 draws for urns with replacement matrices (0,1,1,0), (2,1,1,2), (3,1,1,3), (7,1,1,7), (1,0,0,1).

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 · Random walk
Leading digits of products of random numbers, against Benford's law. 1 factor: ones 11.1%, nines 11.1%; 2 factors: ones 24.1%, nines 3.4%; 3 factors: ones 30.1%, nines 4.2%; 6 factors: ones 30.1%, nines 4.6%; the law gives 30.1% and 4.6%.

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.

probability · Central limit
Oscillators scattered below the threshold and gathered above it. N = 240, Lorentzian width 0.5: K = 0.5 gives r = 0.068; K = 2.5 gives r = 0.775.

A crowd of clocks that falls into step

Give a thousand oscillators a thousand different natural rhythms and let each be pulled towards the average phase. Below a definite pull nothing happens; above it a cluster forms and grows, and Kuramoto's 1975 calculation says exactly where: at twice the spread of the frequencies, with the order growing as the square root of one minus the threshold over the pull. A simulation lands on that curve to the third decimal.

dynamics · Sensitive dependence
A chain locks whole or breaks at its weakest link. Chain of 40, Kₗ = 4.4817 at link 27; frequency spread 1.86e-5 at 1.04 Kₗ, 0.0645 at 0.96 Kₗ.

A long enough chain never locks

Line oscillators with different natural rhythms up in a row and let each feel only its two neighbours. The chain locks into one frequency exactly when the coupling exceeds the largest running total of their frequency differences — a random walk tied down at both ends — so the coupling needed grows like √N, and its law is Kolmogorov's, the same distribution that tests whether a sample fits a curve.

dynamics · Sensitive dependence
A fixed p-value favours the null more as the sample grows. Even odds at p=0.05 near n=76, at p=0.01 near n=1202, at p=0.001 near n=83176; p=0.05 at n=10⁶ gives 116.9 to one for the fair coin; PEAR data z=3.614, p=0.00030, BF₀₁=11.90.

A result at five per cent that favours the null

Toss a coin a million times and find a count of heads exactly at the edge of significance, p = 0.05. A test at the usual level rejects fairness. A Bayes factor comparing a fair coin with a coin of unknown bias says the opposite, by 117 to one. Both computations are right, and the sample size that separates them is about seventy-six tosses.

probability · Bayes
Watching a fair coin until it looks unfair. Fair coins, 2000 runs to 100000: share reaching p<0.05 by 10³ 0.468, by 10⁵ 0.697; share reaching BF₁₀≥20 by 10³ 0.0280, by 10⁵ 0.0340.

Peeking until the answer is yes

Toss a fair coin, test for bias after every toss, and stop the moment the result is significant at 5%. Within a thousand tosses nearly half of fair coins have been declared biased, and with no limit on the tosses every one of them is. Watch a Bayes factor the same way, stopping at twenty to one, and no amount of watching gets more than one fair coin in twenty past the line.

probability · Bayes
The cheapest tree through forty points. n=40, seed 8: total 1.063675, largest edge 0.0605, ζ(3)=1.2020569.

The cheapest tree costs ζ(3)

Join n towns by every possible road, give each road a cost drawn at random between nought and one, and find the cheapest network of n − 1 roads that connects them all. However many towns there are, the bill tends to 1 + 1/8 + 1/27 + 1/64 + … = 1.2020569. The proof watches the cheap roads arrive one at a time and turns the cost into the area under a curve that counts the pieces of a growing random graph.

applied · Assignment
The median has a bell of its own. normal: median sd 0.1238 (pred 0.1247), mean spread 0.0985; laplace: median sd 0.1071 (pred 0.0995), mean spread 0.1405; cauchy: median sd 0.1588 (pred 0.1563), mean spread 1.5006

The middle value has a bell of its own

The central limit theorem is a theorem about sums, and the median of a sample is not a sum of anything. It has a bell all the same: the middle of n draws spreads like 1/(2f√n), where f is the height of the density at the middle — not the variance, which the median never consults. That one number decides when the median beats the average, by a factor of two for a two-sided exponential and outright for the Cauchy law; and where the density is nought at the middle, the bell fails, slowing to a fourth root or splitting in two.

probability · Central limit
Whose vote counts in a two-tier election. Relative chance a voter decides a two-tier vote, districts 9,25,49,81,121,169,225. one vote per district: 2.319 1.367 0.971 0.754 0.616 0.521 0.452. weight in proportion to voters: 0.501 0.296 0.630 0.815 1.466 1.240 2.051. weight in proportion to √voters: 1.021 1.003 0.998 0.996 0.995 0.994 0.994.

A vote worth a square root

Give each country in a council votes in proportion to its people, and a citizen of the largest has about fifteen times the say of a citizen of the smallest. Give each country one vote and the same ratio runs the other way. Lionel Penrose saw in 1946 that the fair weight is the square root of the population, because one voter's chance of deciding an election falls as one over the square root of the crowd. Computed for twenty-seven states, the best quota is 61.5%, and it holds the ratio to 1.006.

applied · Shapley value

Named alongside it

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

VarianceRandom walkScalingBayes factorConvergence rateExpectationHeavy tailsLarge deviationsLaw of large numbersLikelihoodNormal distributionP-value

All concepts