Monte Carlo method

Monte Carlo method

Overview
Monte Carlo methods are a class of computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

al algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulation
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...

s of physical
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

 and mathematical
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 systems. These methods are most suited to calculation by a computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

 and tend to be used when it is infeasible to compute an exact result with a deterministic algorithm
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...

. This method is also used to complement the theoretical derivations.

Monte Carlo methods are especially useful for simulating systems with many coupled
Coupling (physics)
In physics, two systems are coupled if they are interacting with each other. Of special interest is the coupling of two vibratory systems by means of springs or magnetic fields, etc...

 degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model
Cellular Potts model
The cellular Potts model is a lattice-based computational modeling method to simulate the collective behavior of cellular structures. Other names for the CPM are extended large-q Potts model and Glazier and Graner model...

).
Discussion
Ask a question about 'Monte Carlo method'
Start a new discussion about 'Monte Carlo method'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Encyclopedia
Monte Carlo methods are a class of computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

al algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulation
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...

s of physical
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

 and mathematical
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 systems. These methods are most suited to calculation by a computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

 and tend to be used when it is infeasible to compute an exact result with a deterministic algorithm
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...

. This method is also used to complement the theoretical derivations.

Monte Carlo methods are especially useful for simulating systems with many coupled
Coupling (physics)
In physics, two systems are coupled if they are interacting with each other. Of special interest is the coupling of two vibratory systems by means of springs or magnetic fields, etc...

 degrees of freedom, such as fluids, disordered materials, strongly coupled solids, and cellular structures (see cellular Potts model
Cellular Potts model
The cellular Potts model is a lattice-based computational modeling method to simulate the collective behavior of cellular structures. Other names for the CPM are extended large-q Potts model and Glazier and Graner model...

). They are used to model phenomena with significant uncertainty
Uncertainty
Uncertainty is a term used in subtly different ways in a number of fields, including physics, philosophy, statistics, economics, finance, insurance, psychology, sociology, engineering, and information science...

 in inputs, such as the calculation of risk
Risk
Risk is the potential that a chosen action or activity will lead to a loss . The notion implies that a choice having an influence on the outcome exists . Potential losses themselves may also be called "risks"...

 in business. They are widely used in mathematics, for example to evaluate multidimensional definite integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

s with complicated boundary conditions. When Monte Carlo simulations have been applied in space exploration and oil exploration, their predictions of failures, cost overrun
Cost overrun
A cost overrun, also known as a cost increase or budget overrun, is an unexpected cost incurred in excess of a budgeted amount due to an under-estimation of the actual cost during budgeting...

s and schedule overruns are routinely better than human intuition or alternative "soft" methods.

The Monte Carlo method was coined in the 1940s by John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...

, Stanislaw Ulam and Nicholas Metropolis
Nicholas Metropolis
Nicholas Constantine Metropolis was a Greek American physicist.-Work:Metropolis received his B.Sc. and Ph.D. degrees in physics at the University of Chicago...

, while they were working on nuclear weapon projects (Manhattan Project
Manhattan Project
The Manhattan Project was a research and development program, led by the United States with participation from the United Kingdom and Canada, that produced the first atomic bomb during World War II. From 1942 to 1946, the project was under the direction of Major General Leslie Groves of the US Army...

) in the Los Alamos National Laboratory
Los Alamos National Laboratory
Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...

. It was named in homage to the Monte Carlo Casino
Monte Carlo Casino
The Monte Carlo Casino is a gambling and entertainment complex located in Monte Carlo, Monaco. It includes a casino, the Grand Théâtre de Monte Carlo, and the office of Les Ballets de Monte Carlo....

, a famous casino where Ulam's uncle would often gamble away his money.

Introduction



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
    Probability distribution
    In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

     over the domain.
  3. Perform a deterministic
    Deterministic algorithm
    In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...

     computation on the inputs.
  4. Aggregate the results.


For example, consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that is /4, the value of
Pi
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...

 can be approximated using a Monte Carlo method:
  1. Draw a square on the ground, then inscribe a circle within it.
  2. Uniformly
    Uniform distribution (continuous)
    In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...

     scatter some objects of uniform size (grains of rice or sand) over the square.
  3. Count the number of objects inside the circle and the total number of objects.
  4. The ratio of the two counts is an estimate of the ratio of the two areas, which is /4. Multiply the result by 4 to estimate .

In this procedure the domain of inputs is the square that circumscribes our circle. We generate random inputs by scattering grains over the square then perform a computation on each input (test whether it falls within the circle). Finally, we aggregate the results to obtain our final result, the approximation of π.

To get an accurate approximation for this procedure should have two other common properties of Monte Carlo methods. First, the inputs should truly be random. If grains are purposefully dropped into only the center of the circle, they will not be uniformly distributed, and so our approximation will be poor. Second, there should be a large number of inputs. The approximation will generally be poor if only a few grains are randomly dropped into the whole square. On average, the approximation improves as more grains are dropped.

History


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 a probabilistic analog (see Simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...

).
An early variant of the Monte Carlo method can be seen in the Buffon's needle
Buffon's needle
In mathematics, Buffon's needle problem is a question first posed in the 18th century by Georges-Louis Leclerc, Comte de Buffon:Buffon's needle was the earliest problem in geometric probability to be solved; it can be solved using integral geometry...

 experiment, in which π can be estimated by dropping needles on a floor made of parallel strips of wood. In the 1930s, Enrico Fermi
Enrico Fermi
Enrico Fermi was an Italian-born, naturalized American physicist particularly known for his work on the development of the first nuclear reactor, Chicago Pile-1, and for his contributions to the development of quantum theory, nuclear and particle physics, and statistical mechanics...

 first experimented with the Monte Carlo method while studying neutron diffusion, but did not publish anything on it.

In 1946, physicists at Los Alamos Scientific Laboratory were investigating radiation shielding and the distance that neutrons would likely travel through various materials. 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 or how much energy the neutron was likely to give off following a collision, the problem could not be solved with analytical calculations. Stanisław Ulam had the idea of 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

Canfield (solitaire)
Canfield is a solitaire card game with a very low probability to win. According to legend, it is originally a casino game, named after the casino owner who is said to have invented it. In England, it is known as Demon.-The story behind the game:...

 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. Later [in 1946], I described the idea to John von Neumann, and we began to plan actual calculations.



–Stanisław Ulam




Being secret, the work of von Neumann and Ulam required a code name. Von Neumann chose the name "Monte Carlo". The name is a reference to the Monte Carlo Casino
Monte Carlo Casino
The Monte Carlo Casino is a gambling and entertainment complex located in Monte Carlo, Monaco. It includes a casino, the Grand Théâtre de Monte Carlo, and the office of Les Ballets de Monte Carlo....

 in Monaco
Monaco
Monaco , officially the Principality of Monaco , is a sovereign city state on the French Riviera. It is bordered on three sides by its neighbour, France, and its centre is about from Italy. Its area is with a population of 35,986 as of 2011 and is the most densely populated country in the...

 where Ulam's uncle would borrow money to gamble. Using lists of "truly" random numbers was extremely slow, von Neumann developed a form of making pseudorandom numbers, using the middle-square method
Middle-square method
In mathematics, the middle-square method is a method of generating pseudorandom numbers. In practice it is not a good method, since its period is usually very short and it has some crippling weaknesses...

. Though this method has been criticized as crude, von Neumann was aware of this: he justified it as being faster than any other method at his disposal, and also noted that when it went awry it did so obviously, unlike methods which could be subtly incorrect.

Monte Carlo methods were central to the simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....

s required for the Manhattan Project
Manhattan Project
The Manhattan Project was a research and development program, led by the United States with participation from the United Kingdom and Canada, that produced the first atomic bomb during World War II. From 1942 to 1946, the project was under the direction of Major General Leslie Groves of the US Army...

, though severely limited by the computational tools at the time. In the 1950s they were used at Los Alamos
Los Alamos National Laboratory
Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...

 for early work relating to the development of the hydrogen bomb, and became popularized in the fields of physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

, physical chemistry
Physical chemistry
Physical chemistry is the study of macroscopic, atomic, subatomic, and particulate phenomena in chemical systems in terms of physical laws and concepts...

, and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

. The Rand Corporation and the U.S. Air Force were two of the major organizations responsible for funding and disseminating information on Monte Carlo methods during this time, and they began to find a wide application in many different fields.

Uses of Monte Carlo methods require large amounts of random numbers, and it was their use that spurred the development of pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...

s, which were far quicker to use than the tables of random numbers that had been previously used for statistical sampling.

Definitions


There is no consensus on how Monte Carlo should be defined. For example, Ripley defines most probabilistic modeling as stochastic simulation, with Monte Carlo being reserved for Monte Carlo integration and Monte Carlo statistical tests. Sawilowsky
Shlomo Sawilowsky
Shlomo S. Sawilowsky is professor of educational statistics and Distinguished Faculty Fellow at Wayne State University in Detroit, Michigan, where he has received teaching, mentoring, and research awards.- Academic career :...

 distinguishes between a simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....

, Monte Carlo method, and a Monte Carlo simulation: a simulation is a fictitious representation of reality, a Monte Carlo method is a technique that can be used to solve a mathematical or statistical problem, and a Monte Carlo simulation uses repeated sampling to determine the properties of some phenomenon (or behavior). Examples:
  • Simulation: Drawing one pseudo-random uniform variable from the interval [0,1] can be used to simulate the tossing of a coin: If the value is less than or equal to 0.50 designate the outcome as heads, but if the value is greater than 0.50 designate the outcome as tails. This is a simulation, but not a Monte Carlo simulation.
  • Monte Carlo method: The area of an irregular figure inscribed in a unit square can be determined by throwing darts at the square and computing the ratio of hits within the irregular figure to the total number of darts thrown. This is a Monte Carlo method of determining area, but not a simulation.
  • Monte Carlo simulation: Drawing a large number of pseudo-random uniform variables from the interval [0,1], and assigning values less than or equal to 0.50 as heads and greater than 0.50 as tails, is a Monte Carlo simulation of the behavior of repeatedly tossing a coin.


Kalos and Whitlock point out that such distinctions are not always easy to maintain. For example, the emission of radiation from atoms is a natural stochastic process. It can be simulated directly, or its average behavior can be described by stochastic equations that can themselves be solved using Monte Carlo methods. "Indeed, the same computer code can be viewed simultaneously as a 'natural simulation' or as a solution of the equations by natural sampling."

Monte Carlo and random numbers


Monte Carlo simulation methods do not always require truly random number
Random number
Random number may refer to:* A number generated for or part of a set exhibiting statistical randomness.* A random sequence obtained from a stochastic process.* An algorithmically random sequence in algorithmic information theory....

s to be useful — while for some applications, such as primality testing, unpredictability is vital. Many of the most useful techniques use deterministic, pseudorandom
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...

 sequences, making it easy to test and re-run simulations. The only quality usually necessary to make good simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....

s is for the pseudo-random sequence to appear "random enough" in a certain sense.

What this means depends on the application, but typically they should pass a series of statistical tests. Testing that the numbers are uniformly distributed
Uniform distribution
-Probability theory:* Discrete uniform distribution* Continuous uniform distribution-Other:* "Uniform distribution modulo 1", see Equidistributed sequence*Uniform distribution , a type of species distribution* Distribution of military uniforms...

 or follow another desired distribution when a large enough number of elements of the sequence are considered is one of the simplest, and most common ones.

Sawilowsky lists the characteristics of a high quality Monte Carlo simulation:
  • the (pseudo-random) number generator has certain characteristics (e. g., a long “period” before the sequence repeats)
  • the (pseudo-random) number generator produces values that pass tests for randomness
  • there are enough samples to ensure accurate results
  • the proper sampling technique is used
  • the algorithm used is valid for what is being modeled
  • it simulates the phenomenon in question.


Pseudo-random number sampling
Pseudo-random number sampling
Pseudo-random number sampling or non-uniform pseudo-random variate generation is the numerical practice of generating pseudo-random numbers that are distributed according to a given probability distribution....

 algorithms are used to transform uniformly distributed pseudo-random numbers into numbers that are distributed according to a given probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

.

Low-discrepancy sequences are often used instead of random sampling from a space as they ensure even coverage and normally have a faster order of convergence than Monte Carlo simulations using random or pseudorandom sequences. Methods based on their use are called quasi-Monte Carlo method
Quasi-Monte Carlo method
In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral that is based on low-discrepancy sequences...

s.

Monte Carlo simulation versus "what if" scenarios


There are ways of using probabilities that are definitely not Monte Carlo simulations—for example, deterministic modeling using single-point estimates. Each uncertain variable within a model is assigned a “best guess” estimate. Scenarios (such as best, worst, or most likely case) for each input variable are chosen and the results recorded.

By contrast, Monte Carlo simulations sample probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

 for each variable to produce hundreds or thousands of possible outcomes. The results are analyzed to get probabilities of different outcomes occurring. For example, a comparison of a spreadsheet cost construction model run using traditional “what if” scenarios, and then run again with Monte Carlo simulation and Triangular probability distributions shows that the Monte Carlo analysis has a narrower range than the “what if” analysis. This is because the “what if” analysis gives equal weight to all scenarios (see quantifying uncertainty in corporate finance).

Applications


Monte Carlo methods are especially useful for simulating phenomena with significant uncertainty
Uncertainty
Uncertainty is a term used in subtly different ways in a number of fields, including physics, philosophy, statistics, economics, finance, insurance, psychology, sociology, engineering, and information science...

 in inputs and systems with a large number of coupled
Coupling (physics)
In physics, two systems are coupled if they are interacting with each other. Of special interest is the coupling of two vibratory systems by means of springs or magnetic fields, etc...

 degrees of freedom. Areas of application include:

Physical sciences



Monte Carlo methods are very important in computational physics
Computational physics
Computational physics is the study and implementation of numerical algorithms to solve problems in physics for which a quantitative theory already exists...

, physical chemistry
Physical chemistry
Physical chemistry is the study of macroscopic, atomic, subatomic, and particulate phenomena in chemical systems in terms of physical laws and concepts...

, and related applied fields, and have diverse applications from complicated quantum chromodynamics
Quantum chromodynamics
In theoretical physics, quantum chromodynamics is a theory of the strong interaction , a fundamental force describing the interactions of the quarks and gluons making up hadrons . It is the study of the SU Yang–Mills theory of color-charged fermions...

 calculations to designing heat shield
Heat shield
A heat shield is designed to shield a substance from absorbing excessive heat from an outside source by either dissipating, reflecting or simply absorbing the heat...

s and aerodynamic
Aerodynamics
Aerodynamics is a branch of dynamics concerned with studying the motion of air, particularly when it interacts with a moving object. Aerodynamics is a subfield of fluid dynamics and gas dynamics, with much theory shared between them. Aerodynamics is often used synonymously with gas dynamics, with...

 forms. In statistical physics
Statistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...

 Monte Carlo molecular modeling
Monte Carlo molecular modeling
Monte Carlo molecular modeling is the application of Monte Carlo methods to molecular problems. These problems can also be modeled by the molecular dynamics method. The difference is that this approach relies on statistical mechanics rather than molecular dynamics. Instead of trying to reproduce...

 is an alternative to computational molecular dynamics
Molecular dynamics
Molecular dynamics is a computer simulation of physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a period of time, giving a view of the motion of the atoms...

, and Monte Carlo methods are used to compute statistical field theories
Statistical field theory
A statistical field theory is any model in statistical mechanics where the degrees of freedom comprise a field or fields. In other words, the microstates of the system are expressed through field configurations...

 of simple particle and polymer systems. Quantum Monte Carlo
Quantum Monte Carlo
Quantum Monte Carlo is a large class of computer algorithms that simulate quantum systems with the idea of solving the quantum many-body problem. They use, in one way or another, the Monte Carlo method to handle the many-dimensional integrals that arise...

 methods solve the many-body problem
Many-body problem
The many-body problem is a general name for a vast category of physical problems pertaining to the properties of microscopic systems made of a large number of interacting particles. Microscopic here implies that quantum mechanics has to be used to provide an accurate description of the system...

 for quantum systems. In experimental particle physics
Particle physics
Particle physics is a branch of physics that studies the existence and interactions of particles that are the constituents of what is usually referred to as matter or radiation. In current understanding, particles are excitations of quantum fields and interact following their dynamics...

, Monte Carlo methods are used for designing detectors
Particle detector
In experimental and applied particle physics, nuclear physics, and nuclear engineering, a particle detector, also known as a radiation detector, is a device used to detect, track, and/or identify high-energy particles, such as those produced by nuclear decay, cosmic radiation, or reactions in a...

, understanding their behavior and comparing experimental data to theory. In astrophysics
Astrophysics
Astrophysics is the branch of astronomy that deals with the physics of the universe, including the physical properties of celestial objects, as well as their interactions and behavior...

, they are used in such diverse manners as to model both the evolution of galaxies
Galaxy
A galaxy is a massive, gravitationally bound system that consists of stars and stellar remnants, an interstellar medium of gas and dust, and an important but poorly understood component tentatively dubbed dark matter. The word galaxy is derived from the Greek galaxias , literally "milky", a...

 and the transmission of microwave radiation through a rough planetary surface.

Monte Carlo methods are also used in the ensemble models
Ensemble forecasting
Ensemble forecasting is a numerical prediction method that is used to attempt to generate a representative sample of the possible future states of a dynamical system...

 that form the basis of modern weather forecasting
Numerical weather prediction
Numerical weather prediction uses mathematical models of the atmosphere and oceans to predict the weather based on current weather conditions. Though first attempted in the 1920s, it was not until the advent of computer simulation in the 1950s that numerical weather predictions produced realistic...

.

Engineering


Monte Carlo methods are widely used in engineering for sensitivity analysis
Sensitivity analysis
Sensitivity analysis is the study of how the variation in the output of a statistical model can be attributed to different variations in the inputs of the model. Put another way, it is a technique for systematically changing variables in a model to determine the effects of such changes.In any...

 and quantitative probabilistic analysis in process design. The need arises from the interactive, co-linear and non-linear behavior of typical process simulations. For example,
  • in microelectronics engineering
    Microelectronics
    Microelectronics is a subfield of electronics. As the name suggests, microelectronics relates to the study and manufacture of very small electronic components. Usually, but not always, this means micrometre-scale or smaller,. These devices are made from semiconductors...

    , Monte Carlo methods are applied to analyze correlated and uncorrelated variations in analog
    Analog signal
    An analog or analogue signal is any continuous signal for which the time varying feature of the signal is a representation of some other time varying quantity, i.e., analogous to another time varying signal. It differs from a digital signal in terms of small fluctuations in the signal which are...

     and digital
    Digital
    A digital system is a data technology that uses discrete values. By contrast, non-digital systems use a continuous range of values to represent information...

     integrated circuits.
  • in geostatistics
    Geostatistics
    Geostatistics is a branch of statistics focusing on spatial or spatiotemporal datasets. Developed originally to predict probability distributions of ore grades for mining operations, it is currently applied in diverse disciplines including petroleum geology, hydrogeology, hydrology, meteorology,...

     and geometallurgy
    Geometallurgy
    Geometallurgy relates to the practice of combining geology or geostatistics with metallurgy, or, more specifically, extractive metallurgy, to create a spatially- or geologically-based predictive model for mineral processing plants. It is used in the hard rock mining industry for risk management...

    , Monte Carlo methods underpin the design of mineral processing
    Mineral processing
    In the field of extractive metallurgy, mineral processing, also known as mineral dressing or ore dressing, is the process of separating commercially valuable minerals from their ores.-History:...

     flowsheets
    Process Flow diagram
    A process flow diagram is a diagram commonly used in engineering to indicate the general flow of plant processes and equipment.The PFD displays the relationship between major equipment of a plant facility and does not show minor details such as piping details and designations...

     and contribute to quantitative risk analysis.
  • impacts of pollution are simulated and diesel compared with petrol.
  • In autonomous robotics, Monte Carlo localization
    Monte Carlo localization
    In robotics and sensors, Monte Carlo localization is a Monte Carlo method to determine the position of a robot given a map of its environment based on Markov localization. It is basically an implementation of the particle filter applied to robot localization, and has become very popular in the...

     can be used to determine the position of a robot, it is often applied to stochastic filters such as the Kalman filter
    Kalman filter
    In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...

     or Particle filter
    Particle filter
    In statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...

     which form the heart of the SLAM
    Simultaneous localization and mapping
    Simultaneous localization and mapping is a technique used by robots and autonomous vehicles to build up a map within an unknown environment , or to update a map within a known environment , while at the same time keeping track of their current location.- Operational definition :Maps are used...

     ( simultaneous Localisation and Mapping ) algorithm.

Computational biology


Monte Carlo methods are used in computational biology, such for as Bayesian inference in phylogeny
Bayesian inference in phylogeny
Bayesian inference in phylogeny generates a posterior distribution for a parameter, composed of a phylogenetic tree and a model of evolution, based on the prior for that parameter and the likelihood of the data, generated by a multiple alignment. The Bayesian approach has become more popular due...

.

Biological systems such as proteins membranes, images of cancer, are being studied by means of computer simulations.

The systems can be studied in the coarse-grained or ab initio frameworks depending on the desired accuracy.
Computer simulations allow us to monitor the local environment of a particular molecule to see if some chemical
reaction is happening for instance. We can also conduct thought experiment
Thought experiment
A thought experiment or Gedankenexperiment considers some hypothesis, theory, or principle for the purpose of thinking through its consequences...

s when the physical experiments are not feasible,
for instance breaking bonds, introducing impurities at specific sites, changing the local/global structure, or introducing external fields.

Applied statistics


In applied statistics, Monte Carlo methods are generally used for two purposes:
  1. To compare competing statistics for small samples under realistic data conditions. Although Type I error and power properties of statistics can be calculated for data drawn from classical theoretical distributions (e.g., normal curve, Cauchy distribution
    Cauchy distribution
    The Cauchy–Lorentz distribution, named after Augustin Cauchy and Hendrik Lorentz, is a continuous probability distribution. As a probability distribution, it is known as the Cauchy distribution, while among physicists, it is known as the Lorentz distribution, Lorentz function, or Breit–Wigner...

    ) for asymptotic conditions (i. e, infinite sample size and infinitesimally small treatment effect), real data often do not have such distributions.
  2. To provide implementations of hypothesis tests
    Statistical hypothesis testing
    A statistical hypothesis test is a method of making decisions using data, whether from a controlled experiment or an observational study . In statistics, a result is called statistically significant if it is unlikely to have occurred by chance alone, according to a pre-determined threshold...

     that are more efficient than exact tests such as permutation tests (which are often impossible to compute) while being more accurate than critical values for asymptotic distribution
    Asymptotic distribution
    In mathematics and statistics, an asymptotic distribution is a hypothetical distribution that is in a sense the "limiting" distribution of a sequence of distributions...

    s.


Monte Carlo methods are also a compromise between approximate randomization and permutation tests. An approximate randomization test is based on a specified subset of all permutations (which entails potentially enormous housekeeping of which permutations have been considered). The Monte Carlo approach is based on a specified number of randomly drawn permutations (exchanging a minor loss in precision if a permutation is drawn twice – or more frequently – for the efficiency of not having to track which permutations have already been selected).

Games




Monte Carlo methods have recently been incorporated in algorithms for playing games that have outperformed previous algorithms in games like Go, Tantrix
Tantrix
Tantrix is a hexagonal tile-based abstract game invented by Mike McManaway from New Zealand. Each of the 56 different tiles in the set contains three lines, going from one edge of the tile to another. No two lines on a tile have the same colour. There are four colours in the set: red, yellow,...

, and Battleship
Battleship (game)
The game Battleship is a guessing game played by two people. It is known throughout the world as a pencil and paper game which predates World War I. It was published by Milton Bradley Company in 1931 as the pad-and-pencil game "Broadsides, the Game of Naval Strategy".-Description:The game is...

. These algorithms employ Monte Carlo tree search. Possible algorithms are organized in a tree and a large number of random simulations are used to estimate the long-term potential of each move. A black box simulator represents the opponent's moves.

In November 2011, a Tantrix playing robot named FullMonte, which employs the Monte Carlo method, played and beat the previous world champion Tantrix robot (Goodbot) quite easily. In a 200 game match FullMonte won 58.5%, lost 36%, and drew 5.5% without ever running over the fifteen minute time limit.

In games like Battleship, where there is only limited knowledge of the state of the system (i.e., the positions of the ships), a belief state is constructed consisting of probabilities for each state and then initial states are sampled for running simulations. The belief state is updated as the game proceeds, as in the figure. On a 10 x 10 grid, in which the total possible number of moves is 100, one algorithm sank all the ships 50 moves faster, on average, than random play.

One of the main problems that this approach has in game playing is that it sometimes misses an isolated, very good move. These approaches are often strong strategically but weak tactically, as tactical decisions tend to rely on a small number of crucial moves which are easily missed by the randomly searching Monte Carlo algorithm.

Design and visuals


Monte Carlo methods have also proven efficient in solving coupled integral differential equations of radiation fields and energy transport, and thus these methods have been used in global illumination
Global illumination
Global illumination is a general name for a group of algorithms used in 3D computer graphics that are meant to add more realistic lighting to 3D scenes...

 computations which produce photo-realistic images of virtual 3D models, with applications in video games, architecture
Architecture
Architecture is both the process and product of planning, designing and construction. Architectural works, in the material form of buildings, are often perceived as cultural and political symbols and as works of art...

, design
Design
Design as a noun informally refers to a plan or convention for the construction of an object or a system while “to design” refers to making this plan...

, computer generated film
Film
A film, also called a movie or motion picture, is a series of still or moving images. It is produced by recording photographic images with cameras, or by creating images using animation techniques or visual effects...

s, and cinematic special effects.

Finance and business



Monte Carlo methods in finance
Monte Carlo methods in finance
Monte Carlo methods are used in finance and mathematical finance to value and analyze instruments, portfolios and investments by simulating the various sources of uncertainty affecting their value, and then determining their average value over the range of resultant outcomes. This is usually done...

 are often used to calculate the value of companies, to evaluate investments in projects at a business unit or corporate level, or to evaluate financial derivatives
Derivative (finance)
A derivative instrument is a contract between two parties that specifies conditions—in particular, dates and the resulting values of the underlying variables—under which payments, or payoffs, are to be made between the parties.Under U.S...

. They can be used to model project schedules
Project management
Project management is the discipline of planning, organizing, securing, and managing resources to achieve specific goals. A project is a temporary endeavor with a defined beginning and end , undertaken to meet unique goals and objectives, typically to bring about beneficial change or added value...

, where simulations aggregate estimates for worst-case, best-case, and most likely durations for each task to determine outcomes for the overall project.

Telecommunications


When planning a wireless network, design must be proved to work for a wide variety of scenarios that depend mainly on the number of users, their locations and the services they want to use. Monte Carlo methods are typically used to generate these users and their states. The network performance is then evaluated and, if results are not satisfactory, the network design goes through an optimization process.

Use in mathematics


In general, Monte Carlo methods are used in mathematics to solve various problems by generating suitable random numbers and observing that fraction of the numbers which obeys some property or properties. The method is useful for obtaining numerical solutions to problems which are too complicated to solve analytically. The most common application of the Monte Carlo method is Monte Carlo integration.

Integration



Deterministic numerical integration
Numerical integration
In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations. This article focuses on calculation of...

 algorithms work well in a small number of dimensions, but encounter two problems when the functions have many variables. First, the number of function evaluations needed increases rapidly with the number of dimensions. For example, if 10 evaluations provide adequate accuracy in one dimension, then 10100
Googol
A googol is the large number 10100, that is, the digit 1 followed by 100 zeros:The term was coined in 1938 by 9-year-old Milton Sirotta , nephew of American mathematician Edward Kasner...

 points are needed for 100 dimensions—far too many to be computed. This is called the curse of dimensionality
Curse of dimensionality
The curse of dimensionality refers to various phenomena that arise when analyzing and organizing high-dimensional spaces that do not occur in low-dimensional settings such as the physical space commonly modeled with just three dimensions.There are multiple phenomena referred to by this name in...

. Second, the boundary of a multidimensional region may be very complicated, so it may not be feasible to reduce the problem to a series of nested one-dimensional integrals. 100 dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...

s is by no means unusual, since in many physical problems, a "dimension" is equivalent to a degree of freedom
Degrees of freedom (physics and chemistry)
A degree of freedom is an independent physical parameter, often called a dimension, in the formal description of the state of a physical system...

.

Monte Carlo methods provide a way out of this exponential increase in computation time. As long as the function in question is reasonably well-behaved
Well-behaved
Mathematicians very frequently speak of whether a mathematical object — a function, a set, a space of one sort or another — is "well-behaved" or not. The term has no fixed formal definition, and is dependent on mathematical interests, fashion, and taste...

, it can be estimated by randomly selecting points in 100-dimensional space, and taking some kind of average of the function values at these points. By the law of large numbers
Law of large numbers
In probability theory, the law of large numbers is a theorem that describes the result of performing the same experiment a large number of times...

, this method will display convergence—i.e., quadrupling the number of sampled points will halve the error, regardless of the number of dimensions.

A refinement of this method, known as importance sampling
Importance sampling
In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution rather than the distribution of interest. It is related to Umbrella sampling in computational physics...

 in statistics, involves sampling the points randomly, but more frequently where the integrand is large. To do this precisely one would have to already know the integral, but one can approximate the integral by an integral of a similar function or use adaptive routines such as Stratified sampling
Stratified sampling
In statistics, stratified sampling is a method of sampling from a population.In statistical surveys, when subpopulations within an overall population vary, it is advantageous to sample each subpopulation independently. Stratification is the process of dividing members of the population into...

, recursive stratified sampling, adaptive umbrella sampling or the VEGAS algorithm
VEGAS algorithm
The VEGAS algorithm, due to G. P. Lepage, is a method for reducing error in Monte Carlo simulations by using a known or approximate probability distribution function to concentrate the search in those areas of the graph that make the greatest contribution to the final integral.The VEGAS algorithm...

.

A similar approach, the quasi-Monte Carlo method
Quasi-Monte Carlo method
In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral that is based on low-discrepancy sequences...

, uses low-discrepancy sequence
Low-discrepancy sequence
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a low discrepancy....

s. These sequences "fill" the area better and sample the most important points more frequently, so quasi-Monte Carlo methods can often converge on the integral more quickly.

Another class of methods for sampling points in a volume is to simulate random walks over it (Markov chain Monte Carlo
Markov chain Monte Carlo
Markov chain Monte Carlo methods are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the...

). Such methods include the Metropolis-Hastings algorithm
Metropolis-Hastings algorithm
In mathematics and physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult...

, Gibbs sampling
Gibbs sampling
In statistics and in statistical physics, Gibbs sampling or a Gibbs sampler is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables...

 and the Wang and Landau algorithm
Wang and Landau algorithm
The Wang and Landau algorithm proposed by Fugao Wang and David P. Landau is an extension of Metropolis Monte Carlo sampling. It is designed to calculate the density of states of a computer-simulated system, such as an Ising model of spin glasses, or model atoms in a molecular force field...

.

Optimization



Another powerful and very popular application for random numbers in numerical simulation is in numerical optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

. The problem is to minimize (or maximize) functions of some vector that often has a large number of dimensions. Many problems can be phrased in this way: for example, a computer chess
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...

 program could be seen as trying to find the set of, say, 10 moves that produces the best evaluation function at the end. In the traveling salesman problem the goal is to minimize distance traveled. There are also applications to engineering design, such as multidisciplinary design optimization
Multidisciplinary design optimization
Multi-disciplinary design optimization is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. As defined by Prof. Carlo Poloni, MDO is "the art of finding the best compromise"...

.

Most Monte Carlo optimization methods are based on random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...

s. Essentially, the program moves randomly on a multi-dimensional surface, preferring moves that reduce the function, but sometimes moving "uphill".

Inverse problems


Probabilistic formulation of inverse problem
Inverse problem
An inverse problem is a general framework that is used to convert observed measurements into information about a physical object or system that we are interested in...

s leads to the definition of a probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

 in the model space. This probability distribution combines a priori
A priori (statistics)
In statistics, a priori knowledge is prior knowledge about a population, rather than that estimated by recent observation. It is common in Bayesian inference to make inferences conditional upon this knowledge, and the integration of a priori knowledge is the central difference between the Bayesian...

 information with new information obtained by measuring some observable parameters (data). As, in the general case, the theory linking data with model parameters is nonlinear, the a posteriori probability in the model space may not be easy to describe (it may be multimodal, some moments may not be defined, etc.).

When analyzing an inverse problem, obtaining a maximum likelihood model is usually not sufficient, as we normally also wish to have information on the resolution power of the data. In the general case we may have a large number of model parameters, and an inspection of the marginal probability densities of interest may be impractical, or even useless. But it is possible to pseudorandomly generate a large collection of models according to the posterior probability distribution and to analyze and display the models in such a way that information on the relative likelihoods of model properties is conveyed to the spectator. This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the a priori distribution is available.

The best-known importance sampling method, the Metropolis algorithm, can be generalized, and this gives a method that allows analysis of (possibly highly nonlinear) inverse problems with complex a priori information and data with an arbitrary noise distribution.

Computational mathematics


Monte Carlo methods are useful in many areas of computational mathematics, where a "lucky choice" can find the correct result. A classic example is Rabin's algorithm
Miller-Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithmwhich determines whether a given number is prime,...

 for primality testing: for any n which is not prime, a random x has at least a 75% chance of proving that n is not prime. Hence, if n is not prime, but x says that it might be, we have observed at most a 1-in-4 event. If 10 different random x say that "n is probably prime" when it is not, we have observed a one-in-a-million event. In general a Monte Carlo algorithm of this kind produces one correct answer with a guarantee n is composite, and x proves it so, but another one without, but with a guarantee of not getting this answer when it is wrong too often—in this case at most 25% of the time. See also Las Vegas algorithm
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the verity of the result; it gambles only with the resources...

 for a related, but different, idea.

See also


Application areas
  • Modeling light transport in biological tissue
    Monte Carlo method for photon transport
    Modeling photon propagation with Monte Carlo methods is a flexible yet rigorous approach to simulate photon transport. In the method, local rules of photon transport are expressed as probability distributions which describe the step size of photon movement between sites of photon-tissue interaction...

  • Monte Carlo methods for electron transport
    Monte Carlo methods for electron transport
    The Monte Carlo method for electron transport is a semiclassical Monte Carlo approach of modeling semiconductor transport. Assuming the carrier motion consists of free flights interrupted by scattering mechanisms, a computer is utilized to simulate the trajectories of particles as they move across...

  • Biology Monte Carlo method
    Biology Monte Carlo method
    Biology Monte Carlo methods have been developed at the University of Illinois at Urbana-Champaign to simulate ion transport in an electrolyte environment through ion channels or nano-pores embedded in membranes...



Other methods employing Monte Carlo
  • Auxiliary field Monte Carlo
    Auxiliary field Monte Carlo
    Auxiliary field Monte Carlo is a method that allows the calculation, by use of Monte Carlo techniques, of averages of operators in many-body quantum mechanical or classical problems .-Reweighting procedure and numerical sign problem:The distinctive ingredient of "auxiliary field Monte Carlo" is...

  • Direct simulation Monte Carlo
    Direct simulation Monte Carlo
    Direct Simulation Monte Carlo method uses probabilistic simulation to solve the Boltzmann equation for finite Knudsen number fluid flows....

  • Dynamic Monte Carlo method
    Dynamic Monte Carlo method
    In chemistry, dynamic Monte Carlo is a method for modeling the dynamic behaviors of molecules by comparing the rates of individual steps with random numbers...

  • Kinetic Monte Carlo
    Kinetic Monte Carlo
    The kinetic Monte Carlo method is a Monte Carlo method computer simulation intended to simulate the time evolution of some processes occurring in nature. Typically these are processes that occur with a given known rate...

  • Morris method
    Morris method
    In applied statistics, the Morris method for global sensitivity analysis is a so-called one-step-at-a-time method , meaning that in each run only one input parameter is given a new value. It facilitates a global sensitivity analysis by making a number r of local changes at different points x of the...

  • List of software for Monte Carlo molecular modeling


External links