Making Each Sample Count

Last timeHow Far Off Is It

Brute force buys precision at a terrible exchange rate. Three standard tricks reduce the spread of what is being averaged instead, which is worth far more than extra draws.

The previous lesson ended with a discouraging table: each extra digit costs a

hundred times the work.

That table assumed the only lever is the number of draws. It is not even the

better lever.

The two factors

The error is the spread of one computed value divided by the square root of

the number of draws. Everything so far has pushed on the denominator, which is

the expensive one. This lesson pushes on the numerator.

FIG 1Three techniques, and when each one earns its keep

	helps a rare event?	helps a smooth quantity?	extra cost per draw	risk if misapplied
more draws	0.0	1.0	1.0	0.0
sampling where it matter	1.0	0.0	1.2	1.0
mirrored pairs	0.0	1.0	1.0	0.0
subtracting a known quan	0.0	1.0	1.1	0.0

Read the first row as the baseline: more draws helps everything a little and rare events not at all, since a million draws of a one in a million event still produce about one success. The marked row is the one that changes what is possible rather than what is affordable, and it is also the only one carrying real risk, because a badly chosen replacement distribution gives a confident wrong answer rather than a noisy one. The other two are safe, nearly free, and worth applying by default wherever the quantity varies smoothly with its input.

FIG 2Drawing from somewhere else, and correcting for it

: the true distribution, under which the interesting region is almost never visited
: the distribution actually drawn from, chosen to visit that region often
: the ith draw, taken from q rather than from p
: the weight: how much this draw was over favoured, which the average divides back out
: the quantity computed from one draw, unchanged by any of this

The two expectations are equal exactly, not approximately, which is why the estimate on the right is centred on the same answer. The whole benefit is that drawing from q produces useful draws where drawing from p produced almost none. The requirement hiding in the formula is that q must be able to reach everywhere p can: anywhere q is zero and p is not, those draws never occur, their contribution silently vanishes, and the estimate comes back too small with a perfectly healthy looking error bar.

FIG 3A one in a hundred thousand event, estimated twice

step	approach	draws	useful draws	estimate	typical error
1	draw from the true distribution	100 000	about 1	1 in 100 000, or 0	about as large as the answer
2	draw from the true distribution	10 000 000	about 100	close	about ten per cent
3	shift the distribution towards the region	10 000	about 4 000	close	about two per cent
4	the comparison	a thousand times fewer draws		same answer	five times better
5	a bad replacement that misses part of the region	10 000	about 4 000	too small, confidently	small and meaningless

5 steps

The first two rows are the brute force route and show why rare events are hard: the precision follows the count of successes, so ten million draws are needed before the answer has one reliable digit. The third row gets a better answer for a thousandth of the work. The last row is the warning that comes with the technique, and it is not hypothetical: a replacement distribution that never reaches part of the interesting region produces an answer that is too small and an error bar that looks fine, which is the most dangerous combination in this course.

FIG 4Mirrored pairs and a known related quantity, measured

python

import numpy as np
rng = np.random.default_rng(5)
n = 20_000

u = rng.random(n)
print(float(np.std(np.exp(u), ddof=1) / np.sqrt(n)))        # baseline

h = rng.random(n // 2)
paired = (np.exp(h) + np.exp(1 - h)) / 2                     # mirrored pairs
print(float(np.std(paired, ddof=1) / np.sqrt(n // 2)))       # about half the error

v = rng.random(n)
plain = np.exp(v)
adjusted = plain - 1.69 * (v - 0.5)                          # v has known average 0.5
print(float(np.std(adjusted, ddof=1) / np.sqrt(n)))          # much smaller again
print(float(np.mean(plain)), float(np.mean(adjusted)))       # same answer, e minus one

Each block prints a baseline error and then the error after the technique, so the gain is measured rather than claimed. The mirrored pairs block uses the same number of underlying random numbers in both cases, which is the fair comparison, and roughly halves the error because the quantity rises steadily with its input. The known quantity block subtracts off a simpler function whose exact average is a half, which cancels most of the shared noise. Both are three lines, both are safe, and both are worth trying before paying for four times the draws.

Two cheap tricks

The multiplier in the last block is chosen so the two quantities cancel as

fully as possible, and it can be estimated from a short pilot run rather than

derived. Getting it slightly wrong costs a little of the benefit and never

biases the answer, which makes the technique comfortable to apply.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Making Each Sample Count

The two factors

Two cheap tricks

1 more paragraph to go

This is the reading half

Read alongside