The rate is fixed — so attack the constant
The previous guide left you with one law, both liberating and frustrating: a Monte Carlo estimate's error shrinks like O(1/sqrt(N)), no matter the dimension. Liberating, because that rate ignores the curse of dimensionality entirely. Frustrating, because 1/sqrt(N) is slow — to add one more correct decimal digit you must multiply the sample count by a hundred. And here is the wall this guide exists to face honestly: no amount of cleverness changes that exponent. The square-root rate is baked into the central limit theorem, and we are not going to beat it.
But look more closely at the full error formula. The standard error of the average is sigma/sqrt(N), where sigma is the standard deviation of the single random quantity you are averaging. There are two knobs in that fraction, not one. Cranking N is the brute-force knob, and it is expensive. The other knob is sigma — the spread of the thing you sample. If you can rewrite your problem so that the same answer comes out with a smaller sigma, the whole error curve drops, at every N, for free. That is the entire idea of variance reduction: leave the 1/sqrt(N) rate untouched, and shrink the constant multiplying it.
It is worth pricing this out, because it sounds modest and is not. Suppose a trick cuts the variance sigma^2 by a factor of ten. Since error scales like sqrt(sigma^2/N), cutting the variance tenfold is exactly as good as multiplying N tenfold — you reach the same accuracy with one tenth of the samples, or one tenth of the runtime. A clever variance-reduction scheme that costs almost nothing to apply can therefore be worth a 10x or 100x speed-up. That is why this is a whole subject and not a footnote: in serious Monte Carlo, reducing variance is usually where the real wins live.
Importance sampling: spend your darts where the action is
Picture estimating the area under a function that is nearly flat and tiny across most of [0, 1] but has one tall, narrow spike near x = 0.8. Plain Monte Carlo throws darts uniformly, so the overwhelming majority land in the boring flat region and contribute almost nothing useful, while the spike — which holds most of the answer — gets only a handful of hits. Those few hits are wildly variable: catch the spike's peak and your estimate jumps, miss it and it sags. That is a high-sigma situation, and uniform sampling is squandering its effort.
Importance sampling fixes this by sampling on purpose where the integrand is large. Instead of drawing points uniformly, you draw them from a chosen distribution p(x) that mimics the shape of the integrand — heavy near the spike, light over the flats. But sampling more often near the spike would, untouched, overcount it. So you correct each sample by dividing by p(x): a point that p made common is weighted down, a point it made rare is weighted up. The bookkeeping is exact — the estimate stays unbiased, aimed at the true answer — but the spread of the weighted values can be dramatically smaller.
Estimate I = integral of f(x) dx over the domain.
Plain Monte Carlo (uniform on [0,1]):
draw x_1..x_N uniform
I_hat = (1/N) * sum f(x_n)
Importance sampling (draw from your chosen p):
draw x_1..x_N from density p(x)
I_hat = (1/N) * sum f(x_n) / p(x_n)
the ratio f/p is what you actually average
Goal: pick p so that f(x)/p(x) is nearly CONSTANT
-> tiny variance. Perfect p (impossible): p proportional to f.The magic, and the catch, both live in one sentence: variance is smallest when the ratio f(x)/p(x) is most nearly constant. If you could choose p exactly proportional to f, every weighted sample would return the identical value and the variance would be zero — one sample would nail the answer. That perfect p is of course unreachable (knowing it would mean already knowing the integral), but it tells you the target: shape p to look like f. Get p roughly right and sigma collapses; get it badly wrong and you can do far worse than plain Monte Carlo — pick a p that is tiny exactly where f is large and a few samples land there with enormous weights f/p, and the variance can even blow up to infinity. Importance sampling is a sharp knife: powerful, and it cuts you if held wrong.
Stratified sampling: divide the room, then sample each corner
A second, gentler idea attacks a different source of waste. When you throw N uniform darts across [0, 1], pure luck clusters some and leaves gaps elsewhere — and that clumping is itself a source of variance, separate from the integrand's shape. Stratified sampling removes the clumping by force. Split the domain into k equal strips, and insist that each strip receives exactly N/k of the samples instead of letting chance decide. Within each strip you still sample randomly, so the estimate stays honest, but the coverage is now guaranteed even across the whole domain.
Why does forcing even coverage help? Because it surgically removes the part of the variance that came from where the samples happened to fall, leaving only the part that comes from how f wiggles within each strip. Make the strips narrow and f looks nearly flat inside each one, so that leftover variance shrinks too. Stratification can never make things worse — at worst it ties plain Monte Carlo — and it is almost free to implement in low dimensions. Its weakness is the curse again: splitting d axes into k strips each needs k^d strips, so in high dimensions you cannot stratify every axis. The practical compromise, Latin hypercube sampling, stratifies each axis one-dimensionally at once, capturing much of the benefit cheaply.
Control variates and antithetic pairs: cheap, almost-free wins
A third family exploits things you already know. A control variate works like this: suppose alongside the quantity f you actually want, there is a related quantity g that rides up and down together with f sample by sample, and whose true average you happen to know exactly. Then every time your random g comes out above its known mean, that is a hint your random f probably came out high too — so you nudge f's estimate down by the same lucky amount, and vice versa. You are subtracting off the part of f's wobble that g could have predicted, and keeping only the genuinely unpredictable remainder. The stronger the correlation between f and g, the more wobble you cancel and the smaller the variance.
The antithetic-variates trick is even simpler and almost laughably cheap. Notice that if u is a uniform sample, then 1 - u is also a perfectly valid uniform sample — its mirror image. So generate samples in pairs: one from u, its twin from 1 - u. If the integrand is monotone, then when u pushes the first estimate high, its mirror 1 - u pushes the second one low, and their average cancels much of the swing. You get a variance reduction for nearly no extra work — you were going to draw the random numbers anyway, and reflecting them costs one subtraction. It is the closest thing to a free lunch in the whole subject, though, honestly, it only helps when that mirror symmetry actually lines up with your function.
Honest limits, and where this points next
Hold on to the honest summary, because it is easy to oversell these tricks. Every method here is a way to shrink sigma; not one of them touches the 1/sqrt(N) rate, so each is a constant-factor speed-up, not a change in kind. Each also carries a condition for working: importance sampling needs a proposal that genuinely resembles the integrand, stratification needs few enough dimensions, control variates need a correlated quantity with a known mean, antithetics need the right symmetry. Apply one blindly and you may gain nothing, or — for importance sampling especially — make the variance dramatically worse. The estimate stays unbiased throughout (it still aims at the true answer); what these tricks buy, when they fit, is a tighter spread around that aim.
There is also a problem none of these methods can solve, and naming it sets up the final guide. Importance sampling assumed you could draw samples from your chosen p, and the previous guide's sampling tools — inverse-transform, rejection — work beautifully in low dimensions. But the distributions that matter most in physics, statistics, and machine learning live in hundreds or thousands of dimensions, and you often cannot even normalise them, let alone invert them or bound them for rejection. For those, the only way to get samples at all is to take a guided random walk that visits high-probability regions more often, building the right distribution as the long-run behaviour of a wandering chain.
That is exactly the leap of the next and last guide in this rung: Markov-chain Monte Carlo. It trades the clean independence of every method so far for samples that are correlated neighbours along a chain — a new and subtler kind of cost, with its own diagnostics for whether the chain has wandered long enough to be trusted. For now, carry forward the lesson of this guide: the 1/sqrt(N) rate is a law you obey, not a wall you break, and the entire craft of efficient Monte Carlo is the patient art of shrinking the constant in front of it.