🎯 Monte Carlo Importance Sampling

Estimate rare-event probabilities efficiently. Importance sampling: E[f(X)] = E_q[f(X)w(X)] where w = p/q is the likelihood ratio. Optimal q* ∝ |f|p minimizes variance. Compare naive vs IS.

ProbabilityInteractive
p(x)=N(0,1) · q(x)=IS proposal · importance region · R resample · I toggle

How it Works

To estimate P(X > t) for X ~ N(0,1) with large t, naive Monte Carlo rarely hits the tail. Importance sampling draws samples from a shifted Gaussian q = N(μ_q, σ_q²) centred near the threshold t. Each sample x_i gets reweighted by w(x_i) = p(x_i)/q(x_i):

p(x) = N(x; 0, 1) (target) q(x) = N(x; μ_q, σ_q²) (proposal) w(x) = p(x)/q(x) (likelihood ratio) IS estimate: P̂ = (1/N) Σ 1[x_i>t] · w(x_i) x_i ~ q ESS = (Σw_i)² / Σw_i² Var(P̂_IS) ≈ Var_q[1[x>t]·w] / N

The optimal proposal is q*(x) ∝ 1[x>t]·p(x) — a truncated Gaussian on (t,∞). Shifting μ_q to t reduces variance by many orders of magnitude for large t. The ESS (effective sample size) measures efficiency.

Frequently Asked Questions

What is importance sampling?

Importance sampling (IS) is a variance reduction technique that samples from a proposal distribution q instead of the target p. The estimator reweights samples by the likelihood ratio w(x) = p(x)/q(x).

Why is importance sampling useful for rare events?

For rare events (e.g., P(X > 5) for a standard normal X), naive Monte Carlo draws almost no samples from the important tail region. IS shifts the proposal to the region of interest, collecting many more relevant samples.

What is the likelihood ratio (importance weight)?

The importance weight is w(x) = p(x)/q(x). Each sample x drawn from q is multiplied by w(x) to compensate for sampling from the wrong distribution. The IS estimator is (1/N)Σ f(x_i)·w(x_i).

What is the optimal proposal distribution?

The optimal proposal is q*(x) ∝ |f(x)|·p(x), which makes the IS estimator have zero variance. In practice, the optimal q* is not known exactly but can be approximated by shifting/scaling to cover the important region.

What is self-normalised importance sampling?

Self-normalised IS divides by the sum of weights: μ̂_SN = Σ f(x_i)w(x_i) / Σ w(x_i). This makes the estimator consistent even when q is only known up to a normalisation constant, but introduces a small bias.

What is effective sample size (ESS) in IS?

ESS = (Σw_i)² / Σw_i² measures how many equivalent i.i.d. samples from p the IS estimate corresponds to. ESS ≈ N means very low variance; ESS ≪ N indicates weight degeneracy.

What causes weight degeneracy?

Weight degeneracy occurs when a few samples receive nearly all the weight. It happens when p has heavier tails than q, causing extreme weights for occasional samples in the mismatched region.

How is importance sampling used in machine learning?

IS is used in variational inference (IWAE bound), policy gradient methods (off-policy learning), Bayesian model selection, and sequential Monte Carlo (particle filters).

What is the variance reduction factor of IS?

IS reduces variance when Var_q[f·w] < Var_p[f]. The variance ratio equals ESS/N. For the optimal q*, variance is 0. For a Gaussian shifted to cover the rare region, variance reduction can be exponential in the threshold.

What are stratified sampling and control variates?

Stratified sampling divides the input domain into strata and samples each proportionally, reducing variance. Control variates subtract a correlated known-expectation function to reduce estimator variance. Both complement importance sampling.

About this simulation

This simulation estimates the rare-event probability P(X>t) for a standard normal X two ways side by side: naive Monte Carlo, which draws from N(0,1) directly and rarely lands past the threshold, and importance sampling, which draws from a shifted proposal q=N(μ_q,σ_q²) centred near the threshold and reweights every sample by the likelihood ratio w(x)=p(x)/q(x) to correct the bias.

🔬 What it shows

Overlaid target density p(x) and proposal density q(x) curves with the tail region shaded, a scatter of sampled points coloured by their importance weight, plus a stats panel comparing true, naive, and IS probability estimates alongside their standard errors and effective sample size.

🎮 How to use

Set the rare-event threshold t, the IS proposal's shift μ_q and width σ_q, and the sample count N with the sliders, click Resample to redraw, and press Toggle View (or the I key) to switch to a sorted bar chart of the raw importance weights.

💡 Did you know?

Set the threshold to t=5σ or higher and watch the Naive MC estimate stat collapse to exactly 0.000e+0 no matter how many samples you add — with N(0,1), P(X>5) is about 1 in 3.5 million, so a run of even 10,000 naive samples essentially never lands in the tail, while shifting μ_q near 5 lets importance sampling estimate that same tiny probability accurately from a fraction of the samples.

Frequently asked questions

Why does the Naive MC estimate often show exactly 0 while IS shows a real number?

Naive Monte Carlo counts how many of N draws from N(0,1) actually land above threshold t; for large t this probability is astronomically small, so with a few thousand samples the count is very likely to be exactly zero — importance sampling instead draws from q, centred near t, so nearly every sample lands in the region of interest and gets reweighted down by w(x), producing a usable non-zero estimate.

What happens if I set μ_q far away from the threshold t?

If the proposal's centre μ_q drifts far from t, samples from q stop landing efficiently in the tail region past t, and the few that do carry extreme importance weights — this is exactly the weight degeneracy the Toggle View bar chart is built to expose, where a handful of samples end up carrying almost all the statistical weight.

Why does the ESS (effective sample size) sometimes read much lower than N?

ESS = (Σw_i)²/Σw_i² shrinks toward 1 whenever the importance weights become highly unequal — a mismatch between where q actually places its samples and where the tail event lives — so a low ESS relative to N is a direct, computable warning sign that your chosen proposal isn't well matched to the target region.

Why does increasing σ_q sometimes hurt rather than help?

A wider proposal spreads samples over a larger range, diluting how many actually land near the threshold and increasing the spread of importance weights for the ones that do — the ideal σ_q is usually narrow enough to concentrate samples right around t without collapsing to a near-deterministic point mass.

Is there a mathematically optimal choice for the proposal q?

Yes — the zero-variance proposal is q*(x) ∝ 1[x>t]·p(x), a Gaussian truncated to exactly the tail region above t; this simulation's shifted-Gaussian proposal is a practical approximation to that ideal, and setting μ_q close to t (with a moderate σ_q) is the closest you can get to it using an untruncated normal.