Importance Sampling

Imagine that we want to sample the function $f(x)=e^{-x^2}$ in the interval $[0,1]$. It is evident that most of our points will fall in the region where the value of $f(x)$ is very small, and therefore we will need a large number of values to achieve a decent accuracy. A way to improve the measurement by reducing the variance is obtained by ``importance sampling''. As the name says, the idea is to sample the regions with larger contributions to the integral. For this goal, we introduce a probability distribution $P(x)$ normalized in the interval of integration

$$\int _a^b {P(x)dx}=1.$$

Then, we can rewrite the integral of $f(x)$ as

$$I=\int _a^b{\frac{f(x)}{P(x)}P(x)dx}$$ (272)

We can evaluate this integral, by sampling according to the probability distribution $P(x)$ and evaluating the sum

$$I(N)=\frac{1}{N} \sum_{i=1}^N \frac{f(x_i)}{P(x_i)}.$$ (273)

Note that for the uniform case $P(x)=1/(b-a)$, the expression reduces to (270).

We are free to choose $P(x)$ now. We wish to do it in a way to reduce and minimize the variance of the integrand $f(x)/P(x)$. The way to to this is picking a $P(x)$ that mimics $f(x)$ where $f(x)$ is large. if we are able to determine an apropiate $p(x)$, the integrand will be slowly varying, and hence the variance will be reduced. Another consideration is that the generation of points according to the distribution $P(x)$ should be a simple task. As an example, let us consider again the integral

$$I=\int _0^1 {e^{-x^2}dx}.$$

A reasonable choice for a weigh function is $P(x)=Ae^{-x}$, where $A$ is a normalization constant.

Notice that for $P(x)=f(x)$ the variance is zero! This is known as the zero variance property.