An Introduction To Monte Carlo Methods Of Numerical Analysis

Abstract

his paper will trace the history and development of a useful stochastic method for approximating certain analytically intractable integrals, the Monte Carlo method. It will begin with simple explanations and examples of the method and proceed to develop the tools and techniques necessary to allow its application. It also offers the reader a number of numerical examples which serve to illustrate the method and looks into subtle modifications like variance reduction and stratified sampling that help to improve the estimation. An integral part of the Monte Carlo method is the sequence of the random numbers used in the calculation. Random numbers and their generation are examined in detail since various uses of the numbers and the type of generator used to produce these numbers largely determines the success of the Monte Carlo calculation. To provide balance, an account is given of one attractive deterministic alternative to Monte Carlo, the method of uniformly distributed sequences modulo one. This method has the advantage of dispensing with the apparatus of quasi-random number generators required by Monte Carlo. Moreover, it offers error bounds that behave like c/n, where c is a constant and n is the sample size. This is important since Monte Carlo's error bounds are only guaranteed to be on the order of c'A/n, where c' is a constant. To drive home the point that neither stochastic nor deterministic approximation methods should be used when analytic methods are available, there is included a discussion of an interesting integral of an iterated logarithm. This integral is evaluated using techniques borrowed from analytic number theory, in particular from a collection of ideas first developed in the study of Dirichlet series. The reader is invited to try a <br /> corresponding approximate evaluation using Monte Carlo, equidistributed sequences, or the usual quadrature methods of numerical analysis. The thesis closes with some suggestions for further work, with examples of problems that can be studied.