Sampling
Named by 16 essays across 6 fields — each of them below, with the objects they name alongside it.
Getting pi by dropping needles on the floor
Throw a needle at a lined floor enough times, count how often it crosses a line, and pi falls out. There is no circle anywhere in the experiment.
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.
A walk that samples a distribution
When a distribution can be evaluated but not drawn from, a wandering point can be arranged to visit each state as often as its weight says. The rule needs no normalising constant, compares two weights and steps or stays.
Points too even to be random
Independent random points clump, and the clumping is what makes the error fall only as the square root. Points chosen to be evenly spread rather than independently beat that rate, and the price is that nothing about them is random at all.
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.
The rule with no favourites
Over four hundred instances, Jefferson's method gives the largest region a third of a seat more than its exact share and the smallest a third of a seat less. Adams reverses both. Webster's average is a hundredth of a seat, and that is not luck.
A length counted by the lines that cross it
Throw straight lines at random across a curve and count how often they cross it. The average count, times π times the radius of the target, is the curve's length — for a wiggly closed curve, a spiral or a snowflake alike, with no following of the curve and no derivative anywhere. It is Crofton's formula of 1868, and it measures length the way a map-reader's ruled transparency does.
The skeleton inside a shape
Take the Voronoi diagram not of a handful of points but of a shape's whole outline: the points inside the shape that have two nearest points on its edge. What comes out is a skeleton — a thin branching tree that describes the shape and, with one number attached to each point, rebuilds it exactly. It is also where fires lit all round the edge would meet, and it is violently unstable: a tooth too small to notice grows a branch several times its own size.
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.
A mate is rare until order ten
Euler asked whether a Latin square can have an orthogonal mate, and for every order but two and six the answer is yes for some square. For a square chosen at random the answer is different. Exactly 6 of the 56 reduced squares of order five have a mate and none of order six does; of squares drawn at random, about one in a hundred of order seven has one, one in three hundred of order eight, one in seventy of order nine — and three in five of order ten.
Almost every tree can be turned over
Cayley's n^(n−2) counts trees with labels on their points. Take the labels off and the count has no formula, because a symmetric shape absorbs labellings: the star on seven points can be labelled only seven ways, the one asymmetric shape 5,040. The bookkeeping that reconciles the two counts says something unexpected — almost every tree, labelled or not, can be turned over onto itself, where almost every graph cannot.
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.
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.
A wave known only at its ticks
Read a sine wave nine cycles a second at ten instants a second and the readings describe a wave of one cycle a second instead. Read a wave with nothing faster than 3.7 cycles a second at more than 7.4 instants a second and the readings determine it exactly. Both facts are the same fold of the frequency axis, and it is why wagon wheels turn backwards on film.
A grid that packs the copies
Sampling a pattern on a grid makes copies of its frequencies, one for every point of a lattice, and the pattern can be read back from the samples only if the copies do not collide. For a pattern whose frequencies fill a disc the square grid wastes room between its copies. Searching every lattice of samples for the fewest that work finds a nearly hexagonal one every time — 124 samples where the square grid needs 169 — and the saving is the hexagonal packing's over the square, 13.4% in the limit. In three dimensions it is 29%, and in twenty-four the cubic grid needs 16,777,216 times as many samples as the best.
Named alongside it
The objects these essays reach for when they reach for this one.
Monte CarloVarianceConvergence rateEstimator biasExpectationExhaustive searchIntegralAliasingFourier seriesFrequencyIndependenceIntegral geometry