Monte Carlo Methods

technique · mathematics · formal-scientific

Estimating quantities through repeated random sampling.

Monte Carlo Methods are computational techniques that use repeated random sampling to estimate quantities that are difficult or impossible to compute analytically. The methods were named and substantially developed by Stanislaw Ulam, John von Neumann, and Nicholas Metropolis at Los Alamos in the 1940s during the Manhattan Project (the name from the Monte Carlo casino, suggested by Metropolis as a code name reflecting Ulam's uncle's gambling). The foundational paper is Metropolis and Ulam's 1949 'The Monte Carlo Method' (Journal of the American Statistical Association). The basic Monte Carlo workflow: define a domain of possible inputs; randomly generate inputs from a probability distribution over the domain; perform deterministic computation on the inputs; aggregate the results. Estimates converge at rate 1/√n where n is the number of samples — slower than many deterministic methods in low dimensions but independent of dimension (a substantial advantage in high-dimensional integration, where deterministic quadrature suffers from the curse of dimensionality). The Metropolis algorithm (Metropolis, Rosenbluth, Rosenbluth, Teller, Teller 1953) and its generalization the Metropolis-Hastings algorithm (Hastings 1970) introduced Markov Chain Monte Carlo (MCMC), which dramatically expanded the applicability of Monte Carlo methods to high-dimensional probability distributions. Modern variants include Hamiltonian Monte Carlo, NUTS (No-U-Turn Sampler), Gibbs sampling, importance sampling, sequential Monte Carlo (particle filters), and quasi-Monte Carlo (low-discrepancy sequences for faster convergence). Applications span essentially every quantitative discipline: physics (statistical mechanics, lattice QCD), computational biology, finance (option pricing — Black-Scholes via Monte Carlo, risk simulation), Bayesian statistical inference (MCMC), reinforcement learning (Monte Carlo Tree Search — central to AlphaGo), engineering reliability analysis, and many others.

Originators

Stanislaw Ulam, John von Neumann, Nicholas Metropolis (Manhattan Project, 1940s); Metropolis-Hastings algorithm (Metropolis et al. 1953, Hastings 1970) high

Year / Decade

1940s (Los Alamos Manhattan Project development); 1949 (Metropolis-Ulam foundational paper); 1953 (Metropolis algorithm); 1970 (Hastings generalization) high

Primary sources

Metropolis, N. & Ulam, S. (1949). 'The Monte Carlo Method', Journal of the American Statistical Association, Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. & Teller, E. (1953). 'Equation of State Calculations by Fast Computing Machines', Hastings, W.K. (1970). 'Monte Carlo Sampling Methods Using Markov Chains and Their Applications', Robert, C.P. & Casella, G. (2004). Monte Carlo Statistical Methods high

Core components

Random sampling from probability distributions
Estimate convergence at rate 1/√n
Independence from dimensionality (vs deterministic methods)
Markov Chain Monte Carlo (MCMC)
Metropolis-Hastings algorithm
Gibbs sampling
Hamiltonian Monte Carlo
Importance sampling
Sequential Monte Carlo (particle filters)
Quasi-Monte Carlo (low-discrepancy sequences)
Variance reduction techniques
Application to integration, optimization, simulation, statistical inference

Primary use case

Bayesian statistical inference (MCMC is the workhorse method); statistical physics (Metropolis algorithm originated for this); option pricing and financial risk simulation; reinforcement learning (Monte Carlo Tree Search in AlphaGo and related game-playing agents); particle physics (event generators, lattice QCD); computational biology (population genetics, phylogenetics); engineering reliability analysis; weather and climate ensemble forecasting; foundation for substantial commercial software including statistical packages (Stan, JAGS, PyMC).

Common criticisms

Convergence at rate 1/√n is slow when high accuracy is needed
MCMC convergence diagnostics are imperfect — methods may produce samples from non-target distributions if not run long enough or if chains are not properly mixed
tuning of MCMC algorithms (proposal distributions, step sizes, numbers of chains) requires expertise
for some problems, careful Monte Carlo can be competitive with or beaten by deterministic methods
correlated samples in MCMC require longer runs than independent samples would for equivalent precision
high-dimensional and multimodal target distributions remain challenging
the apparent simplicity of 'just sample randomly' obscures substantial mathematical sophistication required for valid inference
commercial Monte Carlo applications in finance and engineering vary in quality of variance-reduction technique application
pseudorandom-number-generator quality matters and is sometimes overlooked.

Lineage

Siblings: Bayesian Inference