Generator

How fast each way of averaging closes in, as the dimension grows

A generator in the probability library, called 39 times across 8 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

sample is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

A walk that visits each state as often as its weight says

How fast each way of averaging closes in, as the dimension grows

Error against the number of points for three randomised methods

Ten plain Monte Carlo runs against ten random shifts of one lattice

64 Sobol' points, and the same points scrambled

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

row 0 of the transition matrix adds to one ×20
every box of width 1/2^0 and height 1/2^6 holds exactly one point ×16
the grid's error in 4 dimensions falls like N^(−2/4) ×5
in 2 dimensions the share crossed falls like N to the power −1/2 ×4
every one of the 16 boxes of side 1/4 holds exactly one point ×3
in 2 dimensions the grid is the faster ×2
in 8 dimensions the grid is the slower ×2
a Fibonacci lattice between 13 and 377 points ×1
a power of two between 16 and 256 ×1
a tilted line and a circle both near −3/4 ×1
and a run of the chain reproduces it to within a twentieth ×1
and at four dimensions the two rates meet ×1
and holds no negative probability ×1
and is between 5 and 400 sharp ×1
and is positive everywhere on the interval, so no weight is unbounded ×1
and is repeated between 40 and 800 times ×1
and is run for between 2,000 and 200,000 steps ×1
and so does every row ×1
and so is the weighted one — neither is biased ×1
and the Halton points' falls faster than that ×1
and the random one falls like N^(−1/2), whatever the dimension ×1
and the weighted one is appreciably quieter ×1
as much probability flows from i to j as back again ×1
at sixteen thousand points the smoothed estimate is over a hundred times better ×1
away from the axes the advantage over random points grows only like N to the quarter ×1
between 32 and 2,048 points are drawn ×1
both intervals are consistent with the true value ×1
each dimension is a whole number between 1 and 12 ×1
each estimate uses between 50 and 5,000 draws ×1
every column of width 1/N holds exactly one lattice point ×1
in 1 dimension the grid is the faster ×1
on an integrand that is not periodic the lattice loses most of its advantage ×1
Owen scrambling beats a random digital shift and approaches N to the minus three halves ×1
plain Monte Carlo falls like N to the minus one half ×1
plain sampling near −1/2 ×1
random points' error grows like the radius for a small circle ×1
random sampling's error falls like one over the square root of N ×1
smooth near −3/2, a jump along an axis near −1 ×1
so a step leaves the target distribution where it was ×1
the axes are far cheaper than every angle between them ×1
the chain has between 5 and 24 states ×1
the discarded start is shorter than the run ×1
the discrepancy is probed on a grid of between 40 and 300 boxes a side ×1
the grid's error in 1 dimension falls like N^(−2/1) ×1
the Halton points are more evenly spread than the random ones on this measure ×1
the integrand is periodic, plain, or periodised ×1
the jump costs half the exponent, and integrating it out restores it ×1
the lattice rule's error on a smooth periodic integrand falls about like 1/N² ×1
the line crosses between √N and 2√N of the N boxes ×1
the peak sits inside the interval ×1
the plain average is centred on the answer ×1
the points to fit a slope through are not all at one place ×1
the proposal is a probability density ×1
the random points' discrepancy falls like one over the square root ×1
the rule sees a Fourier mode exactly when its frequency is on the dual lattice ×1
the scrambled error grows like the square root of the circle's length ×1
the seed is a whole number the drawing can be made from ×1
the shifted lattice's interval is far narrower ×1
the spread is measured over between 4 and 200 runs ×1
the sweep runs over between 3 and 8 sizes ×1
the sweep runs to between 2^8 and 2^18 points ×1
the view is one the family draws ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Probability

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

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.

Probability

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.

Probability

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

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

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.

Applied

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.

Probability

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.

The whole library · What the figures prove