The Monte Carlo method is a family of computational techniques that use repeated random sampling to estimate quantities such as integrals, probabilities, and average outcomes. Rather than evaluating every possible case, a Monte Carlo calculation samples cases according to a specified probabilistic rule and combines their contributions into an estimate. Its foundations lie in probability theory and statistics, and its usefulness extends to deterministic mathematical problems as well as models of random phenomena. (pbr-book.org)
Basic principle
A common Monte Carlo task is to estimate the expected value of a function of a random variable. If (X) follows a specified probability distribution and the quantity of interest is
[ \mu=\mathbb{E}[f(X)], ]
the simplest estimator draws (N) identically distributed samples (X_1,\ldots,X_N) with statistical independence and computes their sample mean:
[ \widehat{\mu}N=\frac{1}{N}\sum{i=1}^{N}f(X_i). ]
This replaces an expectation with an average over sampled outcomes. The sampling distribution need not be uniform: it must correspond to the mathematical model or be accompanied by weights that correct for the sampling scheme. (pbr-book.org)
For numerical integration over a region (D) with finite volume (V), uniformly sampled points yield
[ \widehat{I}N=\frac{V}{N}\sum{i=1}^{N}f(X_i), \qquad I=\int_D f(x),dx. ]
More generally, samples drawn from a probability density (q(x)) yield the estimator
[ \widehat{I}N= \frac{1}{N}\sum{i=1}^{N}\frac{f(X_i)}{q(X_i)}. ]
Here (q) must be positive wherever the integrand contributes, apart from sets of measure zero. The division by (q(X_i)) compensates for unequal sampling probabilities. (pbr-book.org)
Accuracy and convergence
For independent, identically distributed samples with finite (\sigma^2=\operatorname{Var}[f(X)]), the sample-average estimator is unbiased and has variance
[ \operatorname{Var}(\widehat{\mu}_N)=\frac{\sigma^2}{N}. ]
Its standard error is therefore (\sigma/\sqrt{N}), usually estimated from the sample standard deviation. Thus, reducing the typical sampling error by a factor of two requires approximately four times as many samples. This describes statistical accuracy, not a guarantee that every larger run will be closer to the exact answer. (pbr-book.org)
The law of large numbers provides convergence of the sample average under suitable integrability assumptions. With finite, nonzero variance, the central limit theorem supports approximate normal error calculations and confidence intervals for sufficiently large samples. These assumptions require attention: a finite run may miss rare but influential outcomes and consequently underestimate its own error. (www-personal.engin.umich.edu)
The familiar (N^{-1/2}) error rate does not explicitly depend on the number of dimensions. This is an important advantage for high-dimensional integration, but it does not make such problems automatically easy. Variance, sampling difficulty, and the cost of evaluating each sample can all increase with dimension. In low-dimensional, smooth problems, deterministic methods from numerical analysis may converge substantially faster. (pbr-book.org)
An illustrative example: estimating π
Consider independent points sampled from the uniform distribution on the square ([-1,1]^2). A point lies in the inscribed unit disk when
[ x^2+y^2\leq 1. ]
The disk occupies a fraction (\pi/4) of the square’s area. If (K) of the (N) points fall inside it, the corresponding estimator is
[ \widehat{\pi}_N=4\frac{K}{N}. ]
This is a direct application of Monte Carlo integration to an indicator function. Each point contributes either zero or one, and the observed fraction estimates an area ratio. The example illustrates how a deterministic geometric quantity can be estimated through random sampling; it is not a competitive method for high-precision calculation of π. (www-personal.engin.umich.edu)
Sampling strategies and variance reduction
Computational efficiency depends not only on the number of samples but also on how they are chosen. Variance reduction seeks a more precise estimate for a given computational effort. Principal techniques include:
- Importance sampling: draws more samples from regions that contribute strongly to the quantity of interest and corrects their contributions with probability weights. A poorly chosen sampling distribution can increase variance instead of reducing it.
- Stratified sampling: partitions the sampling domain into regions and samples within each, improving coverage.
- Control variates: uses auxiliary quantities with known expectations to remove a predictable component of sampling error.
- Antithetic variates: pairs samples so that their contributions tend to be negatively correlated, reducing the variance of their average. (pbr-book.org)
These methods do not all preserve independence between individual samples. Their uncertainty calculations must reflect the actual sampling design rather than automatically applying the independent-sample formula. Their benefits must also be weighed against the extra computation required per sample. (artowen.su.domains)
Related families of methods
Markov chain Monte Carlo (MCMC) generates samples by evolving a Markov chain whose stationary distribution is the target distribution. It is especially useful when direct independent sampling is difficult, including many applications of Bayesian inference. Consecutive draws are generally correlated, and the chain must adequately explore the target distribution. Monte Carlo standard errors therefore depend on an effective sample size rather than simply the number of iterations. (mc-stan.org)
Quasi-Monte Carlo replaces independent random points with structured, low-discrepancy point sets that cover the domain more evenly. It can outperform ordinary Monte Carlo for suitable integrands. Despite its name, an unrandomized quasi-Monte Carlo calculation is deterministic; randomized versions combine structured coverage with statistical error estimation. (artowen.su.domains)
In computer science, the term Monte Carlo algorithm also has a more specific meaning within the theory of randomized algorithms: an algorithm whose result may be incorrect with a controlled probability. This terminology overlaps with, but is not identical to, Monte Carlo numerical estimation. (www-personal.engin.umich.edu)
Applications
Monte Carlo methods are used wherever averaging over many possible configurations or histories is more feasible than exhaustive calculation. Major application areas include:
- Particle transport: simulating particle paths, collisions, absorption, and other interactions to estimate aggregate physical quantities. This was central to the method’s early development.
- Statistical mechanics: sampling configurations of systems with many interacting components to estimate equilibrium properties.
- Statistical inference: approximating expectations and other quantities under complex distributions, including Bayesian posterior distributions.
- Computer graphics: estimating light transport by sampling directions, surfaces, and paths, particularly in physically based rendering. (mcnp.lanl.gov)
A Monte Carlo simulation can produce more than a mean: samples can also approximate a distribution, a quantile, or an event probability. The appropriate estimator and uncertainty calculation depend on which of these quantities is being computed. (mc-stan.org)
Historical development
Statistical sampling techniques existed before electronic computers. The modern computational approach developed at Los Alamos in the 1940s through the work of Stanisław Ulam, John von Neumann, Nicholas Metropolis, and collaborators. Electronic computing made extensive sampling practical for problems such as neutron transport. Metropolis proposed the name “Monte Carlo,” referring to the association of Monte Carlo with games of chance. (mcnp-green.lanl.gov)
Metropolis and Ulam published “The Monte Carlo Method” in the Journal of the American Statistical Association in 1949. Their paper presented the approach as a statistical way to investigate problems in mathematical physics, including differential and integro-differential equations. Subsequent developments broadened it into a general framework for numerical integration, simulation, and statistical computation. (doi.org)
Computational limitations
Practical implementations commonly use a pseudorandom number generator rather than a physical source of randomness. Such generators produce deterministic sequences designed to behave like random samples. Recording the generator and its initialization supports reproducibility, although a reproducible run is not by itself evidence of accuracy. (www-personal.engin.umich.edu)
Sampling error is only one source of error. More samples can reduce statistical fluctuations, but they do not correct an inappropriate model, an incorrect sampling distribution, implementation mistakes, or persistent numerical approximation errors. Rare outcomes and poorly explored regions are particularly troublesome because apparently stable results can conceal missing contributions. For correlated sampling, convergence assessment and correlation-aware uncertainty estimates are essential. (www-personal.engin.umich.edu)
References
- Monte Carlo Integrationpbr-book.org
- Monte Carlo: Basicspbr-book.org
- Improving Efficiencypbr-book.org
- Sampling and Integrationpbr-book.org
- Fundamentals of the Monte Carlo methodwww-personal.engin.umich.edu
- Monte Carlo Book: the Quasi-Monte Carlo partsartowen.su.domains
- Variance reductionartowen.su.domains
- Posterior Analysismc-stan.org
- The Beginning of the Monte Carlo Methodmcnp-green.lanl.gov
- MCNP Code Version 6.3.1 Theory & User Manualmcnp.lanl.gov
- The Monte Carlo Methodwucj.lab.westlake.edu.cn