Matpic
mathematics, in pictures
Concept

Monte Carlo

Computing a deterministic quantity by averaging a random process designed to have that quantity as its mean. Its error falls like one over the square root of the sample size whatever the dimension, which makes it slow everywhere and the only workable method in high dimensions.

Named by 9 essays across 4 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 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 A walk that visits each state as often as its weight says. The target distribution over 12 states with the share of a 40,000-step Metropolis run beside each bar, above the first 300 steps of the walk itself; the two distributions differ by 0.5 per cent in total.

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.

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 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 Measuring a closed curve with inlets by throwing lines at it. A curve inside a disc crossed by a sample of random lines with each crossing marked, beside the mean number of crossings and the length it implies against the true length.

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.

analysis · Arc length 400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0.

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

discrete · Ramsey theory Where a random walk from the centre leaves the snowflake. 60,000 walks on spheres from the centre of the level-6 snowflake; the most-visited 10% of 768 boundary pieces receive 62.7% of the walks; one walk of 9 jumps drawn.

Where a random walk leaves the snowflake

Start a random walk at the centre of the Koch snowflake and record where it first touches the edge. The edge has dimension 1.26, but the places the walks arrive form a set of dimension one: 60,000 walks spread their entropy by ln 3 a level, not ln 4, and the busiest fifth of the edge takes nine tenths of them. Makarov proved in 1985 that it must be so for every simply connected region in the plane.

analysis · Measure

Named alongside it

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

SamplingConvergence rateEstimator biasIntegralVarianceExpectationIndependenceIntegral geometryPiProbability densityApproximationArc length

All concepts