Quasi-monte carlo
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Numerical integrationDiscrepancyScramblingSobol sequenceConfidence intervalConvergence rateCurse of dimensionalityDual latticeFourier seriesLatticePeriodicityRandomness