Editing Monte Carlo method (section)

==Use in mathematics==
In general, the Monte Carlo methods are used in mathematics to solve various problems by generating suitable random numbers (see also [[Random number generation]]) and observing that fraction of the numbers that obeys some property or properties. The method is useful for obtaining numerical solutions to problems too complicated to solve analytically. The most common application of the Monte Carlo method is Monte Carlo integration.

=== Integration ===
{{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]].

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=December 31, 1986|volume=68|issue=1|pages=237–248|doi=10.1016/0021-9991(87)90054-4|bibcode = 1987JCoPh..68..237M}}</ref><ref>{{cite journal|last1=Bartels|first1=Christian|last2=Karplus|first2=Martin|title=Probability Distributions for Complex Systems: Adaptive Umbrella Sampling of the Potential Energy|journal=The Journal of Physical Chemistry B|date=December 31, 1997|volume=102|issue=5|pages=865–880|doi=10.1021/jp972280j}}</ref> or the [[VEGAS algorithm]].

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.

Another class of methods for sampling points in a volume is to simulate random walks over it ([[Markov chain Monte Carlo]]). Such methods include the [[Metropolis–Hastings algorithm]], [[Gibbs sampling]], [[Wang and Landau algorithm]], and interacting type MCMC methodologies such as the [[Particle filter|sequential Monte Carlo]] samplers.<ref>{{Cite journal|title = Sequential Monte Carlo samplers|journal = Journal of the Royal Statistical Society, Series B|doi=10.1111/j.1467-9868.2006.00553.x|volume=68|issue = 3|pages=411–436|year = 2006|last1 = Del Moral|first1 = Pierre|last2 = Doucet|first2 = Arnaud|last3 = Jasra|first3 = Ajay|arxiv = cond-mat/0212648|s2cid = 12074789}}</ref>

=== Simulation and optimization ===
{{Main|Stochastic optimization}}
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. If instead of the goal being to minimize the total distance traveled to visit each desired destination but rather to minimize the total time needed to reach each destination, this goes beyond conventional optimization since travel time is inherently uncertain (traffic jams, time of day, etc.). As a result, to determine the optimal path a different simulation is required: optimization to first understand the range of potential times it could take to go from one point to another (represented by a probability distribution in this case rather than a specific distance) and then optimize the travel decisions to identify the best path to follow taking that uncertainty into account.

===Inverse problems===
Probabilistic formulation of [[inverse problem]]s leads to the definition of a [[probability distribution]] in the model space. This probability distribution combines [[prior probability|prior]] information with new information obtained by measuring some observable parameters (data).
As, in the general case, the theory linking data with model parameters is nonlinear, the 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 normally information on the resolution power of the data is desired. In the general case many parameters are modeled, and an inspection of the [[marginal probability]] densities of interest may be impractical, or even useless. But it is possible to pseudorandomly generate a large collection of models according to the [[posterior probability distribution]] and to analyze and display the models in such a way that information on the relative likelihoods of model properties is conveyed to the spectator. This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the ''a priori'' distribution is available.

The best-known importance sampling method, the Metropolis algorithm, can be generalized, and this gives a method that allows analysis of (possibly highly nonlinear) inverse problems with complex ''a priori'' information and data with an arbitrary noise distribution.<ref>{{harvnb|Mosegaard|Tarantola|1995}}</ref><ref>{{harvnb|Tarantola|2005}}</ref>

===Philosophy===
Popular exposition of the Monte Carlo Method was conducted by McCracken.<ref>McCracken, D. D., (1955) The Monte Carlo Method, Scientific American, 192(5), pp. 90-97</ref> The method's general philosophy was discussed by [[Elishakoff]]<ref>Elishakoff, I., (2003) Notes on Philosophy of the Monte Carlo Method, International Applied Mechanics, 39(7), pp.753-762</ref> and Grüne-Yanoff and Weirich.<ref>Grüne-Yanoff, T., & Weirich, P. (2010). The philosophy and epistemology of simulation: A review, Simulation & Gaming, 41(1), pp. 20-50</ref>