Monte Carlo Integration

Some integrals and averages are ugly enough that no formula will crack them — a payoff that depends on a whole path, a probability buried in ten dimensions. Monte Carlo integration sidesteps the algebra entirely: instead of solving the integral, you sample it. Throw random points at the problem, evaluate the thing you care about at each one, and average. By the The Law of Large Numbers, that average converges to the true answer. It is brute force, but it is brute force that scales to problems nothing else can touch.

The core idea

Almost any integral can be rewritten as an expected value. If you want the average of a function $f$ over some region, draw random samples $X_1, \dots, X_N$ from the right distribution and just average the function values:

$$E[f(X)] \approx \frac{1}{N}\sum_{i=1}^{N} f(X_i).$$

Here $N$ is the number of random samples, $X_i$ is the $i$-th random draw, and $f(X_i)$ is the quantity evaluated at that draw. The bigger $N$ is, the closer the average sits to the truth. How close? The standard error of the estimate is

$$\text{error} \approx \frac{\sigma}{\sqrt{N}},$$

where $\sigma$ is the standard deviation of $f(X)$. That $\sqrt{N}$ is the whole story: to cut the error in half you need four times the samples, and — crucially — the formula has no dimension in it. A hundred-dimensional integral converges at the same rate as a one-dimensional one, which is why Monte Carlo dominates high-dimensional problems that grid-based methods can't survive.

The classic demonstration: estimating pi

The friendliest example throws darts at a square. Inscribe a quarter circle of radius 1 inside a $1 \times 1$ square. Its area is $\tfrac{\pi}{4}$, so the fraction of random darts that land inside the circle is about $\pi/4$. Multiply that fraction by 4 and you have estimated $\pi$ — without ever using $\pi$.

Worked example: darts to pi

Suppose you scatter $N = 1000$ random points in the unit square and find that 785 of them land inside the quarter circle. Your estimate is

$$\hat{\pi} = 4 \times \frac{785}{1000} = 3.14.$$

Not bad. Now, how reliable is it? Each dart is a coin flip with success probability $p = \pi/4 \approx 0.785$, so one dart's outcome has standard deviation $\sqrt{p(1-p)} \approx 0.41$. The standard error of the mean over 1000 darts is $0.41/\sqrt{1000} \approx 0.013$, and $\hat\pi$ is 4 times that fraction, so its error is about $4 \times 0.013 \approx 0.05$. To shrink that to $0.005$ — one more decimal of accuracy — you would need not ten times but a hundred times the darts. That slow crawl is the price of the method's generality.

Making it faster

Because the error is $\sigma/\sqrt N$, and cranking up $N$ is expensive, the real craft is shrinking $\sigma$ — the variance of what you are averaging — so each sample counts for more. That family of tricks is variance reduction: importance sampling aims samples at the region that matters, antithetic variates pair each draw with its mirror image, and control variates subtract off a piece you can compute exactly. A well-chosen variance-reduction scheme can do more than a thousandfold increase in raw samples.

Monte Carlo integration is the engine behind option pricing by simulation, value-at-risk estimation, and Bayesian computation. Any time a quantity can be written as an expectation and the expectation is too hard to evaluate directly, sampling is the fallback — and coding one up is a common interview task.