Concept

Variance

The average of the squared distances of a quantity's values from its mean, whose square root is the standard deviation. It adds over independent quantities, which is the single fact behind the square root in every diffusion and every limit theorem.

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

five values, unevenly weighted, and the mass outside 3 standard deviations. A distribution drawn as bars, with the windows one and a half, two and three standard deviations wide marked. The probability outside each window is summed and compared with the bound that knows only the variance.

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.

probability · Concentration
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
One walk at three magnifications, and the shape it is heading for. The same random walk over three windows, each ten times longer than the last and scaled vertically by the square root of ten, so all three look alike. Beside them, the exact distribution of the position after a few step counts, standardised, closing on the bell curve.

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.

probability · Random walk
A lopsided distribution added to itself, and the shape that returns. On the left, the exact distribution of a sum of copies of one lopsided distribution, standardised, for several counts: the shapes converge. On the right, the bell curve convolved with itself, which is the bell curve again.

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.

probability · Central limit
Averages of a heavy-tailed quantity, which never settle. Running averages of draws from a Cauchy distribution, which jump rather than converge, beside the cumulative distributions of averages of 1, 4 and 16 draws, which lie on top of one another.

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.

probability · Central limit
How fast a sum becomes a bell curve. The largest gap between the distribution of a standardised sum and the bell curve, against the number of terms, on logarithmic axes. Both summands fall along a line of slope about minus a half.

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.

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
Two unbiased estimates of one integral, and their spread. The sharply peaked integrand with the proposal density that follows it, above a strip plot of 200 estimates from each of two methods; the weighted estimates cluster 4.2 times more tightly about the same value.

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.

probability · Monte Carlo
Sampling the orders, and how fast the answer arrives. The largest error in the estimated shares against the number of orderings sampled, both on logarithmic axes, with the square-root rate drawn through the first point.

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.

applied · Shapley value
A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

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.

probability · Random graphs
Permutations of n things, by how many pairs they put in the wrong order. A table whose row n and column k hold the number of permutations of size n whose inversions is k, with each row's total beside it — the plain count the one-variable series gives.

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.

discrete · Generating functions
The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over.

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.

probability · Concentration
What one input can do, over 1024 cases. A table of functions of several inputs with the largest effect any single input has on each, the bound that effect implies, and the true tail probability — computed by enumerating every input.

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.

probability · Concentration
A year of birthdays with a seasonal swing of ±50%, peaking in September. Bars for the 365 days of a model calendar with a seasonal swing of ±50%, peaking in September, drawn as each day's excess or shortfall against an even year. A shared birthday among 23 people has chance 54.86% against 50.73% for the even year, the first group with an even chance is 22, and the calendar behaves like 324.4 equally likely days.

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.

probability · Birthday problem
12 harmonic series with random signs, each settling on its own sum. Partial sums of the harmonic series with each sign chosen by a fair coin, for several independent runs, plotted against the number of terms on a logarithmic scale, beside the all-plus and alternating sign patterns.

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.

analysis · Harmonic series
How far each estimate can stray, when rare jumps are possible. The error that the sample mean and the median of 12 block means stay within, at confidence levels from 80% to 99.9%, over 60000 repeated samples of 120 draws from normal draws with rare large jumps, with Chebyshev's guarantee for the mean.

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.

probability · Concentration
Error against the number of points for three randomised methods. Log-log plot of root-mean-square integration error against N from 16 to 4096 for plain Monte Carlo (slope -0.52), digitally shifted Sobol' points (-1.00) and Owen-scrambled Sobol' points (-1.43).

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.

probability · Monte Carlo
Tails of a sample drawn with and without replacement, against two bounds. t 0.000: without 1.00e+0, with 1.00e+0, Hoeffding 1.00e+0, Serfling 1.00e+0; t 0.075: without 2.65e-1, with 3.88e-1, Hoeffding 1.00e+0, Serfling 9.56e-1; t 0.150: without 1.35e-2, with 5.57e-2, Hoeffding 3.31e-1, Serfling 1.05e-1; t 0.225: without 1.10e-4, with 3.02e-3, Hoeffding 3.48e-2, Serfling 2.62e-3; t 0.300: without 1.19e-7, with 8.09e-5, Hoeffding 1.49e-3, Serfling 1.50e-5.

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.

probability · Concentration
Tails of a sum of rare events: exact, and three bounds. 10: exact 5.42e-1, Bennett 1.00e+0, Bernstein 1.00e+0, Hoeffding 1.00e+0; 15: exact 8.34e-2, Bennett 3.39e-1, Bernstein 3.42e-1, Hoeffding 9.95e-1; 20: exact 3.44e-3, Bennett 2.09e-2, Bernstein 2.35e-2, Hoeffding 9.80e-1; 25: exact 4.64e-5, Bennett 3.66e-4, Bernstein 5.50e-4, Hoeffding 9.56e-1; 30: exact 2.46e-7, Bennett 2.34e-6, Bernstein 6.10e-6, Hoeffding 9.23e-1; 35: exact 5.88e-10, Bennett 6.45e-9, Bernstein 3.92e-8, Hoeffding 8.82e-1; 40: exact 7.03e-13, Bennett 8.70e-12, Bernstein 1.67e-10, Hoeffding 8.35e-1; 45: exact 4.56e-16, Bennett 6.27e-15, Bernstein 5.21e-13, Hoeffding 7.83e-1; 50: exact 1.71e-19, Bennett 2.59e-18, Bernstein 1.27e-15, Hoeffding 7.26e-1.

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.

probability · Concentration
Four records: rough or smooth, long memory or short. Four random records in a two-by-two grid, each drawn whole and close up; roughness shows in the close-ups and memory in the whole records, and the two vary independently.

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.

dynamics · Fractal dimension
How long x² + c runs before repeating, for four constants. Four survival staircases on a logarithmic scale of length: two following the birthday curve, and two for c equal to 0 and minus 2 lying far to the right.

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.

probability · Birthday problem
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
Every slice of a tilted bell is a bell, centred off the axis. Contour ellipses of a two-variable bell with correlation 0.6, five vertical slices drawn as bells, their centres on the line y = 0.6x, and the ellipses' long axis on the diagonal y = x.

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.

algebra · Completing the square
One shared birthday, as a measurement of the year. Histogram over 20000 rooms of the estimate T(T − 1)/2 from the first shared birthday, averaging 361 against 365, spread widely.

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.

probability · Birthday problem
Running totals of random steps, stopped as they pass 4. Four staircases of uniform steps stopped on passing 4, taking 11, 8, 8, 10 steps; the exact mean is 8.666604.

Two-thirds of a step past the line

Add random numbers between nought and one until the total passes one, and it takes e of them on average. Ask the same about passing any t and the answer is an exact finite sum that settles, within a few units, onto the line 2t + 2/3. The slope is one over the average step. The two-thirds is the interesting part: it is what the one step that crosses the line charges for being chosen by its length, and it is set entirely by how much the steps vary.

probability · Expectation
Primes in five thousand thin sectors. 581517 primes in (2e7, 4e7] in 4967 sectors; mean 117.08, variance ratio 0.874, 2 empty.

Sectors that shrink with the primes

Hecke proved that the angles of the primes a² + b² are evenly spread, so every fixed sector eventually gets its share. Let the sector shrink as the primes grow, to width X^(−α), and the question is open beyond small α. Measured on the 581,517 such primes between twenty and forty million, wide shrinking sectors fluctuate far less than chance and thin ones as much as chance — and the thin sectors that go empty are not scattered: they gather beside the directions of small rational slope, most of all slopes like 1/3 and 1/1 whose two terms are both odd.

number · Sums of two squares
The longest run of heads at three sizes, never the same shape. n=65536: 12:0.018 13:0.117 14:0.233 15:0.239 16:0.172 17:0.104 18:0.057 19:0.030 20:0.015; n=82273: 13:0.075 14:0.204 15:0.249 16:0.197 17:0.124 18:0.070 19:0.037 20:0.019; n=104408: 13:0.040 14:0.162 15:0.248 16:0.221 17:0.148 18:0.086 19:0.046 20:0.024 21:0.012.

The longest run has no limit

Toss a fair coin n times and the longest run of heads is about log₂ n. The average settles: it is log₂ n − 0.667 to within a few millionths by a million tosses. The distribution does not. Because the run is a whole number and log₂ n is not, the chance of each value swings round the same cycle once every doubling of n, for ever, and computing it exactly to a million tosses shows the swing as large at the end as at the start.

probability · Expectation
Two edges of a small graph, and whether one makes the other less likely. tree: 8 total, 5 with e, 5 with f, 3 with both, ratio 0.9600; forest: 24 total, 10 with e, 10 with f, 4 with both, ratio 0.9600; connected: 14 total, 10 with e, 10 with f, 7 with both, ratio 0.9800.

Edges that crowd each other out

Pick a spanning tree of a graph uniformly at random, and the presence of one edge makes every other edge less likely — a theorem of Kirchhoff's electricity. Pick a forest instead, or a connected subgraph, and the same is believed and unproved. Checking every pair of edges in every labelled graph up to six vertices, 871,926 pairs for forests alone, finds no exception, and comes as close as 0.9994 to one.

probability · Concentration
Two random strings of bits and the longest thread between them. Two random binary strings of length 36; longest common subsequence 27.

The longest thread between two random strings

Write down two random strings of a thousand bits each and find the longest sequence that can be read in both, skipping freely. It is about 81% of each, and the exact share — the Chvátal–Sankoff constant — has resisted computation for fifty years. Its fluctuations are a smaller mystery with a sharper edge: the variance is known to be at most n/2, and over every length that can be computed it grows like n to the power 0.7, with nobody able to say what it does after that.

probability · Concentration
Seven workers, seven jobs, one cheapest way. A 7 × 7 table of exponential costs; optimal assignment 1→5, 2→2, 3→4, 4→1, 5→6, 6→7, 7→3 costing 0.7482; expected optimum Σ 1/k² = 1.511797.

One, plus a quarter, plus a ninth

Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.

applied · Assignment
Cells of points scattered at random. Poisson–Voronoi tessellation of 600 points on a torus; mean sides 6.000000000; side counts 3: 9, 4: 56, 5: 165, 6: 167, 7: 131, 8: 49, 9: 18.

The shape of a cell around a random point

Scatter points at random and give each the region nearer to it than to any other. The cells come in every shape from triangles to twelve-sided polygons, and almost nothing about them is fixed by a formula — except one thing: on a closed surface they have exactly six sides on average, every time, because three cells meet at every corner. Two hundred thousand cells measure the rest: 29.5 per cent hexagons, Lewis's law, and small cells surrounded by large ones.

geometry · Voronoi
Predicting the unseen works until the future outgrows the past. Zipf population of 5000, mean sample 2000: seen 756, f1 561, f2 95; at t = 1, 2, 4: truth 489/873/1462, smoothed 492/843/1243.

How many new kinds the next sample will show

Count how many kinds were seen once, twice, three times. Good and Toulmin's alternating sum f₁t − f₂t² + f₃t³ − … then predicts, with no bias at all, how many new kinds a further sample t times as large will reveal. It works perfectly up to t = 1 and is worthless just beyond: past that point the kinds seen most often are multiplied by t to a high power, and the spread of the estimate passes 10⁴⁰ by t = 1.5. Truncating the sum at a random point rescues it, and each fourfold increase in the first sample buys about half a unit more of future.

probability · Birthday problem
One random path estimates the whole tree. probe columns 4,2,5,3,6,0; choices 8,5,3,1,2,1; estimate 769; exact 2057.

One random path down a search tree

Before running a search that may take a week, it is worth knowing whether it will take a week or a century. Donald Knuth's answer, from 1975, is to walk down the search tree once at random, multiply the numbers of choices met on the way, and add up the products: the result is, on average, exactly the size of the tree. On the eight-queens tree one path guesses 769 against a true 2,057 and twenty thousand paths average to within a tenth of a per cent. On a tree built to hide its bulk, the same unbiased estimate is almost always wrong by a factor of thousands.

probability · Monte Carlo
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
Two sign sequences laid on themselves. Length 41: random signs (seed 41) with E = 552 and merit factor 1.523; the rotated Legendre sequence of 41 with E = 176 and merit factor 4.776.

A quarter turn quiets the echoes

Lay a sequence of signs on a shifted copy of itself and add up the squares of the overlaps. Random signs leave the total near n²/2, and the squares modulo a prime, started a quarter of the way along, cut it to a twelfth. Exhaustive search finds far quieter short sequences, and no infinite family is proved to do better than 6.342.

algebra · Polynomial roots
Seven numbers whose 128 subset sums all differ. The 128 subset sums of 20, 31, 37, 40, 42, 43, 44, spread from 0 to 257 with no two equal, above those of the powers of two 1 to 64.

Numbers whose subset sums all differ

The powers of two 1, 2, 4, …, 64 have 128 subset sums and no two are equal. So do 20, 31, 37, 40, 42, 43 and 44, whose largest member is smaller, and an exhaustive search shows no seven numbers do it with less. A pigeonhole on the sums says the largest member must grow like 2ⁿ/n; a variance argument improves that to 2ⁿ/√n; the best known sets sit near 0.22 × 2ⁿ. Whether the truth is a constant times 2ⁿ is Erdős's five-hundred-dollar question, and the pigeonhole cannot reach it.

discrete · Pigeonhole

Named alongside it

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

ExpectationConvergence rateNormal distributionExhaustive searchScalingConcentration inequalityHeavy tailsSamplingIndependenceRandom walkTail boundCentral limit theorem

All concepts