Importance Sampling is a Monte Carlo integration technique for getting (very accurate) approximations to integrals. Consider the integral
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
We can rewrite the above integral as
because this is just multiplying the integrand by 1. One can now make the observation that
and realise that
where
The code below in R performs this summation.
![\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],](http://s0.wp.com/latex.php?latex=%5Cint+%5Cfrac%7Be%5E%7B-%5Cfrac%7B1%7D%7B2%7Dx%5E%7B2%7D%7D%7D%7Bg%28x%29%7Dg%28x%29dx%3D%5Cmathbb%7BE%7D%5Cleft%5B%5Cfrac%7Be%5E%7B-%5Cfrac%7B1%7D%7B2%7Dx%5E%7B2%7D%7D%7D%7Bg%28x%29%7D+%5Cright%5D%2C++&bg=ffffff&fg=000&s=0 "\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],")
![\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})},](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5Cleft%5B%5Cfrac%7Be%5E%7B-%5Cfrac%7B1%7D%7B2%7Dx%5E%7B2%7D%7D%7D%7Bg%28x%29%7D+%5Cright%5D+%5Capprox+%5Cfrac%7B1%7D%7Bn%7D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D+%5Cfrac%7Be%5E%7B-%5Cfrac%7B1%7D%7B2%7Dx_%7Bi%7D%5E%7B2%7D%7D%7D%7Bg%28x_%7Bi%7D%29%7D%2C++&bg=ffffff&fg=000&s=0 "\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})},")
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