Importance sampling is a technique in mathematical statistics to improve the results obtained from random sampling, for example in Monte Carlo computations?.

Details

Consider a real function $f(x, y)$ of two real variables that looks like this:

When we try to calculate the integral of this function on the interval $[-1, 1] \times [-1, 1]$, with deterministic algorithms or using a Monte Carlo integration, then our algorithm will spend a lot of time evaluating $f$ at points where it is near $0$. The idea of importance sampling is that one should try to concentrate on the regions of importance, in this case on the regions where the function $f$ is significantly different from $0$. When we perform a Monte Carlo integration, we could for example estimate a probability distribution $g$, which is concentrated on the area where $f$ is different from $0$, and draw our samples from this distribution instead from the uniform distribution of $[-1, 1] \times [-1, 1]$.

Let’s consider a slightly more general example: Let $\pi$ be a probability distribution (a density with respect to the Lesbegue measure) that is complicated, and let’s say that we are interested in calculating

$\mu := E_{\pi}(h) = \int_{\mathbb{R}} h(x) \pi(x) d x$

Draw $x_1, ..., x_n$ from a trial distribution $g$ and calculate the importance weight

$w_j := \frac{\pi (x_j)}{g(x_j)}$

Then approximate $\mu$ by

$\hat{\mu} := \frac{\sum w_i h(x_i)}{\sum w_i}$

This is a biased estimator. If it is possible to guess $g$ in such a way that it is easily evaluated, that $\frac{\pi}{g}$ is known up to a multiplicative constant and such that $g$ is close to $\pi h$, then this estimator will be easy to calculate and have a small mean square error in comparison with the “vanilla” Monte Carlo estimator, that does not use a trial distribution.

References

Jun S Liu, Monte Carlo Strategies in Scientific Computing (ZMATH).