Content deleted Content added
Polyamorph (talk | contribs) m clean up, typo(s) fixed: ically- → ically |
Aezarebski (talk | contribs) m →Monte Carlo and random numbers: remove unneccesary statement |
||
| (12 intermediate revisions by 6 users not shown) | |||
Line 3:
{{Use American English|date=February 2024}}
{{Use mdy dates|date=February 2024}}
[[File:Approximation d'une distribution normale.gif|thumb|300px|The approximation of a [[normal distribution]] with a Monte Carlo method]]
'''Monte Carlo methods''', or '''Monte Carlo experiments''', are a broad class of [[computation]]al [[algorithm]]s that rely on [[Resampling (statistics)|repeated]] [[random sampling]] to obtain numerical results. The underlying concept is to use [[randomness]] to solve problems that might be [[deterministic system|deterministic]] in principle. The name comes from the [[Monte Carlo Casino]] in Monaco, where the primary developer of the method, physicist [[Stanisław Ulam|Stanislaw Ulam]], was inspired by his uncle's gambling habits.
Line 16 ⟶ 18:
# Define a domain of possible inputs
# Generate inputs randomly from a [[probability distribution]] over the domain
# Perform a [[Deterministic algorithm|deterministic]] computation
# Aggregate the results
Line 42 ⟶ 44:
In principle, Monte Carlo methods can be used to solve any problem having a probabilistic interpretation. By the [[law of large numbers]], integrals described by the [[expected value]] of some random variable can be approximated by taking the [[Sample mean and sample covariance|empirical mean]] ({{a.k.a.}} the 'sample mean') of independent samples of the variable. When the [[probability distribution]] of the variable is parameterized, mathematicians often use a [[Markov chain Monte Carlo]] (MCMC) sampler.<ref>{{cite journal|title=Equation of State Calculations by Fast Computing Machines |journal=The Journal of Chemical Physics |date=June 1, 1953 |issn=0021-9606 |pages=1087–1092|volume=21|issue=6|doi=10.1063/1.1699114 |author-first1=Nicholas |author-last1=Metropolis |author-first2=Arianna W. |author-last2=Rosenbluth |author-first3=Marshall N. |author-last3=Rosenbluth |author-first4=Augusta H. |author-last4=Teller |author-first5=Edward |author-last5=Teller |bibcode=1953JChPh..21.1087M |osti=4390578 |s2cid=1046577 }}</ref><ref>{{cite journal|title=Monte Carlo sampling methods using Markov chains and their applications |journal=Biometrika |date=April 1, 1970 |issn=0006-3444 |pages=97–109 |volume=57 |issue=1 |doi=10.1093/biomet/57.1.97 |author-first=W. K. |author-last=Hastings |bibcode=1970Bimka..57...97H |s2cid=21204149 }}</ref><ref>{{cite journal|title=The Multiple-Try Method and Local Optimization in Metropolis Sampling |journal=Journal of the American Statistical Association |date=March 1, 2000 |issn=0162-1459 |pages=121–134 |volume=95 |issue=449 |doi=10.1080/01621459.2000.10473908 |author-first1=Jun S. |author-last1=Liu |author-first2=Faming |author-last2=Liang |author-first3=Wing Hung |author-last3=Wong |s2cid=123468109 }}</ref> The central idea is to design a judicious [[Markov chain]] model with a prescribed [[stationary probability distribution]]. That is, in the limit, the samples being generated by the MCMC method will be samples from the desired (target) distribution.<ref>{{cite journal |author-last1=Spall |author-first1=J. C. |year=2003 |title=Estimation via Markov Chain Monte Carlo |doi=10.1109/MCS.2003.1188770 |journal=IEEE Control Systems Magazine |volume=23 |issue=2 |pages=34–45 }}</ref><ref>{{cite journal |doi=10.1109/MCS.2018.2876959 |title=Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects |journal=IEEE Control Systems Magazine |volume=39 |pages=56–67 |year=2019 |author-last1=Hill |author-first1=Stacy D. |author-last2=Spall |author-first2=James C. |s2cid=58672766}}</ref> By the [[ergodic theorem]], the stationary distribution is approximated by the [[empirical measure]]s of the random states of the MCMC sampler.
In other problems, the objective is generating draws from a sequence of probability distributions satisfying a nonlinear evolution equation. These flows of probability distributions can always be interpreted as the distributions of the random states of a [[Markov process]] whose transition probabilities depend on the distributions of the current random states (see [[McKean–Vlasov process]]es, [[particle filter|nonlinear filtering equation]]).<ref name="kol10">{{cite book|author-last=Kolokoltsov |author-first=Vassili |title=Nonlinear Markov processes |year=2010 |publisher=[[Cambridge University Press]] |pages=375}}</ref><ref name="dp13">{{cite book|author-last=Del Moral |author-first=Pierre |title=Mean field simulation for Monte Carlo integration |year=2013 |publisher=Chapman & Hall/[[CRC Press]] |quote=Monographs on Statistics & Applied Probability |url=http://www.crcpress.com/product/isbn/9781466504059 |pages=626}}</ref> In other instances
== Computational costs ==
Line 59 ⟶ 61:
Monte Carlo methods were central to the [[simulation]]s required for the [[Manhattan Project]], though severely limited by the computational tools at the time. Von Neumann, [[Nicholas Metropolis]] and others programmed the [[ENIAC]] computer to perform the first fully automated Monte Carlo calculations, of a [[Nuclear weapon design#Pure fission weapons|fission weapon]] core, in the spring of 1948.<ref name="ENIAC">{{cite journal |author-last1=Haigh |author-first1=Thomas |author-last2=Priestley |author-first2=Mark |author-last3=Rope |author-first3=Crispin |title=Los Alamos Bets on ENIAC: Nuclear Monte Carlo Simulations, 1947-1948 |journal=IEEE Annals of the History of Computing |date=2014 |volume=36 |issue=3 |pages=42–63 |doi=10.1109/MAHC.2014.40 |s2cid=17470931 |url=https://ieeexplore.ieee.org/document/6880250}}</ref> In the 1950s Monte Carlo methods were used at [[Los Alamos National Laboratory|Los Alamos]] for the development of the [[hydrogen bomb]], and became popularized in the fields of [[physics]], [[physical chemistry]], and [[operations research]]. 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.
The theory of more sophisticated mean-field type particle Monte Carlo methods had certainly started by the mid-1960s, with the work of [[Henry McKean|Henry P. McKean Jr.]] on Markov interpretations of a class of nonlinear parabolic partial differential equations arising in fluid mechanics.<ref name="mck67">{{cite journal |author-last=McKean |author-first=Henry P. |title=Propagation of chaos for a class of non-linear parabolic equations |journal=Lecture Series in Differential Equations, Catholic Univ. |year=1967 |volume=7 |pages=41–57 }}</ref><ref>{{cite journal |author-last1=McKean |author-first1=Henry P. |title=A class of Markov processes associated with nonlinear parabolic equations |journal = Proc. Natl. Acad. Sci. USA |year=1966 |volume=56 |issue=6 |pages=1907–1911 |doi=10.1073/pnas.56.6.1907 |pmid=16591437 |pmc=220210 |bibcode=1966PNAS...56.1907M |doi-access=free }}</ref>
[[Quantum Monte Carlo]], and more specifically [[Diffusion Monte Carlo|diffusion Monte Carlo methods]] can also be interpreted as a mean-field particle Monte Carlo approximation of [[Richard Feynman|Feynman]]–[[Mark Kac|Kac]] path integrals.<ref name="dp04">{{cite book |author-last=Del Moral |author-first=Pierre |title=Feynman–Kac formulae. Genealogical and interacting particle approximations |year=2004 |publisher=Springer |quote=Series: Probability and Applications |url=https://www.springer.com/mathematics/probability/book/978-0-387-20268-6 |page=575 |isbn=9780387202686 |series=Probability and Its Applications}}</ref><ref name="dmm002">{{cite book |author-last1=Del Moral |author-first1=P. |author-last2=Miclo |author-first2=L. |title=Séminaire de Probabilités XXXIV |contribution=Branching and interacting particle systems approximations of Feynman–Kac formulae with applications to non-linear filtering |contribution-url=http://archive.numdam.org/item/SPS_2000__34__1_0 |doi=10.1007/BFb0103798 |mr=1768060 |pages=1–145 |publisher=Springer |location=Berlin |series=Lecture Notes in Mathematics |volume=1729 |year=2000 |isbn=978-3-540-67314-9 |url=http://www.numdam.org/item/SPS_2000__34__1_0/}}</ref><ref name="dmm00m">{{cite journal|author-last1=Del Moral |author-first1=Pierre |author-last2=Miclo |author-first2=Laurent |title=A Moran particle system approximation of Feynman–Kac formulae. |journal=Stochastic Processes and Their Applications |year=2000 |volume=86 |issue=2 |pages=193–216 |doi=10.1016/S0304-4149(99)00094-0 |doi-access=free}}</ref><ref name="dm-esaim03">{{cite journal|author-last1=Del Moral |author-first1=Pierre |title=Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman–Kac semigroups |journal=ESAIM Probability & Statistics |date=2003 |volume=7 |pages=171–208 |url=http://journals.cambridge.org/download.php?file=%2FPSS%2FPSS7%2FS1292810003000016a.pdf&code=a0dbaa7ffca871126dc05fe2f918880a |doi=10.1051/ps:2003001 |doi-access=free}}</ref><ref name="caffarel1">{{cite journal|author-last1=Assaraf |author-first1=Roland |author-last2=Caffarel |author-first2=Michel |author-last3=Khelif |author-first3=Anatole |title=Diffusion Monte Carlo Methods with a fixed number of walkers |journal=Phys. Rev. E |url=http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf |date=2000 |volume=61 |issue=4 |pages=4566–4575 |doi=10.1103/physreve.61.4566 |pmid=11088257 |bibcode=2000PhRvE..61.4566A |url-status=dead |archive-url=https://web.archive.org/web/20141107015724/http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf |archive-date=November 7, 2014 }}</ref><ref name="caffarel2">{{cite journal|author-last1=Caffarel |author-first1=Michel |author-last2=Ceperley |author-first2=David |author-last3=Kalos |author-first3=Malvin |title=Comment on Feynman–Kac Path-Integral Calculation of the Ground-State Energies of Atoms |journal=Phys. Rev. Lett. |date=1993 |volume=71 |issue=13 |doi=10.1103/physrevlett.71.2159 |bibcode=1993PhRvL..71.2159C |pages=2159 |pmid=10054598}}</ref><ref name="h84">{{cite journal |author-last=Hetherington |author-first=Jack H. |title=Observations on the statistical iteration of matrices |journal=Phys. Rev. A |date=1984 |volume=30 |issue=2713 |doi=10.1103/PhysRevA.30.2713 |pages=2713–2719 |bibcode=1984PhRvA..30.2713H}}</ref> The origins of Quantum Monte Carlo methods are often attributed to Enrico Fermi and [[Robert D. Richtmyer|Robert Richtmyer]] who developed in 1948 a mean-field particle interpretation of neutron-chain reactions,<ref>{{cite journal|author-last1=Fermi |author-first1=Enrique |author-last2=Richtmyer |author-first2=Robert D. |title = Note on census-taking in Monte Carlo calculations |journal=LAM |date=1948 |volume=805 |issue=A |url=http://scienze-como.uninsubria.it/bressanini/montecarlo-history/fermi-1948.pdf |quote=Declassified report Los Alamos Archive}}</ref> but the first heuristic-like and genetic type particle algorithm (a.k.a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984.<ref name="h84" /> In molecular chemistry, the use of genetic heuristic-like particle methodologies (a.k.a. pruning and enrichment strategies) can be traced back to 1955 with the seminal work of [[Marshall Rosenbluth|Marshall N. Rosenbluth]] and [[Arianna W. Rosenbluth]].<ref name=":0">{{cite journal |author-last1 = Rosenbluth|author-first1=Marshall N. |author-last2=Rosenbluth |author-first2=Arianna W. |title=Monte-Carlo calculations of the average extension of macromolecular chains |journal=J. Chem. Phys. |date=1955 |volume=23 |issue=2 |pages=356–359 |bibcode=1955JChPh..23..356R |doi=10.1063/1.1741967 |s2cid=89611599 |doi-access=free }}</ref>
The use of [[Sequential Monte Carlo method|Sequential Monte Carlo]] in advanced [[signal processing]] and [[Bayesian inference]] is more recent. It was in 1993, that Gordon et al., published in their seminal work<ref>{{cite journal|title=Novel approach to nonlinear/non-Gaussian Bayesian state estimation |journal=IEE Proceedings F - Radar and Signal Processing |date=April 1993 |issn=0956-375X |pages=107–113 |volume=140 |issue=2 |author-first1=N.J. |author-last1=Gordon |author-first2=D.J. |author-last2=Salmond |author-first3 = A.F.M. |author-last3=Smith |doi=10.1049/ip-f-2.1993.0015 |s2cid=12644877 }}</ref> the first application of a Monte Carlo [[Resampling (statistics)|resampling]] algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state-space or the noise of the system.
|author-last=Kitagawa |author-first=G. |year=1996 |title=Monte carlo filter and smoother for non-Gaussian nonlinear state space models |volume=5 |issue=1 |journal=Journal of Computational and Graphical Statistics |pages=1–25 |doi=10.2307/1390750 |jstor=1390750}}</ref> and the ones by Pierre Del Moral<ref name="dm9622">{{cite journal |author-last1=Del Moral |author-first1=Pierre |title=Non Linear Filtering: Interacting Particle Solution. |journal=Markov Processes and Related Fields |date=1996 |volume=2 |issue=4 |pages=555–580 |url=http://web.maths.unsw.edu.au/~peterdel-moral/mprfs.pdf |access-date=June 11, 2015 |archive-date=March 4, 2016 |archive-url=https://web.archive.org/web/20160304052857/http://web.maths.unsw.edu.au/~peterdel-moral/mprfs.pdf |url-status=dead }}</ref> and Himilcon Carvalho, Pierre Del Moral, André Monin and Gérard Salut<ref>{{cite journal |author-last1=Carvalho |author-first1=Himilcon |author-last2=Del Moral |author-first2=Pierre |author-last3=Monin |author-first3=André |author-last4=Salut |author-first4=Gérard |title=Optimal Non-linear Filtering in GPS/INS Integration. |journal=IEEE Transactions on Aerospace and Electronic Systems |date=July 1997 |volume=33 |issue=3 |pages=835–850 |url=http://homepages.laas.fr/monin/Version_anglaise/Publications_files/GPS.pdf |bibcode=1997ITAES..33..835C |doi=10.1109/7.599254 |s2cid=27966240 |access-date=June 11, 2015 |archive-date=November 10, 2022 |archive-url=https://web.archive.org/web/20221110053359/https://homepages.laas.fr/monin/Version_anglaise/Publications_files/GPS.pdf |url-status=dead }}</ref> on particle filters published in the mid-1990s. Particle filters were also developed in signal processing in 1989–1992 by P. Del Moral, J. C. Noyer, G. Rigal, and G. Salut in the LAAS-CNRS in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the [https://www.laas.fr/public/en LAAS-CNRS] (the Laboratory for Analysis and Architecture of Systems) on radar/sonar and GPS signal processing problems.<ref>P. Del Moral, G. Rigal, and G. Salut. "Estimation and nonlinear optimal control: An unified framework for particle solutions". LAAS-CNRS, Toulouse, Research Report no. 91137, DRET-DIGILOG- LAAS/CNRS contract, April (1991).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. "Nonlinear and non Gaussian particle filters applied to inertial platform repositioning." LAAS-CNRS, Toulouse, Research Report no. 92207, STCAN/DIGILOG-LAAS/CNRS Convention STCAN no. A.91.77.013, (94p.) September (1991).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation: Experimental results". Convention DRET no. 89.34.553.00.470.75.01, Research report no.2 (54p.), January (1992).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation: Theoretical results".
Convention DRET no. 89.34.553.00.470.75.01, Research report no.3 (123p.), October (1992).</ref><ref>P. Del Moral, J.-Ch. Noyer, G. Rigal, and G. Salut. "Particle filters in radar signal processing: detection, estimation and air targets recognition". LAAS-CNRS, Toulouse, Research report no. 92495, December (1992).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. "Estimation and nonlinear optimal control: Particle resolution in filtering and estimation". Studies on: Filtering, optimal control, and maximum likelihood estimation. Convention DRET no. 89.34.553.00.470.75.01. Research report no.4 (210p.), January (1993).</ref> These Sequential Monte Carlo methodologies can be interpreted as an acceptance-rejection sampler equipped with an interacting recycling mechanism.
Line 102 ⟶ 104:
[[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]]s.
In an effort to assess the impact of random number quality on Monte Carlo simulation outcomes, astrophysical researchers tested cryptographically secure pseudorandom numbers generated via Intel's [[RDRAND]] instruction set, as compared to those derived from algorithms, like the [[Mersenne Twister]], in Monte Carlo simulations of radio flares from [[brown dwarfs]].
=== Monte Carlo simulation versus "what if" scenarios ===
Line 133 ⟶ 135:
Monte Carlo methods are used in various fields of [[computational biology]], for example for [[Bayesian inference in phylogeny]], or for studying biological systems such as genomes, proteins,{{sfn|Ojeda|Garcia|Londono|Chen|2009}} or membranes.{{sfn|Milik|Skolnick|1993}}
The systems can be studied in the coarse-grained or ''ab initio'' frameworks depending on the desired accuracy.
Computer simulations allow
===Computer graphics===
Line 175 ⟶ 177:
Monte Carlo simulation is commonly used to evaluate the risk and uncertainty that would affect the outcome of different decision options. Monte Carlo simulation allows the business risk analyst to incorporate the total effects of uncertainty in variables like sales volume, commodity and labor prices, interest and exchange rates, as well as the effect of distinct risk events like the cancellation of a contract or the change of a tax law.
[[Monte Carlo methods in finance]] are often used to [[Corporate finance#Quantifying uncertainty|evaluate investments in projects]] at a business unit or corporate level, or other financial valuations. They can be used to model [[project management|project schedules]], where simulations aggregate estimates for worst-case, best-case, and most likely durations for each task to determine outcomes for the overall project.
===Law===
Line 210 ⟶ 212:
Another powerful and very popular application for random numbers in numerical simulation is in [[Optimization (mathematics)|numerical optimization]]. The problem is to minimize (or maximize) functions of some vector that often has many dimensions. Many problems can be phrased in this way: for example, a [[computer chess]] 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]]. It has been applied with quasi-one-dimensional models to solve particle dynamics problems by efficiently exploring large configuration space. Reference<ref>Spall, J. C. (2003), ''Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control'', Wiley, Hoboken, NJ. http://www.jhuapl.edu/ISSO</ref> is a comprehensive review of many issues related to simulation and optimization.
The [[traveling salesman problem]] is what is called a conventional optimization problem. That is, all the facts (distances between each destination point) needed to determine the optimal path to follow are known with certainty and the goal is to run through the possible travel choices to come up with the one with the lowest total distance.
===Inverse problems===
Line 216 ⟶ 218:
As, in the general case, the theory linking data with model parameters is nonlinear, the posterior 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
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.<ref>{{harvnb|Mosegaard|Tarantola|1995}}</ref><ref>{{harvnb|Tarantola|2005}}</ref>
| |||