Matpic
mathematics, in pictures
Concept

Sampling

Drawing a limited number of cases from a large or infinite collection in order to say something about the whole. What makes a sample informative is how it was drawn rather than how large it is, since a systematic omission is not repaired by more of the same.

Named by 7 essays across 2 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 Which regions each rule favours. Average seats above or below exact quota for the largest and the smallest region, under each of the five methods, over 400 generated instances.

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.

applied · apportionment

Named alongside it

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

Monte CarloConvergence rateEstimator biasIntegralVarianceExpectationIndependenceProbability densityApportionmentApproximationBiasBuffon's needle

All concepts