The short version. Monte Carlo methods answer questions too large to compute exactly by averaging over random samples. For independent samples, the error shrinks as one over the square root of the sample count, in any number of dimensions. The methods fail quietly when samples are correlated, unrepresentative or not random enough, so a Monte Carlo answer is only as good as its diagnostics.
A card game, a letter and a name
In 1946, while recovering from an illness, the mathematician Stanislaw Ulam wondered about the odds that a game of Canfield solitaire would come out. After trying combinatorics, he asked whether a more practical approach might be to “lay it out say one hundred times and simply observe and count the number of successful plays” [1]. He saw at once that the idea could tackle neutron diffusion, and described it to John von Neumann. In March 1947, von Neumann wrote to Robert Richtmyer at Los Alamos, outlining how to solve neutron diffusion problems statistically on a digital computer [1]. Nicholas Metropolis suggested the name, a nod to an uncle of Ulam’s who “just had to go to Monte Carlo” [2]. In 1949, Metropolis and Ulam published a paper titled simply “The Monte Carlo method” [3].
Monte Carlo methods sit near the centre of my own toolkit, and the Markov chains at the heart of the modern versions are close relatives of the Markovian models behind much of my research. What follows is the intuition I find most useful: why sampling works, and how to tell when it does not.
Why a few samples can stand in for everything
Suppose you want the average of some quantity over every possible state of a system: the expected loss of a portfolio, the energy of a fluid, the probability that a design stays within tolerance. Listing every state is usually impossible. Instead, draw states at random, compute the quantity for each, and average. The law of large numbers says the average converges to the true value. The central limit theorem says how fast:
error ≈ σ / √N
Here σ (sigma) is the standard deviation across individual samples, a measure of how much one differs from the next, and N is the number of independent samples. One consequence is sobering: to gain one more decimal place of accuracy, you need one hundred times as many samples. Another is remarkable: nothing in the formula depends on the number of dimensions. A grid with ten points along each axis needs 10^100 points in a 100-dimensional problem, far beyond any computer. Random sampling does not care, which is why it is the default for problems with many uncertain inputs.
The Metropolis step: sampling what you cannot list
Simple random sampling works when you can draw states directly. Physics rarely allows that. In a fluid or a magnet, states follow the Boltzmann distribution, whose normalizing sum is exactly the quantity you cannot compute. In 1953, Metropolis and four colleagues found a way around it [4]. Start from any state. Propose a small random change. If the change lowers the energy, accept it. If it raises the energy, accept it with a probability that falls exponentially with the increase, scaled by the temperature. Repeat.
The sequence of states forms a Markov chain, a random process in which each step depends only on the current state. The acceptance rule is built so that, run long enough, the chain visits states in proportion to their Boltzmann probability, without ever computing the normalizing sum. Its first test case was a two-dimensional system of rigid spheres [4]. In 1970, W. K. Hastings, then at the University of Toronto, generalized the method for statistical problems [5]. The family is now called Markov chain Monte Carlo.
In 1983, Kirkpatrick, Gelatt and Vecchi turned the idea into an optimization method. Run the Metropolis rule while slowly lowering the temperature, as a metallurgist anneals a metal, and the system settles into low-energy, good solutions. They applied simulated annealing to travelling salesman problems with thousands of cities [6].
Where sampling shows up now
The same ideas run through modern artificial intelligence (AI), finance and engineering. AlphaGo, the Go-playing program, combined deep neural networks with Monte Carlo tree search, which estimates the value of a move by simulating possible continuations [7]. Yarin Gal and Zoubin Ghahramani showed that dropout, a training technique that randomly switches off parts of a neural network, can be read as approximate Bayesian inference, so repeated randomized predictions give an estimate of model uncertainty [8]. In finance, Monte Carlo simulation is a standard tool for pricing derivatives and measuring risk [9]. In metrology, the guidance document JCGM 101:2008 sets out how to propagate measurement uncertainty through a model by Monte Carlo sampling [10].
When sampling fails
All of these uses share the same weaknesses, and a dangerous trait: a failed Monte Carlo run still prints a number.
| Failure | What goes wrong | What to check |
|---|---|---|
| Correlated samples | Effective N far below the count | Autocorrelation, effective sample size |
| Critical slowing down | Local moves barely change anything | Cluster moves [11] |
| Rare events | Key outcomes never drawn | Importance sampling |
| Poor random numbers | Hidden bias that looks like a result | Tests against exact answers [12] |
| Unconverged chains | Answer depends on the starting point | Several chains, dispersed starts [13] |
Near a critical point, regions of aligned spins grow very large, and a method that flips one spin at a time needs ever longer to change anything that matters. In 1987, Robert Swendsen and Jian-Sheng Wang introduced an algorithm that updates whole clusters of spins at once, making large systems near criticality practical to simulate [11]. In 1992, Ferrenberg, Landau and Wong ran Ising-model simulations, where exact answers are known, and found that some well-regarded random number generators produced systematic errors with certain algorithms [12]. Without an exact answer to compare against, those errors could have passed for physics.
The last row is the one I would put on every wall. The approach of Andrew Gelman and Donald Rubin runs several chains from widely dispersed starting points and compares the variation within each chain to the variation between them [13]. If the chains disagree, you have not converged. The converse does not hold: a diagnostic can reveal that a chain has not explored what matters, but none can prove that it has.
What to ask of a Monte Carlo result
Established: for independent samples the σ / √N law holds, and a properly constructed Markov chain converges to its target distribution in the long run. Judgment: how long the long run is, whether the samples are independent enough, and whether the rare events that dominate risk were ever drawn. When a simulation informs a decision, ask for three things: the effective number of samples, the convergence diagnostics, and a check against a case with a known answer. Those three turn a number into evidence.
References
- R. Eckhardt, “Stan Ulam, John von Neumann, and the Monte Carlo method,” Los Alamos Science, no. 15, pp. 131-141, 1987.
- N. Metropolis, “The beginning of the Monte Carlo method,” Los Alamos Science, no. 15, pp. 125-130, 1987.
- N. Metropolis and S. Ulam, “The Monte Carlo method,” Journal of the American Statistical Association, vol. 44, no. 247, pp. 335-341, 1949.
- N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, “Equation of state calculations by fast computing machines,” The Journal of Chemical Physics, vol. 21, no. 6, pp. 1087-1092, 1953.
- W. K. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika, vol. 57, no. 1, pp. 97-109, 1970.
- S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, 1983.
- D. Silver et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, vol. 529, pp. 484-489, 2016.
- Y. Gal and Z. Ghahramani, “Dropout as a Bayesian approximation: Representing model uncertainty in deep learning,” in Proc. 33rd International Conference on Machine Learning (ICML), PMLR vol. 48, pp. 1050-1059, 2016.
- P. Glasserman, Monte Carlo Methods in Financial Engineering. New York: Springer, 2003.
- Joint Committee for Guides in Metrology, “Evaluation of measurement data: Supplement 1 to the ‘Guide to the expression of uncertainty in measurement’: Propagation of distributions using a Monte Carlo method,” JCGM 101:2008, BIPM, 2008.
- R. H. Swendsen and J.-S. Wang, “Nonuniversal critical dynamics in Monte Carlo simulations,” Physical Review Letters, vol. 58, no. 2, pp. 86-88, 1987.
- A. M. Ferrenberg, D. P. Landau and Y. J. Wong, “Monte Carlo simulations: Hidden errors from ‘good’ random number generators,” Physical Review Letters, vol. 69, p. 3382, 1992.
- A. Gelman and D. B. Rubin, “Inference from iterative simulation using multiple sequences,” Statistical Science, vol. 7, no. 4, pp. 457-472, 1992.