Importance Sampling

Importance sampling estimates expectations by drawing from a cleverly chosen distribution and reweighting, cutting variance for rare-event and tail problems.

The estimator

To estimate E_p[h(X)] when sampling from p is inefficient, draw samples from a proposal q and reweight: E_p[h(X)] = E_q[h(X) p(X)/q(X)]. The ratio w(X) = p(X)/q(X) is the importance weight. A good proposal places samples where h(X)p(X) is large, so few samples carry most of the information.

Rare events

Kronos motion — uncertainty

For a failure probability where the event is very unlikely under p, crude Monte Carlo wastes almost all samples on non-failures. Choosing q to oversample the failure region and reweighting can reduce the number of samples needed by orders of magnitude while remaining unbiased.

python

import numpy as np
x = q.rvs(N)
w = p.pdf(x) / q.pdf(x)
est = np.mean(w * h(x))
# effective sample size diagnostic
ess = w.sum()**2 / np.sum(w**2)

Choosing the proposal

The optimal proposal is proportional to |h(x)| p(x), but that requires knowing the answer. Practical choices shift or scale p toward the important region, or adapt the proposal iteratively (adaptive importance sampling, cross-entropy method). A poor proposal that misses the important region gives a badly biased-looking, high-variance estimate.

Diagnostics

Effective sample size: if a few weights dominate, the estimate is unreliable
Weight histogram: heavy tails signal a mismatched proposal
Variance of the weighted estimator, tracked as samples grow

Cautions

In high dimensions weights degenerate: one sample can carry nearly all the weight, collapsing the effective sample size to one. Importance sampling is most reliable in low to moderate dimension or combined with dimension reduction. When it works, it is the backbone of efficient reliability and rare-event estimation.