Chapter 136

Home

Refactoring: Importance Sampling

Standard Monte Carlo samples uniformly — wasteful when most samples contribute nothing. Importance sampling samples from a distribution that concentrates on "important" regions, then weights results to correct the bias. Fewer samples, same accuracy.

Before: Uniform Sampling (wasteful)

C++ — uniform

// To estimate P(X > 5) where X ~ N(0,1):
// Most samples are near 0 — few contribute to the estimate
double count = 0;
for (int i = 0; i < N; i++)
    if (normal_sample() > 5) count++;  // rare event

After: Importance Sampling

C++ — importance sampling

// Sample from a shifted distribution (e.g., N(5,1)) and reweight
// weight = f_target(x) / f_proposal(x)
// where f_target is N(0,1) pdf, f_proposal is N(5,1) pdf

double estimate = 0;
for (int i = 0; i < N; i++) {
    double x = shifted_normal_sample(5);
    if (x > 5) {
        double weight = normal_pdf(x, 0, 1) / normal_pdf(x, 5, 1);
        estimate += weight;
    }
}
estimate /= N;

// Far fewer samples needed for rare events.