Example: tourism industry

Monte Carlo Methods and Importance Sampling

Lecture Notes for Stat 578Cc Eric C. AndersonStatistical Genetics20 October 1999(subbin' Thompson) Monte Carlo Methods and Importance SamplingHistory and de nition:The term \ Monte Carlo " was apparently rst used by Ulam and vonNeumann as a Los Alamos code word for the stochastic simulations they applied to building betteratomic bombs. Their Methods , involving the laws of chance, were aptly named after the inter-national gaming destination; the moniker stuck and soon after the War a wide range of stickyproblems yielded to the new techniques.

t) takes the value 1 when X t = 0 and 0 otherwise. Denoting the ith simulated value of X tby x (i) our Monte Carlo estimate would be Pe(X t=0jX 0 = x 0) … 1 n Xn i=1 If0g(x (i)): Example II: Monte Carlo approximations to distributions. A simple extension of the above example is to approximate the whole probability distribution P(X tjX 0 = x 0 ...

Tags:

  Value, Importance, Sampling, Importance sampling

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Monte Carlo Methods and Importance Sampling

1 Lecture Notes for Stat 578Cc Eric C. AndersonStatistical Genetics20 October 1999(subbin' Thompson) Monte Carlo Methods and Importance SamplingHistory and de nition:The term \ Monte Carlo " was apparently rst used by Ulam and vonNeumann as a Los Alamos code word for the stochastic simulations they applied to building betteratomic bombs. Their Methods , involving the laws of chance, were aptly named after the inter-national gaming destination; the moniker stuck and soon after the War a wide range of stickyproblems yielded to the new techniques.

2 Despite the widespread use of the Methods , and numerousdescriptions of them in articles and monographs, it is virtually impossible to nd a succint de ni-tion of \ Monte Carlo method" in the literature. Perhaps this is owing to the intuitive nature of thetopic which spawns many de nitions by way of speci c examples. Some authors prefer to use theterm \stochastic simulation" for almost everything, reserving \ Monte Carlo " only for Monte CarloIntegration and Monte Carlo Tests ( ). Others seem less concerned about blurringthe distinction between simulation studies and Monte Carlo that as it may, a suitable de nition can be good to have, if for nothing other than to avoid theawkwardness of trying to de ne the Monte Carlo method by appealing to a whole bevy of examplesof it.

3 Since I am (so Elizabeth claims!) unduly in uenced by my advisor's ways of thinking, I liketo de ne Monte Carlo in the spirit of de nitions she has used before. In particular, I use:Definition: Monte Carlo is the art of approximating an expectation by the samplemean of a function of simulated random will nd that this de nition is broad enough to cover everything that has been called MonteCarlo, and yet makes clear its essence in very familiar terms: Monte Carlo is about invoking lawsof large numbers to approximate most Monte Carlo simulations are done by computer today, there were many applicationsof Monte Carlo Methods using coin- ipping, card-drawing, or needle-tossing (rather than computer-generated pseudo-random numbers) as early as the turn of the century|long before the name MonteCarlo more mathematical terms:Consider a (possibly multidimensional) random variableXhaving probability mass function or probability density functionfX(x) which is greater than zeroon a set of valuesX.

4 Then the expected value of a functiongofXisE(g(X)) =Xx2Xg(x)fX(x)(1)ifXis discrete, andE(g(X)) =Zx2Xg(x)fX(x)dx(2)ifXis continuous. Now, if we were to take ann-sample ofX's, (x1;:::;xn), and we computed themean ofg(x) over the sample, then we would have the Monte Carloestimateegn(x)=1nnXi=1g(xi)1 This applies when the simulated variables are independent of one another, and might apply when they arecorrelated with one another (for example if they are states visited by an ergodic Markov chain). For now we willjust deal with independent simulated random variables, but all of this extends to samples from Markov chains viathe weak law of large numbers for the number of passages through a recurrent state in an ergodic Markov chain (seeFeller1957).

5 You will encounter this later when talking about Eric C. Anderson. You may duplicate this freely for pedagogical (g(X)). We could, alternatively, speak of the random variableegn(X)=1nnXi=1g(X)which we call the Monte CarloestimatorofE(g(X)).IfE(g(X)), exists, then the weak law of large numbers tells us that for any arbitrarily small limn!1P(jegn(X) E(g(X))j )=0:This tells us that asngets large, then there is small probability thategn(X) deviates much fromE(g(X)). For our purposes, the strong law of large numbers says much the same thing|theimportant part being that so long asnis large enough,egn(x) arising from a Monte Carlo experimentshall be close toE(g(X)), as other thing to note at this point is thategn(X) is unbiased forE(g(X)):E(egn(X)) =E 1nnXi=1g(Xi)!

6 =1nnXi=1E(g(Xi)) =E(g(X)):Making this useful:The preceding section comes to life and becomes useful when one realizesthat very many quantities of interest may be cast as expectations. Most importantly for applica-tions in statistical genetics, it is possible to express all probabilities, integrals, and summations asexpectations:Probabilities:LetYbe a random variable. The probability thatYtakes on some value in a setAcan be expressed as an expectation using the indicator function:P(Y2A)=E(IfAg(Y))(3)whereIfAg(Y ) is the indicator function that takes the value 1 whenY2 Aand 0 :Consider a problem now which is completely deterministic|integrating a functionq(x)fromatob(as in high-school calculus).

7 So we haveRbaq(x)dx. This can be expressed as anexpectation with respect to a uniformly distributed, continuous random density functionfU(u)=1=(b a), so if we rewrite the integral we get(b a)Zbaq(x)1b adx=(b a)Zbaq(x)fU(x)dx=(b a)E(q(U)):::voila!Discrete Sums:The discrete version of the above is just the sum of a functionq(x) over the count-ably many values ofxin a setA. If we have a random variableWwhich takes values inAallwith equal probabilityp(so thatPw2Ap= 1 then the sum may be cast as the expectationXx2Aq(x)=1pXx2Aq(x)p=1pE(q(W) ):The immediate consequence of this is that all probabilities, integrals, and summations can beapproximated by the Monte Carlo method.)

8 A crucial thing to note, however, is that there is norestriction that saysUorWabove must have uniform distributions. This is just for easy illustrationof the points above. We will explore this point more while considering Importance Eric C. Anderson. Corrections, I: Approximating probabilities by Monte a Wright-Fisherpopulation of sizeNdiploid individuals in whichXtcounts the numbers of copies of a certainallelic type in the population at timet. At time zero, there arex0copies of the allele. Giventhis, what is the probability that the allele will be lost from the population intgenerations, ,P(Xt=0jX0=x0)?

9 This can be computed exactly by multiplying transition probabilitymatrices together, or by employing theBaum(1972) algorithm (which you will learn aboutlater), but it can also be approximated by Monte Carlo . It is simple to simulate genetic drift ina Wright-Fisher population; thus we can easily simulate values forXtgivenX0=x0. Then,P(Xt=0jX0=x0)=E(If0g(Xt)jX0=x0)wher eIf0g(Xt) takes the value 1 whenXt= 0 and 0 otherwise. Denoting theithsimulatedvalue ofXtbyx(i)tour Monte Carlo estimate would beeP(Xt=0jX0=x0) 1nnXi=1If0g(x(i)t):Example II: Monte Carlo approximations to simple extension of theabove example is to approximate the whole probability distributionP(XtjX0=x0) by MonteCarlo.

10 Consider the histogram Carlo Estimate of ProbabilityNumber of Copies of AlleleIt represents the results of simulations in whichn=50;000,x0= 60,t= 14, the Wright-Fisherpopulation sizeN= 100 diploids, and each rectangle represents a Monte Carlo approximation toP(a X14<a+2jX0= 60),a=0;2;4;:::;200. For each such probability, the approximationfollows fromP(a X14<a+2jX0= 60) =E(Ifa X<a+2g(X14)) 1nnXi=1 Ifa X<a+2g(x(i)14);a=0;2;:::;200 Example III: A discrete sum over latent many applications in statisticalgenetics, the probabilityP(Y) of an observed eventYmust be computed as the sum over verymany latent variablesXof the joint probabilityP(Y;X).


Related search queries