Monte Carlo methods are a class of
computationComputation 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
algorithmIn 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 simulationA 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
physicalPhysics 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
mathematicalMathematics 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
computerA 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 algorithmIn 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
coupledIn 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 modelThe 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
uncertaintyUncertainty 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
riskRisk 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 integralIntegration 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 overrunA 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 NeumannJohn 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 MetropolisNicholas 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 ProjectThe 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 LaboratoryLos 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 CasinoThe 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:
- Define a domain of possible inputs.
- Generate inputs randomly from a 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.
- Perform a deterministic
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.
- 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
' 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:
- Draw a square on the ground, then inscribe a circle within it.
- Uniformly
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.
- Count the number of objects inside the circle and the total number of objects.
- 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 annealingSimulated 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 needleIn 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 FermiEnrico 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 solitaireCanfield 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 CasinoThe 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
MonacoMonaco , 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 methodIn 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
simulationSimulation 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 ProjectThe 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 AlamosLos 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
physicsPhysics 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 chemistryPhysical chemistry is the study of macroscopic, atomic, subatomic, and particulate phenomena in chemical systems in terms of physical laws and concepts...
, and
operations researchOperations 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 generatorA 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.
SawilowskyShlomo 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
simulationSimulation 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 numberRandom 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,
pseudorandomA 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
simulationSimulation 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-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 samplingPseudo-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 distributionIn 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 methodIn 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 distributionIn 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
uncertaintyUncertainty 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
coupledIn 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 physicsComputational physics is the study and implementation of numerical algorithms to solve problems in physics for which a quantitative theory already exists...
,
physical chemistryPhysical 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 chromodynamicsIn 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 shieldA 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
aerodynamicAerodynamics 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 physicsStatistical 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 modelingMonte 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 dynamicsMolecular 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 theoriesA 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 CarloQuantum 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 problemThe 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 physicsParticle 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
detectorsIn 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
astrophysicsAstrophysics 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
galaxiesA 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 modelsEnsemble 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 forecastingNumerical 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 analysisSensitivity 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 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 analogAn 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 digitalA 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 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 geometallurgyGeometallurgy 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 processingIn 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:...
flowsheetsA 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
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 filterIn 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 filterIn statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...
which form the heart of the SLAMSimultaneous 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 phylogenyBayesian 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 experimentA 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:
- 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
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.
- To provide implementations of hypothesis tests
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 distributionIn 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,
TantrixTantrix 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
BattleshipThe 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 illuminationGlobal 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,
architectureArchitecture 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...
,
designDesign 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
filmA 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 financeMonte 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 derivativesA 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 schedulesProject 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 integrationIn 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
10100A 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 dimensionalityThe 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
dimensionIn 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 freedomA 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-behavedMathematicians 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 numbersIn 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 samplingIn 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 samplingIn 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 algorithmThe 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 methodIn 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 sequenceIn 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 CarloMarkov 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 algorithmIn 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 samplingIn 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 algorithmThe 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 optimizationIn 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 chessComputer 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 optimizationMulti-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 walkA 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 problemAn 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 distributionIn 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 prioriIn 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 algorithmThe 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 algorithmIn 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
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
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 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 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 method uses probabilistic simulation to solve the Boltzmann equation for finite Knudsen number fluid flows....
- 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
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
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
- Overview and reference list, Mathworld
- Video Overview of Top Excel Monte-Carlo Tools and their Main Functionalities, Eric Torkia
- Introduction to Monte Carlo Methods, Computational Science Education Project
- The Basics of Monte Carlo Simulations, University of Nebraska-Lincoln
- Introduction to Monte Carlo simulation (for Microsoft Excel
Microsoft Excel is a proprietary commercial spreadsheet application written and distributed by Microsoft for Microsoft Windows and Mac OS X. It features calculation, graphing tools, pivot tables, and a macro programming language called Visual Basic for Applications...
), Wayne L. Winston
- Monte Carlo Methods – Overview and Concept, brighton-webs.co.uk
- Molecular Monte Carlo Intro, Cooper Union
The Cooper Union for the Advancement of Science and Art, commonly referred to simply as Cooper Union, is a privately funded college in the East Village neighborhood of Manhattan, New York City, United States, located at Cooper Square and Astor Place...
- Monte Carlo techniques applied in physics
- Monte Carlo Method Example, A step-by-step guide to creating a monte carlo excel spreadsheet
- Pricing using Monte Carlo simulation, a practical example, Prof. Giancarlo Vercellino
- Approximate And Double Check Probability Problems Using Monte Carlo method at Orcik Dot Net