variance reduction
Monte Carlo's error bar is s / sqrt(N): you can shrink it by raising N (taking more samples, which is slow and costly because of the sqrt) or by shrinking s, the variability of what you are averaging. Variance reduction is the family of clever tricks that attack the s instead of the N — rewriting the estimator so each sample carries more information, buying you the same accuracy from far fewer samples, or far better accuracy from the same budget.
The key insight is that there are usually MANY unbiased estimators of the same quantity — different random recipes that all average to the right answer — and they differ wildly in variance. Variance reduction chooses or designs a low-variance one. The main techniques each exploit some structure you know in advance: IMPORTANCE SAMPLING draws more samples where the integrand is large, then re-weights to stay unbiased; CONTROL VARIATES subtract off a correlated quantity whose exact mean you know, cancelling much of the noise; ANTITHETIC VARIATES pair each sample with a mirror-image one (use u and 1 - u) so their errors partly cancel; and STRATIFIED SAMPLING splits the domain into strata and samples each separately, preventing random clumping and gaps. Each can cut the variance by a large factor, occasionally by orders of magnitude.
Why it matters: because the error falls only as 1/sqrt(N), reducing the variance by a factor of 100 is as good as taking 100 times more samples — and far cheaper. Variance reduction is therefore the difference between a Monte Carlo calculation that finishes overnight and one that would take a year. The honest caveats: these methods require knowing something about the problem (a good proposal density, a correlated control quantity, a sensible stratification), a poor choice can backfire and INCREASE the variance, and one must be careful to keep the estimator UNBIASED — a clever weighting that quietly shifts the expected value trades a random error for a systematic one, which is worse.
Estimate the integral of e^x over [0, 1] (true value e - 1 = 1.718). Plain Monte Carlo with N samples has some variance. The antithetic version pairs each u with 1 - u and averages (e^u + e^(1-u))/2; because e^x is monotone, the pair's errors anticorrelate and the variance drops by more than half for free — the same accuracy at half the work.
Attack the variance, not the sample count — far cheaper than brute force.
Variance reduction relies on knowing structure in advance; a careless choice can RAISE the variance instead. And the cardinal rule is to keep the estimator unbiased — a trick that shifts the expected value swaps a shrinking random error for a permanent systematic one.