Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 · Variance Reduction

Importance Sampling

Sample where the action is and reweight. Learn importance sampling, the likelihood ratio, effective sample size and rare-event estimates in Python.

Suppose you want the probability that a standard normal variable exceeds 4. The true value is about 3.2 × 10⁻⁵: roughly 3 in 100,000. A plain Monte Carlo run with a million draws sees only about 30 hits, so the estimate is noisy; with 10,000 draws you will probably see none at all. The method wastes nearly all its effort on draws that do not matter.

Importance sampling fixes this by drawing from a different distribution that visits the interesting region often, then correcting for the change with weights. It is the most powerful variance reduction idea for rare events, and it is also the engine behind many modern algorithms.

The identity

We want μ = E_p[h(X)] = ∫ h(x) p(x) dx, where p is the target density. Pick a proposal density q that is positive wherever h(x)p(x) is nonzero. Then:

Text
μ = ∫ h(x) · [p(x)/q(x)] · q(x) dx = E_q[ h(X) · w(X) ],   w(x) = p(x)/q(x)

So draw X₁, …, X_N from q, compute the weights wᵢ = p(Xᵢ)/q(Xᵢ), and average h(Xᵢ)·wᵢ. The weight w is called the likelihood ratio: it down-weights draws that q over-produces and up-weights those it under-produces.

flowchart LR
  A["Draw X from q"] --> B["Weight w = p(X) / q(X)"]
  A --> C["Evaluate h(X)"]
  B --> D["Average of h(X) * w"]
  C --> D

Sampling from q but correcting with p/q keeps the estimate unbiased.

The ideal proposal is q*(x) ∝ |h(x)| p(x), which would give zero variance for nonnegative h. You cannot sample from it directly (its normalizing constant is the answer you are looking for), but it tells you where to aim: put draws where h(x)p(x) is large.

A rare normal tail

For P(Z > 4) use h(x) = 1 when x > 4, and a proposal N(4, 1), centered on the boundary. The weight is p(x)/q(x) = exp(−x²/2) / exp(−(x−4)²/2) = exp(−4x + 8).

Python Estimating a normal tail probability

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The importance estimate lands within a few percent of the exact value, while the plain estimate is usually 0 or a multiple of 1e-5.

Choosing the shift, and checking weights

A good proposal moves the center, not too far. Too little shift and you remain starved of hits; too much and the weights become wildly uneven, so a few draws dominate. A diagnostic is the effective sample size:

Text
ESS = (Σ wᵢ)² / Σ wᵢ²

If the weights are all equal, ESS = N. If one weight dominates, ESS ≈ 1. Here we try several shifts and measure the spread of repeated estimates.

Python How far should we shift the proposal?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see shift 0 perform worst (it is plain Monte Carlo), with shifts near 4 performing far better. The ESS of the raw weights drops as the shift grows, because the weights spread out; the usable information is in the weights of the draws that hit the event.

Self-normalized importance sampling

Often p is known only up to a constant (this is typical in Bayesian problems). Then use:

Text
μ̂ = Σ h(Xᵢ) wᵢ / Σ wᵢ

with unnormalized weights wᵢ = p̃(Xᵢ)/q(Xᵢ). This version is slightly biased but very useful, and it is the bridge to Markov chain Monte Carlo.

The proposal must have heavier tails than the target. If q decays faster than p·h, the weights can have infinite variance, and the estimate may look stable for a long time and then jump.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the weight in importance sampling?

    We sample from q but want an expectation under p, so each draw is multiplied by p(x)/q(x).
  2. 2. Why does importance sampling help with rare events?

    Draws land in the rare region often, and the weights restore the correct probability.
  3. 3. An effective sample size close to 1 means:

    ESS = (sum w)^2 / sum w^2 is near 1 when a single weight carries almost all the mass.
  4. 4. Which proposal property is dangerous?

    Lighter tails make p/q grow without bound in the tails, giving huge or infinite variance.

Summary

  • Sample from q, multiply by w = p/q, and average: the estimator is unbiased.
  • The ideal q is proportional to |h|·p; aim draws where that product is large.
  • Check weights with the effective sample size, and keep q heavier-tailed than p.
  • Self-normalized weights handle targets known only up to a constant.

Next: Stratified Sampling