Importance sampling - Definition and Overview

Importance sampling is a variance reduction technique that can be used in the Monte Carlo method. The Monte Carlo method is used to approximate the integral of a function <math>f<math> as the average of the function evaluated at a set of points <math>x_1, ..., x_N<math>.

<math> \int_a^b f(u)\,du \approx \left[ \frac{1}{N}\,\sum_{i=1}^N f(x_i) \right] \left( b-a \right) . <math>

If we have additional knowledge about what f looks like and can find a function g similar to f, we can rewrite the integral as

<math> \int_a^b \frac{f(u)}{g(u)} g(u) \,du \approx \left[ \frac{1}{N}\,\sum_{i=1}^N \frac{f(y_i)}{g(y_i)} \right] \left( b-a \right), <math>

where the <math>y_i<math> now follow a <math>g<math> distribution. A popular method to sample from the <math>g<math> distribution is Metropolis sampling.

If <math>f(u)/g(u)<math> has a smaller variance than <math>f(u)<math>, the new sequence will converge faster.