An Introduction to Importance Sampling

Importance Sampling is a Monte Carlo integration technique for getting (very accurate) approximations to integrals. Consider the integral
\int e^{-\frac{1}{2}x^{2}}dx,
and suppose we wish to approximate this without doing any calculus. Statistically speaking we want to compute the normalizing constant for a standard normal, which we know to be
\sqrt{2 \pi} \approx 2.506628.
We can rewrite the above integral as
\int \frac{e^{-\frac{1}{2}x^{2}}}{g(x)}g(x)dx,
because this is just multiplying the integrand by 1. One can now make the observation that
\int \frac{e^{-\frac{1}{2}x^{2}}}{g(x)}g(x)dx=\mathbb{E}\left[\frac{e^{-\frac{1}{2}x^{2}}}{g(x)} \right],
and realise that
\mathbb{E}\left[\frac{e^{-\frac{1}{2}x^{2}}}{g(x)} \right] \approx \frac{1}{n}\sum_{i=1}^{n} \frac{e^{-\frac{1}{2}x_{i}^{2}}}{g(x_{i})},
x_{i} \sim g(x).
The code below in R performs this summation.

for(i in 2:N){

for(i in 1:N) cumsum[i]=cumsum[i]/i

Importance Sampling Normalizing Constant
At n=10000 the normalizing constant given by importance sampling is 2.516303. Increasing n to n=100000 the normalizing constant is 2.505983

  • Silvia

    Very neat!