Monte Carlo simulation

The name comes from the Monte Carlo Casino in Monaco, where the primary developer of the method, mathematician Stanisław Ulam, was inspired by his uncle's gambling habits. Monte Carlo methods are widely used in various fields of science, engineering, and mathematics, such as physics, chemistry, biology, statistics, artificial intelligence, finance, and cryptography. They have also been applied to social sciences, such as sociology, psychology, and political science. Monte Carlo methods have been recognized as one of the most important and influential ideas of the 20th century, and they have enabled many scientific and technological breakthroughs.

Monte Carlo methods also have some limitations and challenges, such as the trade-off between accuracy and computational cost, the curse of dimensionality, the reliability of random number generators, and the verification and validation of the results. Monte Carlo methods vary, but tend to follow a particular pattern:

For example, consider a quadrant (circular sector) inscribed in a unit square. Given that the ratio of their areas is ⁠π/4⁠, the value of π can be approximated using the Monte Carlo method:

In this procedure, the domain of inputs is the square that circumscribes the quadrant. One can generate random inputs by scattering grains over the square, then performing a computation on each input to test whether it falls within the quadrant. Aggregating the results yields our final result, the approximation of π. There are two important considerations:

Uses of Monte Carlo methods require large amounts of random numbers, and their use benefitted greatly from pseudorandom number generators, which are far quicker to use than the tables of random numbers that had been previously employed.

Monte Carlo methods are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

In physics-related problems, Monte Carlo methods are useful for simulating systems with many coupled degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures, e.g. cellular Potts model, interacting particle systems, McKean–Vlasov processes, kinetic models of gases.

Other examples include modeling phenomena with significant uncertainty in inputs such as the calculation of risk in business and, in mathematics, evaluation of multidimensional definite integrals with complicated boundary conditions. In application to systems engineering problems (space, oil exploration, aircraft design, etc.), Monte Carlo–based predictions of failure, cost overruns and schedule overruns are routinely better than human intuition or alternative "soft" methods.

In principle, Monte Carlo methods can be used to solve any problem having a probabilistic interpretation. By the law of large numbers, integrals described by the expected value of some random variable can be approximated by taking the empirical mean (a.k.a. the 'sample mean') of independent samples of the variable. When the probability distribution of the variable is parameterized, mathematicians often use a Markov chain Monte Carlo (MCMC) sampler. The central idea is to design a judicious Markov chain model with a prescribed stationary probability distribution. That is, in the limit, the samples being generated by the MCMC method will be samples from the desired (target) distribution. By the ergodic theorem, the stationary distribution is approximated by the empirical measures of the random states of the MCMC sampler.

In other problems, the objective is generating draws from a sequence of probability distributions satisfying a nonlinear evolution equation. These flows of probability distributions can always be interpreted as the distributions of the random states of a Markov process whose transition probabilities depend on the distributions of the current random states (see McKean–Vlasov processes, nonlinear filtering equation). …

Suppose one wants to know the expected value μ {\displaystyle \mu } of a population (and knows that μ {\displaystyle \mu } exists), but does not have a formula available to compute it. The simple Monte Carlo method gives an estimate for μ {\displaystyle \mu } by running n {\displaystyle n} simulations and averaging the simulations' results. It has no restrictions on the probability distribution of the inputs to the simulations, requiring only that the inputs are randomly generated and are independent of each other and that μ {\displaystyle \mu } exists. A sufficiently large n {\displaystyle n} will produce a value for m {\displaystyle m} that is arbitrarily close to μ {\displaystyle \mu } ; more formally, it will be the case that, for any ϵ > 0 {\displaystyle \epsilon >0} , | μ − m | ≤ ϵ {\displaystyle |\mu -m|\leq \epsilon } . Typically, the algorithm to obtain m {\displaystyle m} is

Suppose we want to know how many times we should expect to throw three eight-sided dice for the total of the dice throws to be at least T {\displaystyle T} . We know the expected value exists. The dice throws are randomly distributed and independent of each other. So simple Monte Carlo is applicable:

If n {\displaystyle n} is large enough, m {\displaystyle m} will be within ϵ {\displaystyle \epsilon } of μ {\displaystyle \mu } for any ϵ > 0 {\displaystyle \epsilon >0} .

Let ϵ = | μ − m | > 0 {\displaystyle \epsilon =|\mu -m|>0} . Choose the desired confidence level – the percent chance that, when the Monte Carlo algorithm completes, m {\displaystyle m} is indeed within ϵ {\displaystyle \epsilon } of μ {\displaystyle \mu } . Let z {\displaystyle z} be the z {\displaystyle z} -score corresponding to that confidence level.

Let s 2 {\displaystyle s^{2}} be the estimated variance, sometimes called the "sample" variance; it is the variance of the results obtained from a relatively small number k {\displaystyle k} of "sample" simulations. …

Despite its conceptual and algorithmic simplicity, the computational cost associated with a Monte Carlo simulation can be staggeringly high. In general the method requires many samples to get a good approximation, which may incur an arbitrarily large total runtime if the processing time of a single sample is high. Although this is a severe limitation in very complex problems, the embarrassingly parallel nature of the algorithm allows this large cost to be reduced (perhaps to a feasible level) through parallel computing strategies in local processors, clusters, cloud computing, GPU, FPGA, etc. In financial and safety-critical applications, floating-point non-determinism across hardware platforms can compound these costs, as results may vary between runs or across different processors (x86, ARM, GPU), sometimes requiring redundant simulations or consensus mechanisms to verify numerical correctness.

Before the Monte Carlo method was developed, simulations tested a previously understood deterministic problem, and statistical sampling was used to estimate uncertainties in the simulations. Monte Carlo simulations invert this approach, solving deterministic problems using probabilistic metaheuristics (see simulated annealing).

An early variant of the Monte Carlo method was devised to solve the Buffon's needle problem, in which π can be estimated by dropping needles on a floor made of parallel equidistant strips. In the 1930s, Enrico Fermi first experimented with the Monte Carlo method while studying neutron diffusion, but he did not publish this work.

In the late 1940s, Stanisław Ulam invented the modern version of the Markov Chain Monte Carlo method while he was working on nuclear weapons projects at the Los Alamos National Laboratory. In 1946, nuclear weapons physicists at Los Alamos were investigating neutron diffusion in the core of a nuclear weapon.

Despite having most of the necessary data, such as the average distance a neutron would travel in a substance before it collided with an atomic nucleus and how much energy the neutron was likely to give off following a collision, the Los Alamos physicists were unable to solve the problem using conventional, deterministic mathematical methods. Ulam proposed using random experiments. He recounts his inspiration as follows:

The first thoughts and attempts I made to practice [the Monte Carlo Method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires. The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than "abstract thinking" might not be to lay it out say one hundred times and simply observe and count the number of successful plays. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neutron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. …