Monte Carlo method


Monte Carlo methods, also called the Monte Carlo experiments or Monte Carlo simulations, are a broad class of computational algorithms based on repeated random sampling for obtaining numerical results. The underlying concept is to use randomness to solve deterministic problems.
Monte Carlo methods are mainly used in three distinct problem classes: optimization, numerical integration, and non-uniform random variate generation, available for modeling phenomena with significant input uncertainties, e.g. risk assessments for nuclear power plants. Monte Carlo methods are often implemented using computer simulations. They can provide approximate solutions to problems too complex for mathematical analysis.

Overview

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:
  1. Define a domain of possible inputs.
  2. Generate inputs randomly from a probability distribution over the domain.
  3. Perform a deterministic computation of the outputs.
  4. Aggregate the results.
For example, consider a quadrant inscribed in a unit square. Given that the ratio of their areas is, the value of pi| can be approximated using the Monte Carlo method:
  1. Draw a square, then inscribe a quadrant within it.
  2. Uniformly scatter a given number of points over the square.
  3. Count the number of points inside the quadrant, i.e. having a distance from the origin of less than 1.
  4. The ratio of the inside-count and the total-sample-count is an estimate of the ratio of the two areas,. Multiply the result by 4 to estimate.
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:
  1. If the points are not uniformly distributed, the approximation will be poor.
  2. The approximation improves as more points are randomly placed in the whole square.
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.

Applications

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, 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 of independent samples of the variable. When the probability distribution of the variable is parameterized, mathematicians often use a Markov chain Monte Carlo 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 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. In other instances, a flow of probability distributions with an increasing level of sampling complexity arise. These models can also be seen as the evolution of the law of the random states of a nonlinear Markov chain.
A natural way to simulate these sophisticated nonlinear Markov processes is to sample multiple copies of the process, replacing in the evolution equation the unknown distributions of the random states by the sampled empirical measures. In contrast with traditional Monte Carlo and MCMC methodologies, these mean-field particle techniques rely on sequential interacting samples. The terminology mean field reflects the fact that each of the samples interacts with the empirical measures of the process. When the size of the system tends to infinity, these random empirical measures converge to the deterministic distribution of the random states of the nonlinear Markov chain, so that the statistical interaction between particles vanishes.

Simple Monte Carlo

Suppose one wants to know the expected value of a population, but does not have a formula available to compute it. The simple Monte Carlo method gives an estimate for by running 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 exists. A sufficiently large will produce a value for that is arbitrarily close to ; more formally, it will be the case that, for any,.
Typically, the algorithm to obtain is
s = 0;
for i = 1 to n do
run the simulation for the ith time, giving result ri;
s = s + ri;
repeat
m = s / n;

Examples

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. We know the expected value exists. The dice throws are randomly distributed and independent of each other. So simple Monte Carlo is applicable:
s = 0;
for i = 1 to n do
throw the three dice until T is met or first exceeded; ri = the number of throws;
s = s + ri;
repeat
m = s / n;
If is large enough, will be within of for any.

Determining a sufficiently large ''n''

General formula

Let. Choose the desired confidence level – the percent chance that, when the Monte Carlo algorithm completes, is indeed within of. Let be the -score corresponding to that confidence level.
Let be the estimated variance, sometimes called the "sample" variance; it is the variance of the results obtained from a relatively small number of "sample" simulations. Choose a ; Driels and Shin observe that "even for sample sizes an order of magnitude lower than the number required, the calculation of that number is quite stable." The following algorithm computes in one pass while minimizing the possibility that accumulated numerical error produces erroneous results:
s1 = 0;
run the simulation for the first time, producing result r1;
m1 = r1; //mi is the mean of the first i simulations
for i = 2 to k do
run the simulation for the ith time, producing result ri;
δi = ri - mi−1;
mi = mi-1 + δi;
si = si-1 + 2;
repeat
s2 = sk/;
Note that, when the algorithm completes, is the mean of the results.
The value is sufficiently large when
If, then ; sufficient sample simulations were done to ensure that is within of. If, then simulations can be run "from scratch," or, since simulations have already been done, one can just run more simulations and add their results into those from the sample simulations:
s = mk * k;
for i = k + 1 to n do
run the simulation for the ith time, giving result ri;
s = s + ri;
m = s / n;