Sampling where the answer lives

The rate cannot be improved, whatever the needles suggested. Averaging $N$ independent things gives an error proportional to $1/\sqrt N$, and no rearrangement of independent sampling changes the exponent.

What can be changed is the number in front. The error is $\sigma/\sqrt N$, and $\sigma$ is a property of the estimator rather than of the problem — two different estimators of the same quantity can have wildly different spreads. Halving $\sigma$ is worth as much as quadrupling $N$, and unlike quadrupling $N$ it is free.

The reweighting #

Suppose the integral wanted is $\int_0^1 f(x)\,dx$. The plain estimator draws $x$ uniformly and averages $f(x)$, because the average of $f$ over a uniform draw is the integral.

Now draw from some other density $q$ instead, one that puts its draws where $f$ is large. The average of $f(x)$ under that density is not the integral — it is weighted towards the peak. But the average of $f(x)/q(x)$ is:

$$\mathbb{E}_q\!\left[\frac{f(X)}{q(X)}\right] = \int_0^1 \frac{f(x)}{q(x)}\,q(x)\,dx = \int_0^1 f(x)\,dx.$$

The $q$ cancels. Dividing each sample by how likely it was to be drawn undoes the bias exactly, whatever $q$ is, provided $q$ is positive everywhere $f$ is.

That is the whole method, and its correctness is one line. What is not one line is whether it helps.

Whether it helps #

The variance of the reweighted estimator is

$$\operatorname{Var}_q\!\left[\frac{f}{q}\right] = \int \frac{f(x)^2}{q(x)}\,dx - \left(\int f\right)^2,$$

and the second term does not depend on $q$, so minimising the variance means minimising $\int f^2/q$.

Read that integral as a statement about where to put the draws. Where $q$ is small, $f^2/q$ is large — so a region where the integrand is substantial and the sampling is thin contributes enormously to the variance. Where $q$ is large the contribution is small. The variance is dominated by the places the proposal neglects and the integrand does not.

The figure measures both halves rather than deriving them. It runs two hundred independent estimates by each method, computes the mean and the standard deviation of each cloud, and asserts three things: that the plain mean is within four standard errors of the true value, that the weighted mean is too, and that the weighted spread is less than half the plain one. The first two are the unbiasedness, checked; the third is the benefit, measured.

The proposal that would be perfect #

There is a choice of $q$ that makes the variance exactly zero, and finding out what it is explains both the power and the limits of the idea.

Take $q(x) = f(x)/\int f$ — the integrand itself, scaled to be a probability density. Then $f/q$ is the constant $\int f$ at every point, so every single draw returns the answer exactly and the variance is nil. One sample suffices.

The catch is immediate: constructing that $q$ requires $\int f$, which is the unknown. The optimal proposal is unusable for the reason that it is optimal.

That is not a dead end, though. It says precisely what a good proposal is: something shaped like the integrand, and the closer the shape the smaller the variance. All of practical importance sampling is choosing a $q$ that resembles $f$ closely enough to help and is simple enough to draw from — and the figure’s proposal is exactly that: a crude triangular approximation to a bump, drawn by inverting its own cumulative in one line, with a uniform floor mixed in for the reason the next section gives.

Where it goes badly wrong #

Importance sampling is the one variance-reduction method that can make things dramatically worse, and it is worth being explicit about how, because the failure is silent.

If $q$ has thinner tails than $f$ — if the proposal decays faster than the integrand somewhere — then $f/q$ is unbounded, and the estimator can have infinite variance. A run will then produce a sequence of reasonable-looking estimates and occasionally one enormous value that dominates everything, and the sample standard deviation, computed from a run that has not yet seen such a value, will be small and reassuring.

That is the worst kind of failure: the diagnostic is computed from the same sample as the estimate, so a sample that missed the problem reports no problem. It is the same shape as the failure noted at the end of the previous rung, made much more likely by a badly chosen proposal.

The practical rule is to make the proposal’s tails heavier than the integrand’s, which costs a little efficiency in the middle and removes the possibility of an unbounded weight. A cautious proposal is worth much more than a well-tuned dangerous one.

That rule is why the proposal drawn here is a triangle plus a flat floor rather than a bare triangle. A bare triangle is zero outside its base, so it fails the coverage condition and biases the answer; a triangle stretched across the whole interval has a density falling to nothing at the ends, so the weights are unbounded and the variance is infinite. Mixing in a small uniform component fixes both — the proposal is positive everywhere and bounded below, so nothing is missed and no weight can run away. The figure asserts both properties before drawing anything.

Other ways to shrink the constant #

Importance sampling is the most powerful of a family, and three siblings are worth naming because they are cheaper and safer.

Antithetic variates. For each uniform draw $u$, also use $1 - u$. If the integrand is monotone the two values are negatively correlated, so the variance of their average is less than half the variance of one — the correlation buys the extra. The cost is nothing at all, and the method works whenever the integrand is roughly monotone in each coordinate. It is the one place in this subject where dependence between samples is deliberately introduced and is unambiguously helpful.

Stratification. Divide the domain into pieces and draw a fixed number of points from each, rather than letting the total fall where it will. This removes the variance due to how many points landed in each piece, leaving only the variance within pieces. It is a partial grid, and it recovers some of a grid’s advantage without paying a grid’s exponential cost — which is why it degrades gracefully with dimension where a grid does not.

Control variates. If some function $g$ close to $f$ has a known integral — a Taylor polynomial, say — estimate $\int(f - g)$ by sampling and add the known $\int g$ back. The sampled part has a much smaller spread because $f - g$ is small. This is importance sampling’s additive cousin, and it is safe: a bad $g$ helps less and cannot hurt beyond a factor.

Sampling from a density at all #

One assumption has been passed over and it is the one that limits everything here: the proposal has to be something that can be drawn from.

For the triangle-plus-floor used in these figures that is easy. Its cumulative distribution is a piecewise quadratic, which inverts in closed form, so a uniform draw becomes a draw from the proposal in a line of arithmetic. That method — invert the cumulative — works for any density whose cumulative can be written down and inverted, which is a small and useful class: exponentials, triangles, and anything piecewise linear.

Outside that class, drawing becomes its own problem. Rejection sampling is the general answer in low dimensions: draw from something easy, keep the draw with probability equal to the ratio of the target to a scaled version of the easy density, and discard otherwise. It is exact and it wastes work, and the fraction wasted grows with the dimension until it is essentially everything. It is the same wall as the grid’s, reached by a different route: an easy density and a target density in a high-dimensional space overlap in a vanishing fraction of their mass, however carefully the easy one is chosen.

That failure is what the next rung is about. When the target cannot be drawn from and rejection wastes too much, the remaining option is to give up independence and build a process that wanders into the right distribution instead — which is a considerably stranger idea and works in dimensions where nothing else does.

How much is it worth #

The right way to compare two estimators is not by variance but by variance times cost, since a method that halves the spread and takes four times as long has lost.

For importance sampling the extra cost is drawing from $q$ instead of uniformly and evaluating $q$ at each draw, which for a simple proposal is a constant factor of perhaps two. A variance reduction of a factor of four in the spread, as in the hero figure, is a factor of about seventeen in the variance and is therefore worth about eight times the sample size after the cost is paid — the difference between a calculation that finishes and one that does not.

That framing also explains why the method is not universal. When the integrand is flat, there is nothing to concentrate on and the proposal can only make matters worse; when the integrand is a spike in a high-dimensional space, finding a proposal shaped like it is as hard as the original problem. Importance sampling works in the middle: where the integrand’s shape is known roughly and its scale is not.

Where the weights come from, in one worked case #

It is worth following a single draw through, because the arithmetic is small and the mechanism is easy to state and easy to get backwards.

Suppose the integrand peaks at 0.25 and the proposal puts four times as much density there as a uniform draw would. A sample landing at 0.25 is therefore four times as likely under the proposal as it would have been uniformly, and its value is divided by four before being averaged in. A sample landing at 0.9, where the proposal is at its floor and much less likely than uniform, is multiplied up.

The average of the weighted values is then the same as the average of the unweighted values under a uniform draw — that is the one-line calculation above — but the individual contributions are far more equal. Under uniform sampling one draw in twenty lands on the peak and contributes almost everything while the rest contribute nothing; under the proposal most draws land on the peak and each contributes a quarter of what it would have.

Equalising the contributions is the whole of variance reduction. The variance of an average is large exactly when a few terms dominate, and a proposal shaped like the integrand is a way of arranging for no term to dominate. The perfect proposal makes every contribution identical, which is why its variance is zero, and why it is unavailable.

A name that describes the wrong half #

The method’s name points at the sampling and the interesting part is the division.

Importance sampling suggests that the trick is to sample the important places, and sampling the important places on its own would be straightforwardly wrong — it would produce an estimate biased towards wherever the sampling was concentrated. What makes it work is the second half: every sample is divided by how likely it was, so a place sampled ten times too often contributes a tenth as much each time.

The two halves cancel exactly, and neither is any use alone. Concentrating without reweighting is a biased estimate; reweighting without concentrating is the plain estimator with extra arithmetic. It is the combination that leaves the answer where it was and moves the noise, and the name mentions only one of them.

That is worth noticing because the same shape appears elsewhere under other names. Rejection sampling concentrates and then discards; a Metropolis chain concentrates and then accepts or refuses. In every case a deliberate distortion is introduced and then exactly undone, and the benefit comes from what happens in between.

What the picture cannot show #

The strip plot shows two hundred estimates and the claim is about the distribution they were drawn from. A cloud that looks tight is a sample that happened to be tight, and the assertion in the figure — that the weighted spread is less than half the plain one — is a statement about these two hundred, from which the statement about the estimators is an inference.

The infinite-variance failure cannot be drawn at all, because a figure showing it would show a hundred and ninety-nine reasonable points and one off the page, and would be indistinguishable from a figure with a bug in it. Every estimator drawn here has a proposal with heavier tails than its integrand, deliberately, so the dangerous case is described and not shown.

And the whole essay is in one dimension, where nobody needs any of this. The methods matter in dimensions where a picture is impossible, and the one-dimensional pictures are analogies for a situation whose difficulty is precisely that it cannot be looked at.

The ladder from here #

Rungs above: Markov chain methods, for when the target can be evaluated but not drawn from. Adaptive importance sampling, which improves the proposal as it goes. Multiple importance sampling, which combines several proposals and is what makes light transport tractable. Rare-event simulation, where the quantity of interest has probability $10^{-9}$ and no plain method will ever see it. And the Rao–Blackwell construction, which reduces variance by integrating out whatever part of the randomness can be handled exactly.

The move in one sentence #

The estimator was changed and the quantity was not.

That is worth stating on its own, because it is easy to read reweighting as an approximation or a trick and it is neither. Two estimators with the same expectation are two ways of computing the same number, and choosing between them is a question about their spread alone. Nothing has been assumed about $f$, no error has been introduced, and the entire benefit comes from noticing that unbiasedness leaves a great deal of freedom and spending it.

The same freedom is what a bound on how far from the average a thing can be is measuring and what a control variate spends. Whenever a quantity can be written as an average in more than one way, the ways will differ in variance, and picking among them costs nothing.