The Azimuth Project
Importance sampling

Contents

Idea

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)f(x, y) of two real variables that looks like this:

double hill function

When we try to calculate the integral of this function on the interval [1,1]×[1,1][-1, 1] \times [-1, 1], with deterministic algorithms or using a Monte Carlo integration, then our algorithm will spend a lot of time evaluating ff at points where it is near 00. 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 ff is significantly different from 00. When we perform a Monte Carlo integration, we could for example estimate a probability distribution gg, which is concentrated on the area where ff is different from 00, and draw our samples from this distribution instead from the uniform distribution of [1,1]×[1,1][-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

μ:=E π(h)= h(x)π(x)dx \mu := E_{\pi}(h) = \int_{\mathbb{R}} h(x) \pi(x) d x

Draw x 1,...,x nx_1, ..., x_n from a trial distribution gg and calculate the importance weight

w j:=π(x j)g(x j) w_j := \frac{\pi (x_j)}{g(x_j)}

Then approximate μ\mu by

μ^:=w ih(x i)w i \hat{\mu} := \frac{\sum w_i h(x_i)}{\sum w_i}

This is a biased estimator. If it is possible to guess gg in such a way that it is easily evaluated, that πg\frac{\pi}{g} is known up to a multiplicative constant and such that gg is close to πh\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).