请输入您要查询的字词:

 

单词 MonteCarloSimulation
释义

Monte Carlo simulation


Monte Carlo simulationis the use of randomized numerical experimentsto evaluate mathematical expressions.

In the typical problems addressed by Monte Carlo simulation,the search space or sample space is countably or uncountably infinite.In contrast to determistic algorithms that sweep a finite subset of pointsin the search space in order to derive a solutionto the problem, Monte Carlo simulation randomizes the selectionof points in the hope that good representatives for the solutionof the problem are chosen.

Monte Carlo integration

The term Monte Carlo simulation most oftenrefers to integration by randomized methods.The problem is to evaluate the expectation or integral

𝔼X=X𝑑

of a real-valuedrandom variableMathworldPlanetmath X on a probability spaceMathworldPlanetmath.The expectation is approximated by taking the sample meanMathworldPlanetmathof independentPlanetmathPlanetmath observations {Xi} with the same distributionPlanetmathPlanetmathPlanetmathas X:

𝔼X1ni=1nXi.

By the strong law of large numbersMathworldPlanetmath, the sample meanconverges almost surely, as n, to the true mean 𝔼X.

Typically the distribution of X is not known in closed form;otherwise we would be able to use the standard numerical quadraturetechniques to compute the one-dimensional integral representing 𝔼X,and one-variable quadraturein general tend to work better than the Monte Carlo method.

Rather, the random variable X=f(Y) is expressed as some function fof another random variable Y, and we know how to compute fand randomized samples of Y.Then

𝔼X=𝔼[f(Y)]1ni=1nf(Yi)

for independent samples {Yi}for the random variable Y.

The realizations Yimay be obtained by generating random (or pseudo-random)samples according to the known distribution for Y.Or, in some cases, they may be obtained from pre-tabulatedobservations, e.g. based on past observations in the real world.

Bounds on error

If X1,X2, are identically and independently distributed,with mean m and varianceMathworldPlanetmath v,then

1ni=1nXi-mv

converges in distribution,as n, to the standard normal distributionMathworldPlanetmath.Then for any δ>0, and for large n, we have

Pr(-δ<1ni=1nXi-mv<δ)2Φ(δ)-1,

approximating the true distribution with the Gaussian cumulativedistribution functionMathworldPlanetmath Φ.Setting (1-α)×100%=2Φ(δ)-1 as the requiredconfidence level,we have δ=Φ-1(1-α/2).

Thus, given an observation of the sample meanfrom a run of the Monte Carlo simulation,with (1-α)×100% confidence,the true mean 𝔼X is approximatelywithin

±δvn=±vnΦ-1(1-α/2)

of the sample mean.

Since the computed sample mean is random,it is in general not possible to obtain actual error bounds,in the usual sense of the word,as with determistic algorithms.Instead, the confidence interval size,or the standard deviationMathworldPlanetmath of (1/n)i=1nXi,is used as a measure of the error of Monte Carlo simulation;this is sometimes called a probabilistic error bound.

Observe that the probabilistic error bound ofthe Monte Carlo simulation decreases as 1/n.

Comparison with other methods

Simplicity.

The chief advantage of Monte Carlo simulation,compared to the other numerical methods that can solve the sameproblem, is that it is conceptually very simple.It does not require specific knowledge of the form of the solutionor its analytic properties.Monte Carlo is also relatively easy to implement on a computer.

Slowness.

The main disadvantage of Monte Carlo integrationis that it is slow.Many samples may berequired — on the order of thousands or even millions —to obtain acceptable precision in the answer.In particular, since the probabilistic error bounddecreases as the reciprocal square root of the number of iterations,to achieve one more decimal digit of precisionin the answer requires 102=100 times more thenumber of iterations.

Other advantages of Monte Carlo.

Independence of dimension.

The amount of work to obtain the same amount of precisionis independent of the dimension dof the underlying random variables.

Thus Monte Carlo integration is practically the only methodto numerically compute high-dimensional integrals. Traditionalquadrature techniques generally require an amount of workexponential in the number of dimensions d,since they require sampling a grid in d-dimensional space.

On the other hand, Monte Carlo integration is generallynot competitive with quadrature for low-dimensional integration(e.g. d=1 or d=2).

Unrestricted choice of functions.

The functions to integrate with Monte Carlocan be practically arbitrary.No smoothness conditions or boundedness conditions are needed,for example, providing the integral is finite.

(However, irregularities in the integrandmay impact the accuracy of the result.)

Easily parallelizable.

Many computer processors can be participatingin a Monte Carlo simulation simultaneously.Each simulation is independent of another.

Other disadvantages of Monte Carlo.

Error may depend on distribution.

The estimateMathworldPlanetmath of the expectation 𝔼X may be impactedseverely if the distribution of X is heavily skewedor has heavier-than-normal tails.A non-random numerical methodmay avoid these deficiencies,or at least not be as severely impacted.

Difficulty in estimating error.

There are no hard bounds on the error of the computed result.The probabilistic error bound, which is essentially based on thevariance, may not be a good measureof the error for skewed distributions.

Black-box approach.

With some types of analytical approximation,one can study the behavior of the solutionif the initial parameters are changed.This generally is hard to do withthe black-box approach of Monte Carlo.

Variance reduction

There are some variance reduction techniquesthat can be used to reduce the error in the resultof a Monte Carlo simulation.However, they generally cannot overcome theslow 1/n decrease of the error inherent in Monte Carlo.

References

  • 1 James E. Gentle. Random Number Generation and Monte Carlo Methods,second edition. Springer, 2003.
  • 2 http://en.wikipedia.org/wiki/Monte_Carlo_methodMonte Carlo method”. Wikipedia, The Free Encyclopedia.Accessed 27 June 2007.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 12:11:30