Importance sampling

Remarks

Clause 1: $\mathbb E[h(Y) p(Y)/g(Y)] = \int_{g > 0} h p = q$, since $h p = 0$ where $g = 0$. Clause 2 is the same computation for the second moment, divided by $n$ for independent samples. Clause 3 follows from the Cauchy–Schwarz inequality: $\left( \int \abs{h} p \right)^2 = \left( \int \frac{\abs{h} p}{\sqrt g} \sqrt g \right)^2 \le \int \frac{h^2 p^2}{g}$, with equality when $g$ is proportional to $\abs{h} p$. The optimal $g^*$ needs $\int \abs{h} p$, which is essentially the unknown; in practice one picks $g$ close in shape to $\abs{h} p$. Example: let $X$ be standard normal and $q = P(X > 4) \approx 3.17 \times 10^{-5}$. Plain sampling sees almost no hits. Sampling from the normal density with mean $4$ puts half the samples in the event and reduces the relative error by orders of magnitude. A badly chosen $g$ with lighter tails than $\abs{h} p$ can make the integral in clause 2 infinite, so the estimate converges very slowly and erratically.

Going deeper

For a student

This is a variance reduction technique for the Monte Carlo method, and also a change of measure: $g$ defines a new probability measure and $p/g$ is the Radon–Nikodym derivative. When $p$ is known only up to a constant, one uses the self-normalised estimator $\sum w_i h(Y_i) / \sum w_i$ with $w_i = p(Y_i)/g(Y_i)$, which is biased but consistent. The effective sample size $(\sum w_i)^2 / \sum w_i^2$ is a common diagnostic of weight degeneracy. In rare-event simulation, exponential tilting of $p$ is a standard way to build $g$, and in sequential Monte Carlo the idea is applied step by step.