5.8 Importance sampling

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §5.8. Rewritten in original wording. Continues 5.7 Monte Carlo variance reduction. Labs: 5.8b Importance-sampling labs.

Reweight the measure

Write the integral against a weight (density) $w$ that you choose, average $f/w$ under samples from $w$, then draw those samples by rejection or inverse CDF. Walk $I=\langle f/w\rangle_w$, the flattening choice $w\propto f$, von Neumann’s accept test, and the $w=2(1-x)$ map — pick the matching equation at each step.

Flatten $f/w$

Uniform sampling is the special case $w=\mathrm{const}$. Importance sampling is the natural next step when you can sample from a peaked $w$ that matches the integrand’s shape.

von Neumann rejection sampling

How do you draw $x\sim w$ when $w$ is not a standard distribution? Enclose $w$ in a box of height $w_0\ge w(x)$; the guide’s rejection step keeps points under the curve. Accepted abscissae are distributed according to $w$. The acceptance rate is the area under $w$ over the box area.

Accepted samples feed an importance estimate $\langle f/w\rangle$. When $w$ is harder to sample by inversion or rejection, Metropolis algorithms (Chapter 17) generate correlated draws from $w$ without needing a tight enclosing box — mentioned here only as the later generalization.

Inverse-CDF shortcut

If the CDF of $w$ is invertible, you can skip rejection: draw $u\sim U[0,1)$ and set $x=F_w^{-1}(u)$. Example on $[0,1]$: $w(x)=2(1-x)$ — the guide’s last step — after which you average $e^{-x}/w(x)$.

Quiz

Importance sampling

1 / 3

Importance sampling writes I as…

Pick an answer to see if you are right.

Next: 5.8b Importance-sampling labs.