How the Monte Carlo method works

What is the core idea?

Some questions have exact answers that are miserable to work out. Monte Carlo methods take a detour: instead of solving the problem on paper, build a random experiment whose average outcome equals the answer, then run that experiment a great many times. Randomness, used carefully, ends up answering a question that has nothing random about it.

The approach is usually described as a four-part pattern. Decide which inputs are possible. Draw inputs at random from a probability distribution over that range. Run an ordinary, fixed calculation on each input. Finally, pool the results, usually by averaging or counting.

A worked example: estimating pi with random dots

Draw a square with sides of length one, and inside it draw a quarter of a circle whose radius is also one, centred on a corner. The quarter circle covers a fixed share of the square, and that share is pi divided by four.

Now scatter dots across the square uniformly at random. For each dot, check whether it lies within distance one of the corner, which means it landed inside the quarter circle. The fraction of dots inside is an estimate of pi over four, so multiplying that fraction by four gives an estimate of pi.

With only a handful of dots the answer jumps around; with many thousands it settles close to the familiar 3.14. Two lessons fall out of this toy. The dots must be spread evenly, or the estimate goes wrong. And the more dots you add, the better the estimate tends to become.

Why does averaging random samples work?

The guarantee comes from the law of large numbers. It says that when you take many independent samples from the same process, their average drifts towards the true expected value, as long as that value exists. Roll a fair six-sided die often enough and the average creeps towards 3.5; flip a fair coin often enough and the share of heads approaches one half.

Simple Monte Carlo applies that law directly. Run the simulation n times, add up the results, divide by n. For a large enough n, the average lands as close to the true value as you want with high confidence. There are formulas for choosing n: run a small batch first, measure how much the results vary, and use that spread together with the accuracy and confidence you need to work out how many more runs to do.

A more advanced family, Markov chain Monte Carlo, is used when the samples themselves are hard to draw. It builds a chain of random steps designed so that, in the long run, the states it visits behave like samples from the distribution you care about.

Where is it used?

The method shows up in three broad jobs: optimization, numerical integration, and generating random draws from complicated probability distributions. Physicists use it to simulate systems with many interacting parts, such as fluids and disordered materials. Businesses use it to model risk when inputs are uncertain, and engineering projects in fields like space and aircraft design use it to predict failures and cost or schedule overruns.

Its history is tied to physics. In the 1940s, Stanisław Ulam proposed random experiments to scientists at Los Alamos who were stuck on a neutron diffusion problem. He later described being inspired by wondering how often a game of solitaire would come out, and realising it might be easier to play many games and count than to calculate the odds. Nicholas Metropolis suggested the code name, taken from the Monte Carlo Casino in Monaco, and in 1948 the ENIAC computer ran the first fully automated Monte Carlo calculations.

Where does it go wrong?

The first limit is cost. Good accuracy often needs a very large number of samples, and if each sample is an expensive simulation the total running time can become huge. The saving grace is that samples are independent, so the work spreads easily across many processors, clusters or graphics cards.

The second limit is the inputs. If the random numbers are flawed, or the samples are not spread the way the method assumes, the average converges confidently to the wrong place. A model with a selection bias stays biased no matter how many runs you add.

The third is heavy tails. Some distributions, such as the Cauchy distribution, have no finite average at all, so averaging more samples never settles down. Adding samples cannot rescue a quantity that does not exist. Finally, a simulation answers the question built into its model. If the model leaves out what matters, the output is a precise estimate of the wrong thing.

Questions people ask

The thinking behind it

• expected value
• regression to the mean
• gamblers fallacy
• signal vs noise
• black swan
• diminishing returns

More algorithms, explained

• How simulated annealing works
• How the minimax algorithm works
• How the Elo rating system works
• How the Gale–Shapley algorithm works