## 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})},$
where
$x_{i} \sim g(x)$.
The code below in R performs this summation.

N=10000
cumsum=rep(0,N)
for(i in 2:N){
x=rt(1,3)
cumsum[i]=cumsum[i-1]+((exp((-0.5)*(x^2)))/dt(x,3))
}

for(i in 1:N) cumsum[i]=cumsum[i]/i
plot(cumsum[50:N],type="l")


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!