Importance sampling

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 $f$ as the average of the function evaluated at a set of points $x_{1},...,x_{N}$.

$\int _{0}^{1}f(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).$

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

$\int _{0}^{1}{\frac {f(u)}{g(u)}}g(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}{\frac {f(y_{i})}{g(y_{i})}},$

where the $y_{i}$ now follow a $g$ distribution.

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