Monte Carlo Integration

Imagine you need the area of a shape so irregular that no formula exists. You could trace it on graph paper and count squares — but that takes forever for complicated shapes, and becomes completely hopeless in more than two or three dimensions.

Monte Carlo integration offers a different answer: throw random points at a bounding box and count how many land inside your shape. The fraction of hits times the box's area is your estimate, and it gets better with every additional point.

The method is named after the famous casino in Monaco, because it relies on chance the same way gambling does — but unlike gambling, the odds here are firmly in the mathematician's favor. The deeper surprise is the curse of dimensionality: classical grid-based methods collapse when the number of dimensions grows, but Monte Carlo's error shrinks as $1/\sqrt{n}$ regardless of how many dimensions you have. That single fact makes it the method of choice wherever integrals live in high-dimensional spaces.

See also Bayesian inference for another technique where probability meets exact mathematics.

A unit circle fits inside a $2\times 2$ square. Any random point $(x, y)$ with $x \in [-1, 1]$ and $y \in [-1, 1]$ lands inside the circle if $x^2 + y^2 \le 1$. The probability of a hit is $\pi/4$, so 4 × (hits / total) estimates $\pi$.

<div class="top-bar">
  <div class="stat"><span class="label">{{label_darts}}</span><span id="total">0</span></div>
  <div class="stat"><span class="label">{{label_inside}}</span><span id="inside">0</span></div>
  <div class="stat pi-stat"><span class="label">π ≈</span><span id="pi-est">—</span></div>
  <div class="stat"><span class="label">{{label_error}}</span><span id="error">—</span></div>
</div>
<canvas id="canvas" width="320" height="220"></canvas>
<div class="btns">
  <button id="btn10" type="button">+10</button>
  <button id="btn100" type="button">+100</button>
  <button id="btn1000" type="button">+1 000</button>
  <button id="btnAuto" type="button">{{btn_auto}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="convergence-label">{{convergence_label}}</div>
<canvas id="conv" width="320" height="80"></canvas>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #f8f9fa; }
.top-bar { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
.stat { background: #fff; border: 1px solid #dde3ea; border-radius: 8px;
        padding: .35rem .7rem; display: flex; flex-direction: column; align-items: center;
        min-width: 64px; }
.pi-stat { min-width: 96px; }
.label { font-size: .7rem; color: #666; text-transform: uppercase; letter-spacing: .04em; }
.stat span:last-child { font: 700 1.05rem ui-monospace, monospace; color: #1d3557; }
canvas { display: block; border-radius: 8px; border: 1px solid #dde3ea;
         background: #fff; margin-bottom: .5rem; max-width: 100%; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #e63946; border-color: #c92f3c; }
.convergence-label { font-size: .75rem; color: #666; margin-bottom: .2rem; }

// Code not found

Watch the estimate converge as darts accumulate. The error does not shrink uniformly — it bounces around and occasionally gets worse before it improves. That is the nature of randomness: statistically the error is proportional to $1/\sqrt{n}$, meaning you need 100× more darts to gain one extra decimal place. But the method never cares whether you are working in 2 dimensions or 200.

How good is Monte Carlo integration, really? The answer depends on what you compare it against.

Grid-based methods (the trapezoid rule, Simpson's rule, Gaussian quadrature) divide the integration domain into a regular grid and evaluate the function at grid points. In d dimensions, covering the domain with k points per axis requires $k^{d}$ evaluations — an exponential blowup. A 10-point grid in 10 dimensions needs 10 billion evaluations; in 20 dimensions, $10^{20}$.

Monte Carlo does not suffer this curse. Its mean squared error is:

$$\mathrm{MSE} = \frac{\mathrm{Var}(f)}{n}$$

which means the root-mean-square error is $\sigma/\sqrt{n}$, regardless of the number of dimensions $d$. To halve the error, double the number of samples. To gain one decimal digit, multiply by 100. The constant $\sigma$ (the standard deviation of $f$ over the domain) matters, but the dimension $d$ does not appear anywhere.

Variance reduction techniques can push the convergence faster in practice:

• Importance sampling: sample more densely where f is large.
• Stratified sampling: divide the domain into strata and sample each separately.
• Quasi-Monte Carlo: replace pseudo-random points with low-discrepancy sequences (Halton, Sobol) to achieve near-$O(n^{-1})$ convergence.

Monte Carlo integration is provably optimal among methods that treat the integrand as a black box in high dimensions. It is not special-cased for specific function shapes — it works on any integrand you can evaluate, including probability distributions that can only be sampled, not written down.

Any problem that boils down to "evaluate a high-dimensional integral" ends up using Monte Carlo:

• Physics simulations: particle transport (neutron scattering, radiation therapy planning) requires integrating over all possible paths through matter — a space with hundreds of dimensions. Monte Carlo was invented at Los Alamos in 1946 by Stanislaw Ulam and John von Neumann precisely for this problem.
• Financial derivatives pricing: the fair price of an option depends on the expected payoff under a probability distribution over future asset paths. A basket option on 50 correlated assets lives in a 50-dimensional space — only Monte Carlo (and quasi-Monte Carlo) is practical.
• Bayesian posterior inference: computing a posterior distribution requires integrating the likelihood times the prior over all parameter values. Markov Chain Monte Carlo (MCMC) is the engine behind almost all modern Bayesian computation.
• Computer graphics: realistic rendering traces light paths through a scene. Each pixel color is an integral over all possible paths from the camera to light sources — an infinite-dimensional space. Path tracing (used in films and real-time ray tracing) is Monte Carlo integration applied to light transport.
• Machine learning: stochastic gradient descent is a Monte Carlo approximation of the true gradient, and variational inference replaces intractable posteriors with Monte Carlo estimates.

The method also connects to randomized algorithms and the broader theme that randomness, used carefully, is a powerful computational resource.

Monte Carlo integration started as a trick for nuclear physicists who could not solve their equations analytically. It has since become one of the most widely used algorithms in science, finance, and engineering.

Its secret is geometric: in high dimensions, almost all the volume of a hypercube sits near its surface, and regular grids miss most of it. Random points, by contrast, are distributed uniformly everywhere, so nothing is systematically neglected.

The price is statistical noise — the $1/\sqrt{n}$ convergence rate is modest. But it is guaranteed, dimension-independent, and improvable with variance reduction. For integrals in ten or more dimensions, no deterministic method comes close.

Next time you watch a ray-traced film, price an option, or train a neural network, there is a good chance a shower of random darts is quietly doing the mathematics behind the scenes.