Variance reduction

Summary

Variance reduction is the family of techniques that make a Monte Carlo method more accurate for the same computing effort. The error of a plain Monte Carlo estimate with $n$ samples is about $\sigma/\sqrt{n}$, where $\sigma^2$ is the variance of one sample. The rate $n^{-1/2}$ is fixed for plain random sampling. So the gains come from replacing the sampled quantity by another with the same mean and a smaller variance. Halving $\sigma$ saves a factor of four in the number of samples.