Importance sampling · subhransu.fyi

Suppose we want the expectation of $f$ under $p$ , but sampling from $p$ is awkward: it is expensive, it is only known up to a constant, or we already have samples from something else. Multiply and divide by any $q$ that covers the support of $p$ and the expectation does not change:

\mathbb{E}_p[f(x)] = \int f(x)\,p(x)\,dx = \int f(x)\,\frac{p(x)}{q(x)}\,q(x)\,dx = \mathbb{E}_q[f(x)\,w(x)],

with the importance weight $w(x) = p(x)/q(x)$ .

Samples are drawn from $q$ (ticks) and reweighted by $p(x)/q(x)$ . Here $f$ is the indicator of the shaded region, so $q$ is placed where $f$ is nonzero.

Every sample carries the weight $w(x) = p(x)/q(x)$ . When $q$ puts little mass where $p$ puts a lot, a rare sample lands with a huge weight and the variance of the estimate explodes. The animation below draws samples one at a time and tracks the running estimate.

Samples arriving one at a time on the left, the running estimate of $P_p(x > 1)$ on the right.

The same two densities drawn with manim, rendered once per theme.