Editing Monte Carlo method (section)

== 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 [[Probability|probabilistic]] [[metaheuristic]]s (see [[simulated annealing]]).

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

In the late 1940s, [[Stanisław Ulam]] invented the modern version of the Markov Chain Monte Carlo method while he was working on nuclear weapons projects at the [[Los Alamos National Laboratory]]. In 1946, nuclear weapons physicists at Los Alamos were investigating neutron diffusion in the core of a nuclear weapon.{{sfn|Metropolis|1987}} Despite having most of the necessary data, such as the average distance a neutron would travel in a substance before it collided with an atomic nucleus and how much energy the neutron was likely to give off following a collision, the Los Alamos physicists were unable to solve the problem using conventional, deterministic mathematical methods. Ulam proposed using random experiments. He recounts his inspiration as follows:

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

Being secret, the work of von Neumann and Ulam required a code name.{{sfn|Mazhdrakov|Benov|Valkanov|2018|p=250}} A colleague of von Neumann and Ulam, [[Nicholas Metropolis]], suggested using the name ''Monte Carlo'', which refers to the [[Monte Carlo Casino]] in [[Monaco]] where Ulam's uncle would borrow money from relatives to gamble.{{sfn|Metropolis|1987}}
Monte Carlo methods were central to the [[simulation]]s required for further postwar development of nuclear weapons, including the design of the H-bomb, 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> An earlier pioneering article by [[Ted Harris (mathematician)|Theodore E. Harris]] and Herman Kahn, published in 1951, used mean-field [[genetic algorithm|genetic]]-type Monte Carlo methods for estimating particle transmission energies.<ref>{{cite journal |author-last1=Herman |author-first1=Kahn |author-last2=Theodore |author-first2=Harris E. |title=Estimation of particle transmission by random sampling |journal=Natl. Bur. Stand. Appl. Math. Ser. |year=1951 |volume=12 |pages=27–30 |url=https://dornsifecms.usc.edu/assets/sites/520/docs/kahnharris.pdf }}</ref> Mean-field genetic type Monte Carlo methodologies are also used as heuristic natural search algorithms (a.k.a. [[metaheuristic]]) in evolutionary computing. The origins of these mean-field computational techniques can be traced to 1950 and 1954 with the work of [[Alan Turing]] on genetic type mutation-selection learning machines<ref>{{cite journal |author-last=Turing |author-first=Alan M. |title=Computing machinery and intelligence |journal=Mind |volume=LIX |issue=238 |pages=433–460 |doi=10.1093/mind/LIX.236.433 |year=1950 }}</ref> and the articles by [[Nils Aall Barricelli]] at the [[Institute for Advanced Study]] in [[Princeton, New Jersey]].<ref>{{cite journal |author-last=Barricelli |author-first=Nils Aall |year=1954 |author-link=Nils Aall Barricelli |title=Esempi numerici di processi di evoluzione |journal=Methodos |pages=45–68 }}</ref><ref>{{cite journal |author-last=Barricelli |author-first=Nils Aall |year=1957 |author-link=Nils Aall Barricelli |title=Symbiogenetic evolution processes realized by artificial methods |journal=Methodos |pages=143–182 }}</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. Another pioneering article in this field was Genshiro Kitagawa's, on a related "Monte Carlo filter",<ref>{{cite journal
 |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.

From 1950 to 1996, all the publications on Sequential Monte Carlo methodologies, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and on genealogical and ancestral tree based algorithms. The mathematical foundations and the first rigorous analysis of these particle algorithms were written by Pierre Del Moral in 1996.<ref name="dm9622"/><ref name=":22">{{cite journal|author-last1=Del Moral |author-first1=Pierre |title=Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems |journal=Annals of Applied Probability |date=1998 |edition=Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996) |volume=8 |issue=2 |pages=438–495 |url=http://projecteuclid.org/download/pdf_1/euclid.aoap/1028903535 |doi=10.1214/aoap/1028903535 |citeseerx=10.1.1.55.5257}}</ref>

Branching type particle methodologies with varying population sizes were also developed in the end of the 1990s by Dan Crisan, Jessica Gaines and Terry Lyons,<ref name=":42">{{cite journal|author-last1=Crisan |author-first1=Dan |author-last2=Gaines |author-first2=Jessica |author-last3=Lyons |author-first3=Terry |title=Convergence of a branching particle method to the solution of the Zakai |journal=SIAM Journal on Applied Mathematics |date=1998 |volume=58 |issue=5 |pages=1568–1590 |doi=10.1137/s0036139996307371 |s2cid=39982562 }}</ref><ref>{{cite journal|author-last1=Crisan |author-first1=Dan |author-last2=Lyons |author-first2=Terry |title=Nonlinear filtering and measure-valued processes |journal=Probability Theory and Related Fields |date=1997 |volume=109 |issue=2 |pages=217–244 |doi=10.1007/s004400050131 |s2cid=119809371|doi-access=free }}</ref><ref>{{cite journal|author-last1=Crisan |author-first1=Dan |author-last2=Lyons |author-first2=Terry |title=A particle approximation of the solution of the Kushner–Stratonovitch equation |journal=Probability Theory and Related Fields |date=1999 |volume=115 |issue=4 |pages=549–578 |doi=10.1007/s004400050249 |s2cid=117725141|doi-access=free }}</ref> and by Dan Crisan, Pierre Del Moral and Terry Lyons.<ref name=":52">{{cite journal|author-last1=Crisan |author-first1=Dan |author-last2=Del Moral |author-first2=Pierre |author-last3=Lyons |author-first3=Terry |title=Discrete filtering using branching and interacting particle systems |journal=Markov Processes and Related Fields |date=1999 |volume=5 |issue=3 |pages=293–318 |url=http://web.maths.unsw.edu.au/~peterdel-moral/crisan98discrete.pdf}}</ref> Further developments in this field were described in 1999 to 2001 by P. Del Moral, A. Guionnet and L. Miclo.<ref name="dmm002"/><ref name="dg99">{{cite journal|author-last1=Del Moral |author-first1=Pierre |author-last2=Guionnet |author-first2=Alice |title=On the stability of Measure Valued Processes with Applications to filtering |journal=C. R. Acad. Sci. Paris |date=1999 |volume=39 |issue=1 |pages=429–434}}</ref><ref name="dg01">{{cite journal|author-last1=Del Moral |author-first1=Pierre |author-last2=Guionnet |author-first2=Alice |title=On the stability of interacting processes with applications to filtering and genetic algorithms |journal=Annales de l'Institut Henri Poincaré |date=2001 |volume=37 |issue=2 |pages=155–194 |url=http://web.maths.unsw.edu.au/~peterdel-moral/ihp.ps|doi = 10.1016/s0246-0203(00)01064-5 |bibcode=2001AIHPB..37..155D}}</ref>