Variance
Named by 22 essays across 5 fields — each of them below, with the objects they name alongside it.
How far from the average a thing can be
Knowing only an average and a spread — nothing about the shape, nothing about the number of outcomes, nothing about symmetry — the chance of landing three standard deviations out is at most one in nine. And there is a distribution that lands there exactly that often, so the bound cannot be improved.
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.
The walk that becomes a curve
Shrink the steps of a random walk and it disappears. Shrink them while stretching the time in the right proportion — space by the square root of whatever time is divided by — and something is left behind, which is a curve nobody could draw.
The shape that averaging leaves alone
Adding independent quantities blurs their distributions together, and rescaling restores the width. Almost every shape is changed by that operation. Exactly one is returned unaltered, and that is why sums of unrelated things keep arriving at it.
An average that never settles
The average of many independent quantities is supposed to steady as their number grows. For one famous distribution it does not steady at all — the average of a thousand draws has exactly the same distribution as a single draw, and no amount of further averaging changes it.
How fast the bell arrives
The limit theorem says a standardised sum approaches the bell curve and says nothing about when. The rate is one over the square root of the number of terms, the constant in front is made of the third moment, and both are visible.
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.
Sampling where the answer lives
Monte Carlo error cannot be made to fall faster than the square root, so the only thing left to attack is the constant in front of it. Drawing points where the integrand is large, and dividing by how often they were drawn, leaves the answer alone and can shrink the noise many times over.
Too many orders to list
The rule is an average over every order the players could have arrived in. At seven players that is five thousand orders and at twenty it is more than there are seconds in the age of the universe — so the average is sampled, and the error falls at a rate that can be measured.
Finding a threshold with two moments
Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.
The coefficient that is a polynomial
Add a second variable to track a statistic and each coefficient stops being a number. Set the new variable to one and the old count comes back untouched; leave it in and the mean of the statistic is a derivative rather than an average.
The bound is the answer to a search
Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.
No single input can move it far
Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.
Any unevenness brings the match sooner
Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.
A coin in front of every term
Put all plus signs in front of 1, 1/2, 1/3, … and the sum runs off to infinity; alternate them and it settles on log 2. Toss a fair coin for each sign instead, and the sum settles — every time, on a different number. Where it tends to settle has a smooth, flat-topped shape, and at the value 2 that shape takes a height that agrees with one eighth to forty-two decimal places and is not one eighth.
The median of many small averages
Knowing only that a quantity has a finite spread, the plain average of n samples can be promised to within σ/√(nδ) with confidence 1 − δ, and no better — Chebyshev's bound is tight, and rare large jumps achieve it. Cut the same samples into a dozen blocks, average each block, and take the median of the averages, and the promise improves to within about σ√(log(1/δ)/n). Nothing about the data has been assumed beyond the spread; only the way of combining it has changed.
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.
Drawn without putting back
Every concentration bound on this shelf assumes the draws are independent. A real sample is not: a pollster does not ring the same person twice, and every ball taken from an urn changes what is left in it. The dependence runs the helpful way. Wassily Hoeffding proved in 1963 that a sample drawn without replacement is at least as concentrated as one drawn with it, for every convex measure of spread at once — and the variance falls by an exact factor that reaches zero when the whole urn is taken.
Charged for the variance, not the range
Hoeffding's inequality knows one thing about each term of a sum: the interval it lies in. For ten thousand coins that each land heads once in a thousand, that makes it promise almost nothing — a 92% chance of thirty heads, when the truth is two in ten million. Tell the bound each term's variance as well and it changes character: Bernstein's and Bennett's inequalities decay like the normal curve while the deviation is small and like a Poisson tail beyond, and for rare events they are millions of times sharper.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
ExpectationConvergence rateNormal distributionScalingConcentration inequalityIndependenceRandom walkTail boundConvergenceHeavy tailsSamplingCentral limit theorem