Convergence rate
Named by 42 essays across 9 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.
How long until every one turns up
Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.
The sum that fits in one square
Half, then a quarter, then an eighth, forever. Adding infinitely many things sounds like it should give infinity, and the picture that says otherwise is a square with a corner left uncut.
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.
A map that shrinks everything
One extra hypothesis — that every distance is shortened by at least a fixed factor — turns the existence of a fixed point into its uniqueness, an algorithm for finding it, and a bound on the error after any number of steps.
Counting what has no formula
There is no expression that gives the nth prime, and yet the number of primes below a bound is predictable to within a fraction of a per cent — by a function that is not a formula for the primes but an integral of the wrong-looking quantity.
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 same map in a better basis
Measured along its own invariant directions, a linear map stops shearing and becomes two independent stretches. Nothing about the map has changed; the grid it is described against has.
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.
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.
A tail too small to be a whole number
If e were a fraction with denominator q, then q! times e would be a whole number. It splits into a whole part and a tail, the tail is squeezed strictly between nothing and one, and there is no whole number there.
How fast the staircase arrives
The slope at a crossing decides whether an orbit reaches it. The same number decides how fast — and when the slope is zero the arithmetic changes kind, from a fixed factor per step to a doubling of the correct digits.
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.
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.
The series everything else is measured against
A geometric series is not one series among many. It is the yardstick: a total exists if its terms eventually fit under one, so a single comparison settles infinitely many questions — and the test built from it says nothing at all in exactly the place where the interesting cases are.
The repair at the boundary
Where the geometric yardstick says nothing, compare a series with itself at doubled spacing. That one move turns every 1/n^p back into a geometric series, reads the threshold off at p = 1, and then produces an infinite hierarchy of boundaries with no slowest divergent series anywhere in it.
Almost no number is one
Sums of two squares look common — a sixth of all numbers up to a million are one. The fraction is falling to nothing, at a rate so slow that no computation will ever make it obvious, and the constant in front of it has been computed to fifty places and identified with nothing.
The one that hardly ever comes up
Make the kinds unequally likely and the tidy decomposition into stages fails, because a stage's rate now depends on which kinds turned up rather than on how many. What replaces it is an alternating sum over every subset — and the rarest kind turns out to be nearly the whole answer.
Pinned between two sequences
The ring dissection makes the answer obvious and proves nothing. Archimedes' method proves it and makes nothing obvious — it never exhibits the area at all, it rules out every other value — and the recursion that drives it computes π by hand with one square root a step.
A double root halves the error instead of squaring it
Near an ordinary root, Newton's method squares its error at every step and a handful of steps reach full precision. Near a double root it only halves the error — twenty steps where five would do, and a ceiling of about eight correct digits that no number of steps can break through. Doubling the step repairs the double root and ruins the simple one.
A cubic method that is Newton's in disguise
Halley's method, from 1694, uses the second derivative as well as the first and cubes the error at every step where Newton's squares it. It is also, exactly, Newton's method applied to a different function — p divided by the square root of p′ — and that single fact explains why its basins are calmer, why it walks out of the trap that holds Newton for ever, and why its boundaries are still fractal.
What a jump costs evenly spread points
Scrambled Sobol' points integrate a smooth function with an error that falls like N to the power −3/2. Put a jump in the integrand along a tilted line and the exponent halves, to −3/4, because about √N of the N boxes the points fill are cut by the jump and each of those is left to chance. A jump along an axis costs almost nothing, the cost grows with the length of the jump and the dimension, and integrating across the jump before sampling gives the whole rate back.
What it costs to find the point that stays put
Brouwer's theorem promises a point a map leaves where it is, and Sperner's corridor walks to it. On a gentle map the walk is short; twist the map about its fixed point and the corridor follows every turn, so its cost grows like the square of the grid. Halving the square by winding number finds the same point in a number of readings proportional to the grid's side whatever the map does — and no method that only reads the map can do fundamentally better.
The area of the Mandelbrot set, from two sides
The Mandelbrot set has an area, and nobody knows it. Counting grid cells closes in on 1.5066 from both sides, but every count judges a cell by a single point, and points on the boundary never declare themselves. An exact formula exists — π times one minus a sum over the coefficients of the map onto the set's outside — and every partial sum is a guaranteed upper bound; after sixteen thousand coefficients the bound is still 1.786, and at the rate it falls it would need something like 10²⁵ more.
Settling in order settles everywhere at once
A sequence of functions can settle at every point and never settle uniformly — the largest gap stays put while each point escapes it. Dini found the circumstances in which that cannot happen: continuous functions, a continuous limit, every member above the next, and a closed interval. Under those four conditions convergence at each point is convergence everywhere at once, and Weierstrass's iteration for the square root becomes a sequence of polynomials converging uniformly to |x|.
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.
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.
A share that depends on the average
What share of the whole numbers begin with the digit 1? Counted up to N, the answer swings between one ninth and five ninths for ever, and averaging the swing over N, even three times over, narrows it without removing it. Weight each number n by 1/n instead and the share settles at log₁₀ 2 — Benford's value — and so does every other sensible weighting that counts each decade alike. The primes behave the same way. Benford's law for the counting numbers is not a fact about them; it is a fact about how they are averaged.
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.
Two rays for every fraction
Seen from far away, every point of the Mandelbrot set's outside has an angle, and the curves of constant angle come in to land on the set. At the root of the p/q bulb exactly two of them land, and their angles are written by the staircase under a line of slope p/q. The limbs those pairs fence off share out the whole circle of angles between them, by the identity Σ φ(q)/(2^q − 1) = 1.
What a missing string of digits leaves behind
Strike from the harmonic series every term whose denominator contains 42 and the rest adds up to 228.45. Strike out 99 instead and it adds up to 253.28. The difference is not about which numbers are lost but about waiting: 99 overlaps itself, so it takes 110 random digits on average to turn up where 42 takes 100, and the sum is almost exactly ln 10 times that wait.
A best reply to the past
Let two players each answer the whole history of the other's play as though it were a fixed plan. In a zero-sum game the history closes in on the equilibrium, as Julia Robinson proved in 1951. In Lloyd Shapley's three-by-three game it never does: play runs round six profiles for ever, each run the one before plus the one three before plus two, so the runs grow by the real root of x³ = x² + 1 and every run is a fixed share of all the history.
Three hundred thousand outputs of nearly nothing
Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.
Where to take the samples
Every numerical integral is a weighted sum of samples of the curve. Spacing the samples evenly gives errors that shrink like a power of their number; choosing where they go, as Gauss did in 1814, makes six samples exact for every polynomial up to degree eleven and turns the power into a geometric rate. The surprise is that the humble trapezoid rule, evenly spaced and exact only for straight lines, does the same thing on any smooth curve that goes once round a circle — and that a single corner defeats every one of them.
A rule that counts lets the sum escape
Strike out every number containing a 9 and the harmonic series converges, to 22.92. Keep only the numbers with as many 7s as 3s and it diverges — slowly, like the square root of the number of digits. Ask for two such balances and it still diverges; ask for three and it converges. The dividing line is Pólya's theorem that a random walk comes home in one and two dimensions and not in three.
Newton's method without a derivative
Replace Newton's tangent by the chord through the last two guesses and the method no longer needs a derivative — but it needs two starting values, so its basins live in a plane of pairs instead of on a line. The errors multiply instead of squaring, their logarithms add like Fibonacci numbers, and the digits gained grow by the golden ratio: 1, 3, 5, 9, 15, 25, 41, 67, 109.
The error that predicts itself
Archimedes' polygons close on π slowly — six doublings of the sides for two decimals. But the error does not fall at random. Each doubling adds almost exactly a quarter of the area the doubling before it added, so the rest of the slivers can be summed before they are drawn. Liu Hui saw the quarter in 263; Snell and Huygens turned it into bounds; and the 96-gon that gave Archimedes two decimals gives six once its error is known.
A disc that turns for ever
At each fraction on the Mandelbrot set's cardioid a bulb is born. At the irrational numbers between them something rarer can happen: a disc round the fixed point rotates rigidly for ever, with no point falling in or flying out. Whether it exists depends on nothing but the digits of one continued fraction, and on one sum of their logarithms.
Root two, raised to itself for ever
Stack √2 to the power √2 to the power √2 without end and the tower settles at exactly 2. Solve the equation for a tower equal to 4 and √2 appears again, and that answer is false. The bases that give a limit run from e^(−e) to e^(1/e), the slope at the crossing decides everything, and a sum over labelled trees turns out to be the same number.
A table that never reaches π
Fill a square table with 1/1, 1/2, 1/3 along the rows, each row starting one place further on. Every row is a piece of the harmonic series, and yet the table stretches no vector by as much as π. At a thousand rows the stretch is 2.42, at a trillion it is near 2.94, and one integral explains both the number and the failure to arrive.
Named alongside it
The objects these essays reach for when they reach for this one.
ExpectationVarianceApproximationHarmonic seriesLimitConvergenceGeometric seriesIterationFixed pointMonte CarloSamplingExact arithmetic