Concept

Alternating series

A series whose terms change sign at every step, so its partial sums land on either side of the total in turn. Its partial sums therefore bracket the total, so stopping anywhere gives an error no larger than the first term left out.

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

The same terms, with the signs alternating. The partial sums of 1 - 1/2 + 1/3 - 1/4 + …, out to 24 terms. They close on 0.69315 from both sides at once, and the gap between consecutive sums is the next term, so the answer is trapped.

The same terms, in a different order, adding to whatever is asked

Flip alternate signs in the harmonic series and it converges. Reorder the terms — add nothing, remove nothing — and it converges to any number chosen in advance. Addition stops being commutative, and the picture shows where it goes.

analysis · Harmonic series
All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked.

Nobody gets their own hat

Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.

probability · Inclusion exclusion
Partial sums of x − x²/2 + x³/3 − … on [0, 1]. Partial sums of the power series x − x²/2 + x³/3 − … drawn on the interval from 0 to 1 with the function the series sums to inside the interval, and the values at x = 1 marked.

A sum read from inside

The series 1 − 1/2 + 1/3 − 1/4 + … adds to log 2, and the reason is not in the series. Its power series equals log(1 + x) inside the interval, and the value at the edge is read off by continuity. Abel's theorem says when that reading is honest — and the series 1 − 1 + 1 − …, which has no sum, is read the same way as a half.

analysis · Uniform convergence
A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve.

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

probability · Inclusion exclusion
Forty terms, two digits or thirteen. Errors after 40 terms: series -6.249e-3, Aitken -1.053e-6, Euler -1.250e-13; Wynn after 17 terms 1.250e-13.

Turning a slow series geometric

Leibniz's series 1 − 1/3 + 1/5 − 1/7 + … adds up to π/4, and it takes five billion terms to give ten decimal places. Euler found a rule that rewrites it, using exactly the same terms, as a series whose terms halve at every step — and forty of those give thirteen places. Aitken's and Shanks's later rules do better still. None of them works on every slow series, and the reason is that each one is a guess about the shape of the error.

analysis · Geometric series
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

Named alongside it

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

ApproximationConvergenceComplementary countingCounting argumentDerangementGeometric seriesLogarithmPiPower seriesAbel summationAbsolute convergenceCommutativity

All concepts