Importance sampling
From Academic Kids
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 <math>f<math> as the average of the function evaluated at a set of points <math>x_1, ..., x_N<math>.
- <math> \int_a^b f(u)\,du = \mathrm{E}\{f(X)(b-a)\}\quad (X\sim unif(a,b))\approx \left[ \frac{1}{N}\,\sum_{i=1}^N f(x_i) \right] \left( b-a \right), <math>
where <math>x_1, ..., x_N<math> were drawn from a uniform distribution over the inter val <math>[a,b)<math>, and <math>\mathrm{E}\{.\}<math> denotes the expected value. 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
- <math> \int_a^b \frac{f(u)}{g(u)} g(u) \,du \approx \left[ \frac{1}{N}\,\sum_{i=1}^N \frac{f(y_i)}{g(y_i)} \right], <math>
where the <math>y_i<math> now follow a <math>g<math> distribution. A popular method to sample from the <math>g<math> distribution is Metropolis sampling.
If <math>f(u)/g(u)<math> has a smaller variance than <math>f(u)<math>, the new sequence will converge faster.
