Matpic
mathematics, in pictures
Concept

Convergence rate

How quickly a sequence closes on its limit, measured by how the remaining error shrinks each step. It is what decides whether an iteration is worth running, and it can be geometric, quadratic or as slow as one over a square root.

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

120 needles on a lined floor. 120 needles dropped at random across evenly spaced lines; 83 of them cross a line.

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.

probability · Monte Carlo Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

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.

probability · Expectation A square cut into 7 pieces and a remainder. A square divided by cutting off a fixed fraction of what is left, over and over, so that the pieces are the terms of a geometric series and the uncut corner is the tail.

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.

analysis · Geometric series 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 x ↦ cos x: two starts, one destination. A map whose graph is nowhere steeper than a fixed factor under one, with staircases from two different starting points converging on the same crossing, and the distance to it falling under a geometric bound.

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.

analysis · Fixed points π(x) against its two estimates, up to 20,000. The ratio of the prime counting function to x over the logarithm of x, and to the logarithmic integral, plotted against x. The first is above one and coming down slowly; the second is close to one throughout.

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.

number · Prime distribution 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 The same map, written in the basis of its own eigenvectors. Three panels: the map [2, 1, 1, 2] on the standard grid, the diagonal stretch by 3 and 1 it becomes on the eigenvector grid, and the two put back together.

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.

algebra · Eigenvectors 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 Points too even to be random. 256 independent random points beside 256 points of a Halton sequence, with the largest mismatch between a box's share of points and its area plotted against the number of points for both.

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.

probability · Monte Carlo The tail that would have to be a whole number. For each denominator, the value of q! times the tail of the series for e, plotted against the band between zero and one where no whole number lies, with the bound 1/q above it.

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.

number · Irrationality How fast an iteration arrives. The distance from the fixed point plotted against the step number on a logarithmic vertical axis, for two ordinary iterations and for Newton's method, whose curve bends downward.

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.

dynamics · Iteration 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

Named alongside it

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

VarianceApproximationExpectationMonte CarloSamplingIntegralConvergenceEstimator biasIndependenceIterationNormal distributionCentral limit theorem

All concepts