Monte Carlo — the series
-
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.
-
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.
-
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.
-
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.
-
Points on a lattice that see almost nothing
Average a function over the points of a carefully tilted lattice and the error can fall like one over the square of the number of points — far faster than random sampling, and faster than the most evenly spread sequences. The reason is that a lattice rule is blind to only a thin set of frequencies, its dual lattice, and a smooth periodic function has almost nothing there.
-
An error bar for points that are not random
Evenly spread points integrate far better than random ones and give no error bar; random points give an error bar and integrate badly. Randomise the even points themselves — shift a lattice by a random vector, or scramble the digits of a Sobol' sequence — and both are kept: an unbiased estimate, a confidence interval from a handful of repeats, and an error that falls faster than any deterministic set's.
-
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.
-
One random path down a search tree
Before running a search that may take a week, it is worth knowing whether it will take a week or a century. Donald Knuth's answer, from 1975, is to walk down the search tree once at random, multiply the numbers of choices met on the way, and add up the products: the result is, on average, exactly the size of the tree. On the eight-queens tree one path guesses 769 against a true 2,057 and twenty thousand paths average to within a tenth of a per cent. On a tree built to hide its bulk, the same unbiased estimate is almost always wrong by a factor of thousands.
-
What a random chord is
Draw a chord of a circle at random. How often is it longer than the side of the inscribed equilateral triangle? Pick two random points on the rim and the answer is 1/3. Pick a radius and a random point on it, and the answer is 1/2. Pick a random midpoint in the disc, and the answer is 1/4. All three calculations are correct, and Bertrand published them in 1889 to warn that the phrase had no meaning. Eighty-four years later Jaynes argued that one answer is right after all.