Monte Carlo Methods from Scratch — Solving Integrals with Dice

An integral you cannot solve can still be estimated: scatter random points and take the average. This piece builds up why the law of large numbers buys you only 1/√N, what importance sampling rescues, and how MCMC samples from a distribution whose normalizing constant nobody can compute.

To Measure a Pond, Count the Raindrops

There is a pond of some irregular shape in the middle of a 100-square-metre lot, and you want its area without surveying it.

Here is a way. Wait for rain to fall evenly over the whole lot, then count what fraction of the drops landed in the water. If 283 out of 1,000 drops hit the pond, the area is about 28.3 square metres. You never need a formula for the shape, and you never need to remember any geometry. You just reinterpret "the fraction that hit" as "the size."

That is the whole of Monte Carlo. In the 1940s, the mathematician Stanislaw Ulam, recovering from illness at Los Alamos, was trying to work out the odds of a solitaire hand and realized it would be faster to deal the cards a few hundred times and count than to enumerate the combinatorics. With von Neumann he applied the idea to neutron diffusion, and the method was named after the casino district of Monaco. It carries the name of a gambling house, but what it does is count raindrops.

Read an Integral as an Average

In school, an integral is a stack of thin rectangles you add up. Monte Carlo looks at the same object from a different angle: an integral is width times average height.

One symbol at a time. $\mathbb{E}$ means "average," $U \sim \mathrm{Uniform}(a,b)$ means "a single point picked between $a$ and $b$, every location equally likely," and $f(U)$ is the height of the function there. In words, the formula says: take the average height at a randomly chosen point, multiply by the width of the interval, and you have the area. It is the same logic as "area = width × height" for a rectangle, with the varying height smoothed out by averaging.

And an average can be replaced by the average of the samples you actually drew.

Pick $N$ points $x_1,\dots,x_N$ at random from the interval, add up the heights, divide by the count. That is, taste a few spoonfuls and treat their average as the whole pot — the same reasoning as an election exit poll. This is Monte Carlo integration, and it works no matter how ugly $f$ is, as long as you can evaluate it.

Why Not Just Lay Down a Grid?

In one dimension, evenly spaced slices (the trapezoid rule, Simpson's rule) are more accurate. There is no reason to reach for randomness. What changes everything is dimension.

Say you want 10 points per axis. In 2D that is $10^2 = 100$ points, in 3D it is 1,000. Still fine. But 10 dimensions costs 10 billion points, and 20 dimensions costs $10^{20}$. Even at the crudest possible resolution — two divisions per axis — 20 dimensions is $2^{20}$, over a million points. A grid grows exponentially in the number of dimensions. That is the curse of dimensionality.

This is exactly where Monte Carlo wins. As we will see, its error shrinks like $1/\sqrt{N}$, and that rate does not depend on the dimension at all. In 100 dimensions or 10,000, ten thousand samples buy you whatever ten thousand samples are worth. A method that loses to a grid in 1D becomes the only workable option in high dimensions. Portfolio valuation, rendering, Bayesian inference — they all reach for Monte Carlo because their integrals are high-dimensional.

Where 1/√N Comes From

The law of large numbers promises that more samples get you closer to the truth. The central limit theorem answers the question that actually matters in practice: closer how fast?

Since $\hat{I}_N$ is the average of $N$ independent values, its variance is the original variance divided by $N$.

$\sigma$ is the spread (standard deviation) of $f(U)$. The variance gets divided by $N$, but the error you actually feel is its square root — so error only shrinks like $\sqrt{N}$. That is the whole story.