Monte Carlo Simulation And Numerical Integration
Monte Carlo Simulation and Numerical IntegrationJohn GewekeDepartment of Economics, University of Minnesotaand Federal Reserve Bank of Minneapolisgeweke@atlas.socsciumn.eduMarch 14, 1994Draft chapter prepared for Handbook of Computational Economics, edited by HansAmman, David Kendrick, and John Rust; to be published by North-Holland. This draftwas prepared explicitly for a conference in Minneapolis, March 18-19, 1994, and shouldnot be cited or distributed without the author's permission. Section 7 of this draft isincomplete. Suggestions and corrections will be gratefully received and acknowledged.This work was supported in part by National Science Foundation Grant SES-9210070.The views expressed in this paper are those of the author and not necessarily those of theFederal Reserve Bank of Minneapolis or the Federal Reserve System.
1. IntroductionOptimization problems in dynamic, stochastic environments are an increasinglyimportant part of economic theory and applied economics. Inspired by the potential returnsto richer and more realistic models of a variety of policy problems and the promise of evergrowing computational power, economists have turned more and more to models that can besimulated but not solved in closed form. The central role of simulation gives rise to twosubsequent related integration problems. One arises in model solution, for agents whoseexpected utilities cannot be expressed as a closed function of state and decision variables.The other occurs when the investigator combines sources of uncertainty about the model todraw conclusions about policy.This chapter concentrates on computational methods that are both important and usefulin the solution of these simulation and integration problems. In mathematics there is alongstanding use of simulation in the solution of integration problems, notably partialdifferential equations, where the form of the simulation is often suggested by the problemitself. The history of simulation methods to solve integration problems in economics isshorter, but these methods are appealing for the same reason there: integration generallyinvolves probability distributions in the integrand, which thereby suggests the simulationmethods to be employed.This pervasive use of simulation methods in science persists despite the well knownasymptotic advantages of deterministic approaches to integration. This continued use ofsimulation methods arises in part because astronomical computing time is often required torealize the promise of deterministic methods. A more important fact is that simulationmethods are generally straightforward for the investigator to implement, relying on anunderstanding of a few principles of simulation and the structure of the problem at hand.By contrast deterministic methods typically require much larger problem-specificinvestments in numerical methods. Simulation methods economize the use of that mostvaluable resource, the investigator's time.The objective of this chapter is to convey an understanding of principles for thepractical application of simulation in economics, with a specific focus on integrationproblems. It begins with a discussion of circumstances in which deterministic methods arepreferred to simulation, in Section 2. The next section takes up general procedures forsimulation from univariate and multivariate distributions, including acceptance and adaptivemethods. The construction and use of independent identically distributed random vectors tosolve the multidimensional integration problems that typically arise in economic models istaken up in Section 4, with special attention to combination of different approaches and1
assessment of the accuracy of numerical approximations to the integral. Section 5discusses some modifications of these methods to produce identically but not independentlydistributed random vectors, that often greatly reduce approximation error in applications ineconomics. Recently developed Markov chain Monte Carlo methods, which make use ofsamples that are neither independently nor identically distributed, have greatly expanded thescope of integration problems with convenient practical solutions. These procedures aretaken up in Section 6. The chapter concludes with some examples of recent applications ofsimulation and integration methods in economics.2
2. Deterministic methods of integrationThe evaluation of the integralI ff(x)cbcis a problem as old as the calculus itself, and is equivalent to solution of the differentialequationdyldx f(x)subject to the boundary condition y(a) 0. In well-catalogued instances analyticalsolutions are available (Gradshteyn and Ryzhik, 1965, is a useful standard reference). Theliterature on numerical approaches to each problem is huge, a review of any small part ofwhich would occupy a substantial part of this volume. This section focuses on thoseprocedures that provide the most useful tools in economics and econometrics and arereadily available in commercial software. This means neglecting the classical but datedapproaches using equally-spaced abscissas, like Newton-Cotes; a useful overview of thesemethods is provided by Press et al. (1987, Chapter 4) and a more extended discussion maybe found in Davis and Rabinowitz (1984, Chapter 2).2.1 Unidimensional quadratureThe principle underlying most state-of-the-art deterministic evaluations of I 5f(x)drais Gaussian quadrature. If f(x) p(x)w(x), where p(x) is any polynomial of degree2n –1 or lower, and w(x) is a chosen basis function, then there exist points x, E [a, b] anda weight a), associated with each point such thattf(x)dx p(x) w(x)dr exI I w, p(x, ).The points and weights depend only on a, b, and the function w(x), and if they are knownfor a 0 and b 1 then it is straightforward to determine their values for any other choicesof a and b. If r(x) f(x)/w(x) is not a polynomial of degree 2n –1 or lower, thenrai co, r(x,)may be taken as an approximation to I erf(x)thc. If r(x) is "smooth" relative to apolynomial of degree 2n –1, then the approximation should be good. More precisely, onemay show that if r(x) is 2n-times differentiable thenabf(x)dxjfor some 1(01r(x,) TC2n)(4)4 e [a,b], where {c} is a sequence of constants withc„ 0. For(nOlt(2n 1)12n !r} (Judd,example, if w(x) 1,a –1, b 1, then c„ z2114-16-7, 6-8).31991, pp.
This approach can be applied to any subinterval of [a,b] as well, and so long as r(x) is2n-times differentiable the accuracy of the approximation may be improved by summingover subintervals. In fact in this case, one may satisfy prespecified convergence or errorcriteria through successive bisection. Error criteria are usually specified as the absolute orrelative difference in the computed approximation to I f(x)dx using an n -point and anani -point quadrature (Golub and Welsch, 1969).Open and semi-open intervals can be treated by appropriate transformation of theinterval to a finite interval (Piessens et al., 1983). Existence and boundedness of r(2")depends in part on the choice of basis function w(x). Some of the most useful areindicated in the following table.w(x)Interval(-1,1)1N1 – x 2(-1,1)1(-1,1) 00)exp(–x2 )(1 x)a (1–x)3(-1,1)(0, 00)exp(–x)x“Vcosh(x)NameLegendreChebyshev first IdndChebyshev second kindHermiteJacobiGeneralized LaguerreHyperbolic cosineFor many purposes Gauss-Legendre rules are adequate, and there is a substantial stock ofcommercially supplied software to evaluate one-dimensional integrals up to specifiedtolerances. These methods have been adapted to include functions having singularities atidentified points in the interval of integration (Piessens, et al., 1983).2.2 Multidimensional quadratureSome multidimensional integration problems in fact reduce to an integration in a singlevariable that must be carried out numerically. For example, all but one dimension may beintegrable analytically, or the multidimensional integral may in fact be a product of integralseach in a single variable, perhaps after a suitable change of variable. In such casesquadrature for one-dimensional integrals usually provides a neat solution. Such cases arerare in economics and econometrics. If the dimension of the domain of integration is nottoo high and the integrand is sufficiently smooth, then one-dimensional methods may beextended with practical results. These cases cover a small subset of integration problems ineconomics and econometrics, but they deserve discussion because quadrature-basedmethods are then quite efficient and may be easy to use.4
The straightforward extension of quadrature methods to higher dimensions shows bothits strengths and weaknesses. Following Davis and Rabinowitz (1984, pp. 354-359),suppose that R is an m -point rule of integration over B g 91' , leading to the approximationR(f) cok f(x) ) if (x)dx, x1 e B,and that S is an n -point rule over G c W , leading to the approximationS(f ) Inkal f (yk )f (y)dy,yk e G.JcThe product rule of R and S i s the mn -point rule applicable to BxG,Rx S(f) f (x, y)dxdy, x jy E B,EG.13rk) JZft., 0, vk f(X)BxGIf R integrates f(x) exactly over B, if S integrates g(y) exactly over G, and ifh(x,y) f(x)g(y), then Rx S will integrate h(x,y) exactly over BxG. The obviousextensions to the product of three or more rules can be made. These extensions can beexpected to work well when (a) quadrature is adequate in the lower dimensional marginalsof the function at hand, (b) h(x,y) f (x)g(y), and (c) the product Inn is small enough thatcomputation time is reasonable. Condition (b) is violated when the support of h is smallrelative to the Cartesian boundaries for that support, as illustrated in Figure 1(a). A morecommon occurrence in economics and econometrics involves both (a) and (b): BxG x 9ts , but the function is concentrated on a small subset of its support that cannot beexpressed as a Cartesian product, as illustrated in Figure 1(b). Whether these difficultiesare present or not, the number of function evaluations and products required in any productrule increases geometrically with the number of arguments of the function, a phenomenonsometimes dubbed "the curse of dimensionality."These constitute the dominant problems for numerical integration in economics andeconometrics. To a point, one may extend quadrature to higher dimensions usingextensions more sophisticated than product rules. Extensions are usually specific tofunctions of a certain type, and for this reason the literature is large but reliable software fora problem at hand may be hard to come by. For example, there has been considerableattention to monomials (polynomials whose highest degree in any one product is bounded);e.g. McNamee and Stenger (1967), Genz and Malik (1983), Davis and Rabinowitz (1984,Section 5.7). Compound, or subregion, methods provide the most widely appliedextensions of quadrature to higher dimensions. In these procedures a finer and finersubdivision of the original integration region is dynamically constructed, with smallersubregions concentrated where the integrand is most irregular. Within each subregion alocal rule with a moderate number of points is used to provide an estimated for the integral.If, at a given step, a prespecified global convergence criterion is not satisfied, those regionsfor which the convergence criterion is farthest from being satisfied are subdivided, and the5
local rule is applied to the new subdivisions (van Dooren and de Ridder, 1976; Genz andMalik, 1980; Genz, 1991). For these procedures to work successfully it is important tohave a scheme for construction of subregions well suited to the problem at hand, asreconsideration of Figure 1(b) will make clear. For example Genz (1994) provides analgorithm that copes well with the isolated peaks in high-dimensional spaces often found inBayesian multiparameter problems.These extensions of quadrature are routinely successful for integrals throughdimension four or five. Beyond four or five, success depends on whether the problem athand is of a type for which existing subregion methods are well suited. Whereas theapplication of quadrature to a function of a single variable can be successful as a "blackbox" procedure, problems of dimensions three and four are more likely to requiretransformations or other analytical work before quadrature can be applied. There are veryfew applications of quadrature-based methods to integrals over more than five dimensionsin the literature. For these problems other deterministic methods may be used, but thestochastic methods developed beginning in Section 3 of this chapter are generally morepractical.2.3 Other deterministic methodsThere exist a number of methods for higher dimensional integrals that are in a practicalsense intermediate between quadrature and the Monte Carlo procedures taken up beginningin Section 3. Two examples are given here.The m -point quadrature rules are highly structured, but difficult to adapt efficiently tohigher dimensions. A less structured but still systematic approach was suggested byRichtmeyer (1952, 1958) in work made known in Hammersly and Handscomb (1964).Suppose it is desired to find I Lf(x)dx, where f: H 9V and H is the unit hypercubein 91k . Let a„ . ak be irrational roots of a polynomial of degree 3 . k 1. LetVail—Dad)where [ ] denotes fractional part. Suppose f (x) has Fourier expansionf (x) E E-k . a (1:1,.,nk)exp(2 wit IIf E-k . E ( max In j 18- )Ia(n .nIthenf (xl 0(N-1).IMore practically, if En- Igni,.nkl.B , thenf (x )15 (1 log MBIN6).
kThis approach applies to a wide range of functions defined over hyperrectangles in 91 andprovides an interesting supplement to quadrature-based methods. However, a finite range ofintegration in all dimensions is essential to the method. Transformation of the domain to ahypercube, in a way that preserves accuracy for reasonable values of N may be difficult orimpossible. These difficulties probably account for the dearth of application of thisapproach to date.In specialized settings integration in high dimensions can be made more tractable. Theobvious limiting case is the one in which the entire problem may be solved analytically. Butthere are also classes of problems that cannot be solved analytically, with common featuresthat suggest specific approximations. An example is provided by Tierney and Kadane(1986) for a class of problems arising in Bayesian statistics and econometrics:exp[n L(0)]d0g(0)exp[t(0)]1/(0)d0E„(g)j e exp[n (0)[d0fa exp[t(0)]x(0)d0where t(9) is a log-likelihood function; 140) is a prior density kernel; g(9) is a strictlypositive function of interest; n is the number of observations entering the log-likelihoodfunction; L(0) [log Ir(0) t(0)]1 n; and L (0). [log g(0) log z(0) .40)11 n .*2Let 9 denote the mode of L, and let E d L dad01fe exp[n L(0 d 0)j s exp[n 14e)–jLaPlace's approximation is42 2– 0) E(0 – O) d (2 tr) 1Ir exp[n L(t3)].Similarly, if b* is the mode of L and r d 2 L. I Od 019 ,42 exp[n L*(?)]The error of approximation in each case is 0(n -v2 ), but in the corresponding approximation(g) II /4/2 expf n[1: Cal- L(0)11exp[n C (0 d 0)].t, (2 x)II * Iinthe leading terms in the numerator and denominator cancel and the resulting error ofapproximation for E„ (g) is O(n ') (Tierney and Kadane, 1986).The approximate solution provided by this method is a substantial improvement onprevious approximations of this kind, which worked with a single expansion about B. Itexhibits two attractions shared by most specialized approximations to integration in higherdimensions. First, it avoids the need for specific adaptive subregion analysis required forquadrature, if indeed quadrature can be made to work at all. Second, once function-specificcode has been written the computations involve standard ascent algorithms to find B andb* and are usually extremely fast. This example also shares some limitations of thisapproach. First, there is no way to reduce approximation error, whereas in quadrature one7
can increase the number of points or subregions used and in Monte Carlo one can increasethe number of iterations. Second, there is no way to evaluate the error of approximation;again, quadrature and Monte Carlo will prove error estimates. Third, there is possibly timeintensive analytical work required for each problem in forming derivatives for different g aswell as different f . And finally, the requirement that g be strictly positive is restrictive. Themethod may be extended to more general functions at the cost of some increase incomplexity (Tierney, Kass and Kadane, 1989).8
3. Pseudorandom number generationThe analytical properties of virtually all Monte Carlo methods for numerical integration,and more generally for simulation, are rooted in the assumption that it is possible to observesequences of independent random variables, each distributed uniformly on the unit interval.Given this assumption various methods, described in Section 3.2, may be used to constructrandom variables and vectors with more complex distributions. Specific transformationsfrom the uniform random distribution to virtually all of the classical distributions ofmathematical statistics have been constructed using these methods. Some examples arereviewed in Sections 3.3 and 3.4. These distributions, in turn, constitute building blocks forthe solutions of integration and simulation problems described subsequently in this chapter.The assumption that it is possible to observe sequences of independent randomvariables, distributed uniformly or otherwise, constitutes a model or idealization of whatactually occurs. In this regard it plays the same role here with respect to what follows, asdoes the assumption of randomness in much of economic theory with respect to the derivedimplications for optimizing behavior, or does the assumption of randomness with respect tothe development of methods of statistical inference in econometrics. In current methods forpseudorandom number generation the observed sequences of numbers for which theassumption of an i.i.d. uniform distribution is the model, are in fact deterministic. Since thealgorithms that produce these observed sequences are known, the properties of thesequences may be studied analytically in a way that events in the real world correspondingto assumptions of randomness in economic models may not. Thus, the adequacy orinadequacy of stochastic independence as a model for these sequences is on a surer footingthan is this assumption as a model in economic or econometric theory. We begin thissection with an overview of current methods of generating sequences for which theindependent uniform assumption should be an adequate model.3.1 Uniform pseudorandom number generationVirtually all pseudorandom number generators employed in practice are linearcongruential generators and their elaborations. In the linear congruential generator asequence of integers PC,1 is determined by the recursionX, c)modm.(3.1)The parameters a, c, and m determine the qualities of the generator. If c 0 the resultinggenerator is a pure multiplicative congruential generator. For example, the multiplicativegenerator with m 23/ —1 2147483647 (a prime) and c 16807, c 397204094, orc 950706376 is used in the IMSL scientific library (IMSL, 1989), and the user may9
choose between different values of c, as well as set the seed X0 . The sequence IX,1 ismapped into the pseudorandom uniform sequence {U,} by the transformation(3.2)If in is prime the sequence will cycle after producing exactly m distinct values; clearly onecan do no better than m 23' –1 for a sequence of positive integers with 32-bit arithmetic.There are many criteria for evaluating the i.i.d. uniform distribution as a model for theresulting sequences iL7,1. Informal but useful discussions are provided by Press et al.(1986, pp. 192-194) and Bratley, Fox and Schrage (1987, pp. 216-220). More technicaland detailed evaluations, including discussion of t
investments in numerical methods. Simulation methods economize the use of that most valuable resource, the investigator's time. . The next section takes up general procedures for simulation from univariate and multivariate distributions, including acceptance and adaptive . literature on numerical approaches to each problem is huge, a review .
The Markov Chain Monte Carlo Revolution Persi Diaconis Abstract The use of simulation for high dimensional intractable computations has revolutionized applied math-ematics. Designing, improving and understanding the new tools leads to (and leans on) fascinating mathematics, from representation theory through micro-local analysis. 1 IntroductionCited by: 343Page Count: 24File Size: 775KBAuthor: Persi DiaconisExplore furtherA simple introduction to Markov Chain Monte–Carlo .link.springer.comHidden Markov Models - Tutorial And Examplewww.tutorialandexample.comA Gentle Introduction to Markov Chain Monte Carlo for .machinelearningmastery.comMarkov Chain Monte Carlo Lecture Noteswww.stat.umn.eduA Zero-Math Introduction to Markov Chain Monte Carlo .towardsdatascience.comRecommended to you b
Quasi Monte Carlo has been developed. While the convergence rate of classical Monte Carlo (MC) is O(n¡1 2), the convergence rate of Quasi Monte Carlo (QMC) can be made almost as high as O(n¡1). Correspondingly, the use of Quasi Monte Carlo is increasing, especially in the areas where it most readily can be employed. 1.1 Classical Monte Carlo
Fourier Analysis of Correlated Monte Carlo Importance Sampling Gurprit Singh Kartic Subr David Coeurjolly Victor Ostromoukhov Wojciech Jarosz. 2 Monte Carlo Integration!3 Monte Carlo Integration f( x) I Z 1 0 f( x)d x!4 Monte Carlo Estimator f( x) I N 1 N XN k 1 f( x k) p( x
Introduction to Markov Chain Monte Carlo Monte Carlo: sample from a distribution - to estimate the distribution - to compute max, mean Markov Chain Monte Carlo: sampling using "local" information - Generic "problem solving technique" - decision/optimization/value problems - generic, but not necessarily very efficient Based on - Neal Madras: Lectures on Monte Carlo Methods .
vi Equity Valuation 5.3 Reconciling operating income to FCFF 66 5.4 The financial value driver approach 71 5.5 Fundamental enterprise value and market value 76 5.6 Baidu’s share price performance 2005–2007 79 6 Monte Carlo FCFF Models 85 6.1 Monte Carlo simulation: the idea 85 6.2 Monte Carlo simulation with @Risk 88 6.2.1 Monte Carlo simulation with one stochastic variable 88
de Monte Carlo. Nous faisons une etude comparative des principales m ethodes qui evaluent les options am ericaines avec la simulation de Monte Carlo. Notre etude se base sur l'algorithme de Del Moral et al. (2006) qui utilise l'interpolation lin eaire et la simulation de Monte Carlo pour evaluer le prix des options am ericaines.
Monte Carlo simulation is rapidly gaining currency as the preferred method of generating probability distributions of risk. . II. . is collected together and used for analysing the project completion probabilities by using Monte Carlo simulation in Ms Excel. draft a schedule date from Collect all this Data of each acti Monte C IV.File Size: 6MBPage Count: 11
Computational Geometry Aspects of Monte Carlo Approaches to PDE Problems in Biology, Chemistry, and Materials Monte Carlo Methods for PDEs A Little History on Monte Carlo Methods for PDEs Early History of MCMs for PDEs 1.Courant, Friedrichs, and Lewy: Their pivotal 1928 paper has probabilistic interpretations and MC algorithms for linear elliptic
