Content deleted Content added
Citation bot (talk | contribs) Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | #UCB_CommandLine |
Aezarebski (talk | contribs) m →Monte Carlo and random numbers: remove unneccesary statement |
||
| (28 intermediate revisions by 18 users not shown) | |||
Line 1:
{{Short description|Probabilistic problem-solving algorithm}}
{{distinguish|Monte Carlo algorithm}}
{{Use American English|date=February 2024}}
'''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. They are often used in [[physics|physical]] and [[mathematics|mathematical]] problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes:<ref>{{cite journal|author-last1=Kroese |author-first1=D. P. |author-last2=Brereton |author-first2=T. |author-last3=Taimre |author-first3=T. |author-last4=Botev |author-first4=Z. I. |year=2014 |title=Why the Monte Carlo method is so important today |journal = WIREs Comput Stat |volume=6 |issue=6 |pages=386–392 |doi=10.1002/wics.1314 |s2cid=18521840 |url=https://semanticscholar.org/paper/7a56b632de84d0b81f283750b11609a042890639}}</ref> [[optimization]], [[numerical integration]], and generating draws from a [[probability distribution]].▼
{{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]]
In physics-related problems, Monte Carlo methods are useful for simulating systems with many [[coupling (physics)|coupled]] [[degrees of freedom]], such as fluids, disordered materials, strongly coupled solids, and cellular structures (see [[cellular Potts model]], [[interacting particle systems]], [[McKean–Vlasov process]]es, [[kinetic theory of gases|kinetic models of gases]]).▼
'''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.
Other examples include modeling phenomena with significant [[uncertainty]] in inputs such as the calculation of [[risk]] in business and, in mathematics, evaluation of multidimensional [[Integral|definite integral]]s with complicated [[boundary conditions]]. In application to systems engineering problems (space, [[oil exploration]], aircraft design, etc.), Monte Carlo–based predictions of failure, [[cost overrun]]s and schedule overruns are routinely better than human intuition or alternative "soft" methods.<ref>{{cite journal|author-last1=Hubbard |author-first1=Douglas |author-last2=Samuelson |author-first2=Douglas A. |date=October 2009 |title=Modeling Without Measurements |url=http://viewer.zmags.com/publication/357348e6#/357348e6/28 |journal=OR/MS Today |pages=28–33}}</ref>▼
Monte Carlo methods are mainly used in three distinct problem classes: optimization, numerical integration, and generating draws from a probability distribution. They can also be used to model phenomena with significant uncertainty in inputs, such as calculating the risk of a nuclear power plant failure. Monte Carlo methods are often implemented using computer simulations, and they can provide approximate solutions to problems that are otherwise intractable or too complex to analyze mathematically.
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=1 June 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 |url=https://semanticscholar.org/paper/f6a13f116e270dde9d67848495f801cdb8efa25d}}</ref><ref>{{cite journal|title=Monte Carlo sampling methods using Markov chains and their applications |journal=Biometrika |date=1 April 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=1 March 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 |url=https://semanticscholar.org/paper/ff17c129a8d32bb7dc7206230da612e94bd24b9f}}</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.▼
Monte Carlo methods are widely used in various fields of science, engineering, and mathematics, such as physics, chemistry, biology, statistics, artificial intelligence, finance, and cryptography. They have also been applied to social sciences, such as sociology, psychology, and political science. Monte Carlo methods have been recognized as one of the most important and influential ideas of the 20th century, and they have enabled many scientific and technological breakthroughs.
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 we are given a flow of probability distributions with an increasing level of sampling complexity (path spaces models with an increasing time horizon, Boltzmann–Gibbs measures associated with decreasing temperature parameters, and many others). These models can also be seen as the evolution of the law of the random states of a nonlinear Markov chain.<ref name="dp13" /><ref>{{cite journal|title=Sequential Monte Carlo samplers |author-last1=Del Moral |author-first1=P. |author-last2=Doucet |author-first2=A. |author-last3=Jasra |author-first3=A. |year=2006 |doi=10.1111/j.1467-9868.2006.00553.x |volume=68 |issue=3 |journal=Journal of the Royal Statistical Society, Series B |pages=411–436 |arxiv=cond-mat/0212648 |s2cid=12074789 }}</ref> A natural way to simulate these sophisticated nonlinear Markov processes is to sample multiple copies of the process, replacing in the evolution equation the unknown distributions of the random states by the sampled [[empirical measure]]s. In contrast with traditional Monte Carlo and MCMC methodologies, these [[mean-field particle methods|mean-field particle]] techniques rely on sequential interacting samples. The terminology ''mean field'' reflects the fact that each of the ''samples'' ({{a.k.a.}} particles, individuals, walkers, agents, creatures, or phenotypes) interacts with the empirical measures of the process. When the size of the system tends to infinity, these random empirical measures converge to the deterministic distribution of the random states of the nonlinear Markov chain, so that the statistical interaction between particles vanishes.▼
Monte Carlo methods also have some limitations and challenges, such as the trade-off between accuracy and computational cost, the curse of dimensionality, the reliability of random number generators, and the verification and validation of the results.
Despite its conceptual and algorithmic simplicity, the computational cost associated with a Monte Carlo simulation can be staggeringly high. In general the method requires many samples to get a good approximation, which may incur an arbitrarily large total runtime if the processing time of a single sample is high.<ref name="sw09">{{cite book|author-last1=Shonkwiler |author-first1=R. W. |author-last2=Mendivil |author-first2=F. |title=Explorations in Monte Carlo Methods |year=2009 |publisher=Springer}}</ref> Although this is a severe limitation in very complex problems, the [[embarrassingly parallel]] nature of the algorithm allows this large cost to be reduced (perhaps to a feasible level) through [[parallel computing]] strategies in local processors, clusters, cloud computing, GPU, FPGA, etc.<ref>{{cite journal|author-last1=Atanassova |author-first1=E. |author-last2=Gurov |author-first2=T. |author-last3=Karaivanova |author-first3=A. |author-last4=Ivanovska |author-first4=S. |author-last5=Durchova |author-first5=M. |author-last6=Dimitrov |author-first6=D. |year=2016 |title=On the parallelization approaches for Intel MIC architecture |journal=AIP Conference Proceedings |volume=1773 |issue=1 |pages=070001 |doi=10.1063/1.4964983 |bibcode=2016AIPC.1773g0001A}}</ref><ref>{{cite journal|author-last1=Cunha Jr |author-first1=A. |author-last2=Nasser |author-first2=R. |author-last3=Sampaio |author-first3=R. |author-last4=Lopes |author-first4=H. |author-last5=Breitman |author-first5=K. |year=2014 |title=Uncertainty quantification through the Monte Carlo method in a cloud computing setting |journal=Computer Physics Communications |volume=185 |issue=5 |pages=1355–1363 |doi=10.1016/j.cpc.2014.01.006 |arxiv=2105.09512 |bibcode=2014CoPhC.185.1355C |s2cid=32376269}}</ref><ref>{{cite journal|author-last1=Wei |author-first1=J. |author-last2=Kruis |author-first2=F.E. |year=2013 |title=A GPU-based parallelized Monte-Carlo method for particle coagulation using an acceptance–rejection strategy |journal=Chemical Engineering Science |volume=104 |pages=451–459 |doi=10.1016/j.ces.2013.08.008|bibcode=2013ChEnS.104..451W }}</ref><ref>{{cite journal|author-last1=Lin |author-first1=Y. |author-last2=Wang |author-first2=F. |author-last3=Liu |author-first3=B. |year=2018 |title=Random number generators for large-scale parallel Monte Carlo simulations on FPGA |journal = Journal of Computational Physics |volume=360 |pages=93–103 |doi=10.1016/j.jcp.2018.01.029 |bibcode=2018JCoPh.360...93L}}</ref>▼
== Overview ==
Line 17 ⟶ 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
[[File:Pi
For example, consider a [[circular sector#Quadrant|quadrant (circular sector)]] inscribed in a [[unit square]]. Given that the ratio of their areas is {{sfrac|{{pi}}|4}}, the value of [[pi|{{pi}}]] can be approximated using a Monte Carlo method:{{sfn|Kalos|Whitlock|2008}}
# Draw a square, then [[inscribed figure|inscribe]] a quadrant within it
Line 33 ⟶ 34:
Uses of Monte Carlo methods require large amounts of random numbers, and their use benefitted greatly from [[pseudorandom number generators]], which are far quicker to use than the tables of random numbers that had been previously used for statistical sampling.
== Application ==
▲
▲In physics-related problems, Monte Carlo methods are useful for simulating systems with many [[coupling (physics)|coupled]] [[degrees of freedom]], such as fluids, disordered materials, strongly coupled solids, and cellular structures (see [[cellular Potts model]], [[interacting particle systems]], [[McKean–Vlasov process]]es, [[kinetic theory of gases|kinetic models of gases]]).
▲Other examples include modeling phenomena with significant [[uncertainty]] in inputs such as the calculation of [[risk]] in business and, in mathematics, evaluation of multidimensional [[Integral|definite integral]]s with complicated [[boundary conditions]]. In application to systems engineering problems (space, [[oil exploration]], aircraft design, etc.), Monte
▲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=
▲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 ==
▲Despite its conceptual and algorithmic simplicity, the computational cost associated with a Monte Carlo simulation can be staggeringly high. In general the method requires many samples to get a good approximation, which may incur an arbitrarily large total runtime if the processing time of a single sample is high.<ref name="sw09">{{cite book|author-last1=Shonkwiler |author-first1=R. W. |author-last2=Mendivil |author-first2=F. |title=Explorations in Monte Carlo Methods |year=2009 |publisher=Springer}}</ref> Although this is a severe limitation in very complex problems, the [[embarrassingly parallel]] nature of the algorithm allows this large cost to be reduced (perhaps to a feasible level) through [[parallel computing]] strategies in local processors, clusters, cloud computing, GPU, FPGA, etc.<ref>{{cite journal|author-last1=Atanassova |author-first1=E. |author-last2=Gurov |author-first2=T. |author-last3=Karaivanova |author-first3=A. |author-last4=Ivanovska |author-first4=S. |author-last5=Durchova |author-first5=M. |author-last6=Dimitrov |author-first6=D. |year=2016 |title=On the parallelization approaches for Intel MIC architecture |journal=AIP Conference Proceedings |volume=1773 |issue=1 |pages=070001 |doi=10.1063/1.4964983 |bibcode=2016AIPC.1773g0001A}}</ref><ref>{{cite journal|author-last1=Cunha Jr |author-first1=A. |author-last2=Nasser |author-first2=R. |author-last3=Sampaio |author-first3=R. |author-last4=Lopes |author-first4=H. |author-last5=Breitman |author-first5=K. |year=2014 |title=Uncertainty quantification through the Monte Carlo method in a cloud computing setting |journal=Computer Physics Communications |volume=185 |issue=5 |pages=1355–1363 |doi=10.1016/j.cpc.2014.01.006 |arxiv=2105.09512 |bibcode=2014CoPhC.185.1355C |s2cid=32376269}}</ref><ref>{{cite journal|author-last1=Wei |author-first1=J. |author-last2=Kruis |author-first2=F.E. |year=2013 |title=A GPU-based parallelized Monte-Carlo method for particle coagulation using an acceptance–rejection strategy |journal=Chemical Engineering Science |volume=104 |pages=451–459 |doi=10.1016/j.ces.2013.08.008|bibcode=2013ChEnS.104..451W }}</ref><ref>{{cite journal|author-last1=Lin |author-first1=Y. |author-last2=Wang |author-first2=F. |author-last3=Liu |author-first3=B. |year=2018 |title=Random number generators for large-scale parallel Monte Carlo simulations on FPGA |journal = Journal of Computational Physics |volume=360 |pages=93–103 |doi=10.1016/j.jcp.2018.01.029 |bibcode=2018JCoPh.360...93L}}</ref>
== History ==
Line 43 ⟶ 58:
{{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 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=
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 59 ⟶ 74:
==Definitions==
There is no consensus on how ''Monte Carlo'' should be defined. For example, Ripley<ref name=Ripley>{{harvnb|Ripley|1987}}</ref> defines most probabilistic modeling as ''[[stochastic simulation]]'', with ''Monte Carlo'' being reserved for [[Monte Carlo integration]] and Monte Carlo statistical tests. [[Shlomo Sawilowsky|Sawilowsky]]<ref name=Sawilowsky>{{harvnb|Sawilowsky|2003}}</ref> distinguishes between a [[simulation]], a 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 obtain the statistical properties of some phenomenon (or behavior).
Here are the examples:
*Monte Carlo method: Pouring out a box of coins on a table, and then computing the ratio of coins that land heads versus tails is a Monte Carlo method of determining the behavior of repeated coin tosses, but it is not a simulation.▼
*
▲* Monte Carlo method: Pouring out a box of coins on a table, and then computing the ratio of coins that land heads versus tails is a Monte Carlo method of determining the behavior of repeated coin tosses, but it is not a simulation.
* Monte Carlo simulation: Drawing ''a large number'' of pseudo-random uniform variables from the interval [0,1] at one time, or once at many different times, 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<ref name="Kalos">{{harvnb|Kalos|Whitlock|2008}}</ref> 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."
Convergence of the Monte Carlo simulation can be checked with the [[Gelman-Rubin statistic]].
===Monte Carlo and random numbers===
The main idea behind this method is that the results are computed based on repeated random sampling and statistical analysis. The Monte Carlo simulation is, in fact, random experimentations, in the case that, the results of these experiments are not well known.
Monte Carlo simulations are typically characterized by many unknown parameters, many of which are difficult to obtain experimentally.<ref name="usaus">{{cite journal|author-last1=Shojaeefard |author-first1=M.H. |author-last2=Khalkhali |author-first2=A. |author-last3=Yarmohammadisatri |first3=Sadegh |title=An efficient sensitivity analysis method for modified geometry of Macpherson suspension based on Pearson Correlation Coefficient |journal=Vehicle System Dynamics |volume=55 |issue=6 |pages=827–852 |doi=10.1080/00423114.2017.1283046 |year=2017 |bibcode = 2017VSD....55..827S |s2cid=114260173}}</ref> Monte Carlo simulation methods do not always require [[Random number generation#
What this means depends on the application, but typically they should pass a series of statistical tests. Testing that the numbers are [[Uniform distribution (continuous)|uniformly distributed]] 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. Weak correlations between successive samples are also often desirable/necessary.
Sawilowsky lists the characteristics of a high-quality Monte Carlo simulation:<ref name=Sawilowsky/>
* the (pseudo-random) number generator has certain characteristics (e.g. a long "period" before the sequence repeats)
* the (pseudo-random) number generator produces values that pass tests for randomness
* there are enough samples to ensure accurate results
* the proper sampling technique is used
* the algorithm used is valid for what is being modeled
* it simulates the phenomenon in question.
[[Pseudo-random number sampling]] algorithms are used to transform uniformly distributed pseudo-random numbers into numbers that are distributed according to a given [[probability distribution]].
Line 85 ⟶ 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
=== 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.{{sfn|Vose|2008|page=13}}
By contrast, Monte Carlo simulations sample from a [[probability distribution]] for each variable to produce hundreds or thousands of possible outcomes. The results are analyzed to get probabilities of different outcomes occurring.{{sfn|Vose|2008|page=16}} For example, a comparison of a spreadsheet cost construction model run using traditional "what if" scenarios, and then running the comparison again with Monte Carlo simulation and [[triangular distribution|triangular probability distribution]]s shows that the Monte Carlo analysis has a narrower range than the "what if" analysis.{{
==Applications==
Line 98 ⟶ 117:
{{Computational physics}}
{{See also|Monte Carlo method in statistical physics}}
Monte Carlo methods are very important in [[computational physics]], [[physical chemistry]], and related applied fields, and have diverse applications from complicated [[quantum chromodynamics]] calculations to designing [[heat shield]]s and [[aerodynamics|aerodynamic]] forms as well as in modeling radiation transport for radiation dosimetry calculations.<ref>{{cite journal |doi=10.1088/0031-9155/59/4/R151 |pmid=24486639 |volume=59 |issue=4 |title=GPU-based high-performance computing for radiation therapy |journal=Physics in Medicine and Biology |pages=R151–R182 |bibcode=2014PMB....59R.151J |year=2014 |author-last1=Jia |author-first1=Xun |author-last2=Ziegenhein |author-first2=Peter |author-last3=Jiang |author-first3=Steve B |pmc=4003902 }}</ref><ref>{{cite journal |doi=10.1088/0031-9155/59/6/R183 |volume=59 |issue=6 |title=Advances in kilovoltage x-ray beam dosimetry | journal=Physics in Medicine and Biology |pages=R183–R231 |bibcode=2014PMB....59R.183H |pmid=24584183 |date=Mar 2014 |author-last1=Hill |author-first1=R. | last2=Healy |author-first2=B. |author-last3=Holloway |author-first3=L. |author-last4=Kuncic |author-first4=Z. |author-last5=Thwaites |author-first5=D. |author-last6=Baldock |author-first6=C. |s2cid=18082594
===Engineering===
Line 108 ⟶ 127:
* In [[telecommunications]], when planning a wireless network, the design must be proven 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.
* In [[reliability engineering]], Monte Carlo simulation is used to compute system-level response given the component-level response.
* In [[signal processing]] and [[Bayesian inference]], [[particle filter]]s and [[sequential Monte Carlo method|sequential Monte Carlo techniques]] are a class of [[mean-field particle methods]] for sampling and computing the posterior distribution of a signal process given some noisy and partial observations using interacting [[empirical measure]]s.<ref>{{cite journal |author-last1=Chen |author-first1=Shang-Ying |author-last2=Hsu |author-first2=Kuo-Chin |author-last3=Fan |author-first3=Chia-Ming |title=Improvement of generalized finite difference method for stochastic subsurface flow modeling |journal=Journal of Computational Physics |date=
===Climate change and radiative forcing===
The [[IPCC|Intergovernmental Panel on Climate Change]] relies on Monte Carlo methods in [[probability density function]] analysis of [[radiative forcing]].<ref>{{cite book|title=Climate Change 2013 The Physical Science Basis |date=2013 |publisher=[[Cambridge University Press]] |isbn=978-1-107-66182-0 |page=697 |url=http://www.climatechange2013.org/images/report/WG1AR5_ALL_FINAL.pdf |access-date=
===Computational biology===
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 123 ⟶ 142:
===Applied statistics===
The standards for Monte Carlo experiments in statistics were set by Sawilowsky.<ref>{{cite journal |author-last1=Cassey |author-last2=Smith |year=2014 |title=Simulating confidence for the Ellison-Glaeser Index |journal=Journal of Urban Economics |volume=81 |page=93 |doi=10.1016/j.jue.2014.02.005}}</ref> In applied statistics, Monte Carlo methods may be used for at least four 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]]) for [[asymptotic]] conditions (''i. e'', infinite sample size and infinitesimally small treatment effect), real data often do not have such distributions.<ref>{{harvnb|Sawilowsky|Fahoome|2003}}</ref>
# To provide implementations of [[Statistical hypothesis testing|hypothesis tests]] that are more efficient than exact tests such as [[permutation tests]] (which are often impossible to compute) while being more accurate than critical values for [[asymptotic distribution]]s.
# To provide a random sample from the posterior distribution in [[Bayesian inference]]. This sample then approximates and summarizes all the essential features of the posterior.
# To provide efficient random estimates of the Hessian matrix of the negative log-likelihood function that may be averaged to form an estimate of the [[Fisher information]] matrix.<ref>{{cite journal |doi=10.1198/106186005X78800 |title=Monte Carlo Computation of the Fisher Information Matrix in Nonstandard Settings |journal=Journal of Computational and Graphical Statistics |volume=14 |issue=4 |pages=889–909 |year=2005 |author-last1=Spall |author-first1=James C. |citeseerx=10.1.1.142.738 |s2cid=16090098}}</ref><ref>{{cite journal |doi=10.1016/j.csda.2009.09.018 |title=Efficient Monte Carlo computation of Fisher information matrix using prior information |journal=Computational Statistics & Data Analysis |volume=54 |issue=2 |pages=272–289 |year=2010 |author-last1=Das |author-first1=Sonjoy |author-last2=Spall |author-first2=James C. |author-last3=Ghanem |author-first3=Roger}}</ref>
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).
Line 134 ⟶ 153:
===Artificial intelligence for games===
{{Main|Monte Carlo tree search}}
Monte Carlo methods have been developed into a technique called [[Monte-Carlo tree search]] that is useful for searching for the best move in a game. Possible moves are organized in a [[search tree]] and many random simulations are used to estimate the long-term potential of each move. A black box simulator represents the opponent's moves.<ref>{{cite web|url=http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf |title=Monte-Carlo Tree Search: A New Framework for Game AI |author-first1=Guillaume |author-last1=Chaslot |author-first2=Sander |author-last2=Bakkes |author-first3=Istvan |author-last3=Szita |author-first4=Pieter |author-last4=Spronck |website=Sander.landofsand.com |access-date=
The Monte Carlo tree search (MCTS) method has four steps:<ref>{{cite web|url=http://mcts.ai/about/index.html |title=Monte Carlo Tree Search - About|access-date=
# Starting at root node of the tree, select optimal child nodes until a leaf node is reached.
# Expand the leaf node and choose one of its children.
# Play a simulated game starting with that node.
# Use the results of that simulated game to update the node and its ancestors.
The net effect, over the course of many simulated games, is that the value of a node representing a move will go up or down, hopefully corresponding to whether or not that node represents a good move.
Monte Carlo Tree Search has been used successfully to play games such as [[Go (game)|Go]],<ref>{{cite book|chapter=Parallel Monte-Carlo Tree Search |doi=10.1007/978-3-540-87608-3_6 |volume=5131 |pages=60–71 |series=Lecture Notes in Computer Science |year=2008 |author-last1=Chaslot |author-first1=Guillaume M. J. -B |author-last2=Winands |author-first2=Mark H. M. |author-last3=Van Den Herik |author-first3=H. Jaap |title=Computers and Games |isbn=978-3-540-87607-6 |citeseerx=10.1.1.159.4373}}</ref> [[Tantrix]],<ref>{{cite report|url=https://www.tantrix.com/Tantrix/TRobot/MCTS%20Final%20Report.pdf |title=Monte-Carlo Tree Search in the game of Tantrix: Cosc490 Final Report |author-last=Bruns |author-first=Pete}}</ref> [[Battleship (game)|Battleship]],<ref>{{cite web |url=http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/pomcp.pdf |title=Monte-Carlo Planning in Large POMDPs |author-first1=David |author-last1=Silver |author-first2=Joel |author-last2=Veness |website=0.cs.ucl.ac.uk |access-date=
{{See also|Computer Go}}
Line 152 ⟶ 171:
===Search and rescue===
The [[US Coast Guard]] utilizes Monte Carlo methods within its computer modeling software [[SAROPS]] in order to calculate the probable locations of vessels during [[search and rescue]] operations. Each simulation can generate as many as ten thousand data points that are randomly distributed based upon provided variables.<ref>{{cite web|url=http://insights.dice.com/2014/01/03/how-the-coast-guard-uses-analytics-to-search-for-those-lost-at-sea |title=How the Coast Guard Uses Analytics to Search for Those Lost at Sea |work=Dice Insights |date=
===Finance and business===
{{See also|Monte Carlo methods in finance| Quasi-Monte Carlo methods in finance| Monte Carlo methods for option pricing| Stochastic modelling (insurance) | Stochastic asset model}}
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
[[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===
A Monte Carlo approach was used for evaluating the potential value of a proposed program to help female petitioners in Wisconsin be successful in their applications for [[Harassment Restraining Order|harassment]] and [[Domestic Abuse Restraining Order|domestic abuse restraining orders]]. It was proposed to help women succeed in their petitions by providing them with greater advocacy thereby potentially reducing the risk of [[rape]] and [[physical assault]]. However, there were many variables in play that could not be estimated perfectly, including the effectiveness of restraining orders, the success rate of petitioners both with and without advocacy, and many others. The study ran trials that varied these variables to come up with an overall estimate of the success level of the proposed program as a whole.<ref name="montecarloanalysis">{{cite web|url=http://legalaidresearch.org/wp-content/uploads/Research-Increasing-Access-to-REstraining-Order-for-Low-Income-Victims-of-DV-A-Cost-Benefit-Analysis-of-the-Proposed-Domestic-Abuse-Grant-Program.pdf |title=Increasing Access to Restraining Orders for Low Income Victims of Domestic Violence: A Cost-Benefit Analysis of the Proposed Domestic Abuse Grant Program |publisher=[[State Bar of Wisconsin]] |date=December 2006 |access-date=
===Library science===
Monte Carlo approach had also been used to simulate the number of book publications based on book [[Literary genre|genre]] in Malaysia. The Monte Carlo simulation utilized previous published National Book publication data and book's price according to book genre in the local market. The Monte Carlo results were used to determine what kind of book genre that Malaysians are fond of and was used to compare book publications between [[Malaysia]] and [[Japan]].<ref>{{Cite journal|author-last=Dahlan |author-first=Hadi Akbar |date=
===Other===
Line 176 ⟶ 195:
{{Main|Monte Carlo integration}}
[[File:Monte-carlo2.gif|thumb|Monte-Carlo integration works by comparing random points with the value of the function.]]
[[File:Monte-Carlo method (errors).png|thumb|Errors reduce by a factor of <math>\scriptstyle 1/\sqrt{N}</math>.]]
Deterministic [[numerical integration]] 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 [[googol|10<sup>100</sup>]] points are needed for 100 dimensions—far too many to be computed. This is called the [[curse of dimensionality]]. Second, the boundary of a multidimensional region may be very complicated, so it may not be feasible to reduce the problem to an [[iterated integral]].<ref name=Press>{{harvnb|Press|Teukolsky|Vetterling|Flannery|1996}}</ref> 100 [[dimension]]s is by no means unusual, since in many physical problems, a "dimension" is equivalent to a [[degrees of freedom (physics and chemistry)|degree of freedom]].
Line 183 ⟶ 202:
Monte Carlo methods provide a way out of this exponential increase in computation time. As long as the function in question is reasonably [[well-behaved]], 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 [[central limit theorem]], this method displays <math>\scriptstyle 1/\sqrt{N}</math> convergence—i.e., quadrupling the number of sampled points halves the error, regardless of the number of dimensions.<ref name=Press/>
A refinement of this method, known as [[importance sampling]] in statistics, involves sampling the points randomly, but more frequently where the integrand is large. To do this precisely one would have to already know the integral, but one can approximate the integral by an integral of a similar function or use adaptive routines such as [[stratified sampling]], [[Monte Carlo integration#Recursive stratified sampling|recursive stratified sampling]], adaptive umbrella sampling<ref>{{cite journal|last=MEZEI|first=M|title=Adaptive umbrella sampling: Self-consistent determination of the non-Boltzmann bias|journal=Journal of Computational Physics|date=
A similar approach, the [[quasi-Monte Carlo method]], uses [[low-discrepancy sequence]]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.
Line 193 ⟶ 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 199 ⟶ 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>
Line 235 ⟶ 254:
=== Sources ===
{{refbegin}}
* {{cite journal |first = Herbert L. |last = Anderson |author-link = Herbert L. Anderson |url = http://library.lanl.gov/cgi-bin/getfile?00326886.pdf |title = Metropolis, Monte Carlo and the MANIAC |journal = [[Los Alamos Science]] |volume = 14 |pages = 96–108 |year = 1986 }}
* {{cite journal |last = Benov |first = Dobriyan M. |title=The Manhattan Project, the first electronic computer and the Monte Carlo method |journal = Monte Carlo Methods and Applications |volume = 22 |issue = 1 |pages = 73–79 |year=2016 |doi=10.1515/mcma-2016-0102 |s2cid = 30198383 }}
* {{cite journal |first=Stephan A. |last=Baeurle |title = Multiscale modeling of polymer materials using field-theoretic methodologies: A survey about recent developments |journal = Journal of Mathematical Chemistry|volume=46 |issue=2 |pages=363–426 |year=2009 |doi = 10.1007/s10910-008-9467-3 |s2cid=117867762 }}
Line 241 ⟶ 260:
* {{cite book |title=The Monte Carlo Method in Condensed Matter Physics |last=Binder |first=Kurt |author-link=Kurt Binder |year=1995 |publisher=Springer |location=New York |isbn=978-0-387-54369-7 }}
* {{cite book |title = Monte Carlo and quasi-Monte Carlo methods |last=Caflisch |first=R. E. |author-link=Russel E. Caflisch |year=1998 |series = Acta Numerica |volume=7 |publisher=Cambridge University Press |pages=1–49 }}
* {{cite book |last = Davenport |first=J. H.
* {{cite book |title=Sequential Monte Carlo methods in practice |last1=Doucet |first1=Arnaud |last2=Freitas |first2=Nando de |last3=Gordon |first3=Neil |year=2001 |publisher=Springer |location=New York |isbn=978-0-387-95146-1 }}
* {{cite journal |last = Eckhardt |first = Roger |year = 1987 |title = Stan Ulam, John von Neumann, and the Monte Carlo method |journal = Los Alamos Science |issue = 15 |pages = 131–137 |url = http://library.lanl.gov/cgi-bin/getfile?15-13.pdf }}
* {{cite book |title=Monte Carlo: Concepts, Algorithms, and Applications |last=Fishman |first=G. S. |year=1995 |publisher=Springer |location=New York |isbn = 978-0-387-94527-9 }}
* {{cite journal |title = A Monte Carlo tool to simulate breast cancer screening programmes | author = C. Forastero and L. Zamora and D. Guirado and A. Lallena |journal = Phys. Med. Biol. |volume = 55 |issue = 17 |pages = 5213–5229 |year = 2010 |doi = 10.1088/0031-9155/55/17/021 |pmid = 20714045 |bibcode = 2010PMB....55.5213F | s2cid = 30021759 }}
* {{cite journal |first = Leslie M. |last = Golden |title = The Effect of Surface Roughness on the Transmission of Microwave Radiation Through a Planetary Surface |journal = [[Icarus (journal)|Icarus]] |volume = 38 |year = 1979 |pages = 451–455 |bibcode = 1979Icar...38..451G |doi = 10.1016/0019-1035(79)90199-4 |issue = 3 }}
* {{cite book |title = An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems |last1 = Gould |first1 = Harvey |last2=Tobochnik |first2=Jan |year=1988 |publisher=Addison-Wesley |location = Reading |isbn=978-0-201-16504-3 }}
* {{cite book |first1=Charles |last1=Grinstead |first2=
* {{cite book |title = Monte Carlo Methods |last1 = Hammersley |first1=J. M. |last2=Handscomb |first2=D. C. |year=1975 |publisher=Methuen |location=London |isbn=978-0-416-52340-9 }}
* {{cite book |last=Hartmann |first=A.K. |year=2009 |title=Practical Guide to Computer Simulations |publisher=World Scientific |isbn=978-981-283-415-7 |url
* {{cite book |first=Douglas |last=Hubbard |title
* {{cite book |first=Douglas |last=Hubbard |title=The Failure of Risk Management: Why It's Broken and How to Fix It |publisher= [[John Wiley & Sons]] |year=2009 }}
* {{cite book |title=Judgement under Uncertainty: Heuristics and Biases |last1 = Kahneman |first1 = D. |last2=Tversky |first2 = A. |year=1982 |publisher=Cambridge University Press }}
* {{cite book |first1=Malvin H. |last1=Kalos |first2=Paula A. |last2=Whitlock |title=Monte Carlo Methods |publisher=[[Wiley-VCH]] |year=2008 |isbn=978-3-527-40760-6 }}
* {{cite book |title=Handbook of Monte Carlo Methods |last1
* {{cite journal |first1 = H. T.|last1 = MacGillivray |first2 = R. J. |last2=Dodd |title=Monte-Carlo simulations of galaxy systems |journal=[[Astrophysics and Space Science]] |volume = 86 |issue= 2 |pages= 419–435 |year= 1982 |doi = 10.1007/BF00683346 |s2cid = 189849365 }}
* {{cite book |title=Stochastic Simulation in Physics |last=MacKeown |first = P. Kevin |year=1997 |publisher=Springer |location=New York |isbn=978-981-3083-26-4 }}
* {{cite journal |last = Metropolis |first = N. |author-link = Nicholas Metropolis |url = http://library.lanl.gov/cgi-bin/getfile?15-12.pdf |title = The beginning of the Monte Carlo method |journal = Los Alamos Science |issue = 1987 Special Issue dedicated to Stanislaw Ulam |pages = 125–130 |year = 1987 }}
* {{cite journal |last1 = Metropolis |first1 = N. |author1-link = Nicholas Metropolis |last2=Rosenbluth |first2=Arianna W.|last3=Rosenbluth |first3=Marshall N. |last4=Teller |first4=Augusta H. |last5=Teller |first5=Edward |year=1953 |title=Equation of State Calculations by Fast Computing Machines |journal=Journal of Chemical Physics |volume=21 |issue=6 |page=1087 |doi = 10.1063/1.1699114 |bibcode = 1953JChPh..21.1087M |title-link = Equation of State Calculations by Fast Computing Machines |osti = 4390578 |s2cid = 1046577 }}
* {{cite journal |last1 = Metropolis |first1 = N. |author1-link = Nicholas Metropolis |last2 = Ulam |first2 = S. |author-link2=Stanislaw Ulam |year=1949 |title = The Monte Carlo Method |journal = Journal of the American Statistical Association |volume=44 |issue=247 |pages=335–341 |doi = 10.1080/01621459.1949.10483310 |pmid=18139350 |jstor=2280232 }}
* {{cite journal |doi = 10.1002/prot.340150104 |title = Insertion of peptide chains into lipid membranes: an off-lattice Monte Carlo dynamics model |first1 = M. |last1 = Milik |first2 = J. |last2 = Skolnick |journal = Proteins |volume = 15 |issue = 1 |pages = 10–25 |date = Jan 1993 |pmid = 8451235 |s2cid = 7450512
* {{cite journal |last1 = Mosegaard |first1 = Klaus |last2 = Tarantola |first2 = Albert |year = 1995 |title = Monte Carlo sampling of solutions to inverse problems |journal = J. Geophys. Res. |volume = 100 |number = B7 |pages = 12431–12447 |doi = 10.1029/94JB03097 |url = http://www.math.pitt.edu/~cbsg/Materials/MonteCarlo_latex.pdf |bibcode = 1995JGR...10012431M |access-date = November 1, 2017 |archive-date = March 10, 2021 |archive-url = https://web.archive.org/web/20210310023658/http://www.math.pitt.edu/~cbsg/Materials/MonteCarlo_latex.pdf |url-status = dead }}
* {{cite journal |title = Monte Carlo Simulations of Proteins in Cages: Influence of Confinement on the Stability of Intermediate States |first1=P. |last1=Ojeda |first2=M. |last2=Garcia |first3=A. |last3=Londono |first4=N.Y. |last4=Chen |journal = Biophys. J. |volume = 96 |issue = 3 |pages = 1076–1082 |date=Feb 2009 |doi = 10.1529/biophysj.107.125369 |pmid = 18849410 |pmc = 2716574 |bibcode = 2009BpJ....96.1076O }}
* {{cite journal |doi=10.1504/IJVD.2001.001963 |last1 = Int Panis |first1 = L. |last2 = De Nocker |first2 = L. |last3 = De Vlieger |first3 = I. |last4= Torfs |first4=R. |year=2001 |title=Trends and uncertainty in air pollution impacts and external costs of Belgian passenger car traffic|journal= International Journal of Vehicle Design |volume=27 |issue=1–4 |pages=183–194 }}
Line 268 ⟶ 287:
* {{cite book |last1 = Press |first1 = William H. |last2 = Teukolsky |first2 = Saul A. |last3 = Vetterling |first3 = William T. |last4 = Flannery |first4 = Brian P. |title = Numerical Recipes in Fortran 77: The Art of Scientific Computing |edition = 2nd |series = Fortran Numerical Recipes |volume = 1 |year = 1996 |orig-year = 1986 |publisher = [[Cambridge University Press]] |isbn=978-0-521-43064-7 }}
* {{cite book |last = Ripley |first = B. D. |title = Stochastic Simulation |publisher = [[Wiley & Sons]] |year=1987 }}
* {{cite book |title
* {{cite book |title = Simulation and the Monte Carlo Method |last1 = Rubinstein |first1 = R. Y. |last2 = Kroese |first2 = D. P. |year=2007 |edition=2nd |publisher = John Wiley & Sons |location=New York |isbn = 978-0-470-17793-8 }}
* {{cite journal |last = Savvides |first = Savvakis C. |title = Risk Analysis in Investment Appraisal |journal = Project Appraisal Journal |year = 1994 |volume = 9 |issue = 1 |doi = 10.2139/ssrn.265905 |s2cid = 2809643 |url = https://mpra.ub.uni-muenchen.de/10035/1/MPRA_paper_10035.pdf }}
* {{cite book |last1=Sawilowsky |first1=Shlomo S. |last2=Fahoome |first2=Gail C. |year=2003 |title=Statistics via Monte Carlo Simulation with Fortran |location=Rochester Hills, MI |publisher=JMASM |isbn=978-0-9740236-0-1}}
* {{cite journal |last=Sawilowsky |first=Shlomo S. |title=You think you've got trivials? |journal=[[Journal of Modern Applied Statistical Methods]] |volume=2 |issue=1 |pages=218–225 |year=2003 |doi=10.22237/jmasm/1051748460 |doi-access=free |url=https://digitalcommons.wayne.edu/cgi/viewcontent.cgi?article=1744&context=jmasm }}
* {{cite conference |conference=Neural Information Processing Systems 2010 |last1=Silver |first1=David |last2=Veness |first2=Joel |year=2010 |title=Monte-Carlo Planning in Large POMDPs |editor1-last=Lafferty |editor1-first=J. |editor2-last=Williams |editor2-first=C. K. I. |editor3-last=Shawe-Taylor |editor3-first=J. |editor4-last=Zemel |editor4-first=R. S. |editor5-last=Culotta |editor5-first=A. |book-title=Advances in Neural Information Processing Systems 23 |publisher=Neural Information Processing Systems Foundation |url=http://books.nips.cc/papers/files/nips23/NIPS2010_0740.pdf |access-date=March 15, 2011 |archive-date=May 25, 2012 |archive-url=https://web.archive.org/web/20120525143936/http://books.nips.cc/papers/files/nips23/NIPS2010_0740.pdf |url-status=dead }}
* {{cite book |first=László |last=Szirmay-Kalos |title=Monte Carlo Methods in Global Illumination - Photo-realistic Rendering with Randomization |publisher=VDM Verlag Dr. Mueller e.K. |year=2008 |isbn=978-3-8364-7919-6}}
* {{cite book |title = Inverse Problem Theory |last = Tarantola |first = Albert |author-link = Albert Tarantola |year = 2005 |publisher = Society for Industrial and Applied Mathematics |location = Philadelphia |isbn = 978-0-89871-572-9 |url = http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html }}
Line 295 ⟶ 314:
======================= {{No more links}} =============================-->
{{
{{Statistics}}
| |||