Back to course

Importance Sampling

Estimating a rare event by plain Monte Carlo is hopeless. To measure a probability of 10−410^{-4} with any precision you need millions of draws, and almost every one contributes nothing.

Importance sampling fixes this: sample from a distribution that visits the region of interest often, then correct for having done so.

Importance sampling
Ep[f(X)]=∫f(x)p(x)q(x)q(x) dx≈1n∑if(xi)p(xi)q(xi)E_p[f(X)] = \int f(x)\frac{p(x)}{q(x)}q(x)\,dx \approx \frac{1}{n}\sum_i f(x_i)\frac{p(x_i)}{q(x_i)}

Draw from a distribution that visits the region you care about, then correct with the likelihood ratio.

Draw from a proposal qq, and weight each sample by the importance weight p(x)q(x)\frac{p(x)}{q(x)}, which undoes the distortion. The estimator remains unbiased.

The intuition

Suppose you want the probability of a 5-sigma loss. Sampling from the true distribution, you almost never see one.

Instead sample from a distribution shifted toward the tail, so losses of that size occur frequently. Each sample is then down-weighted by how much more likely it was under qq than under pp. You get many informative samples, correctly discounted.

The rest of this lesson is for subscribers

Unlock every lesson in Advanced Topics in Probability and Statistics, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextBootstrapping

Keep reading Advanced Topics in Probability and Statistics

35 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them