Monte Carlo Methods

1 Monte Carlo MethodsDirk P. KroeseDepartment of MathematicsSchool of Mathematics and PhysicsThe University of These notes were used for an honours/graduate course on Monte Carlomethods at the 2011 Summer Schoolof theAustralian Mathematical SciencesInstitute(AMSI).No part of this publication may be reproduced or transmitted without theexplicit permission of the Kroese3 PrefaceMany numerical problems in science, engineering, finance, and statistics aresolved nowadays throughMonte Carlo Methods ; that is, through randomexperiments on a computer. The purpose of this AMSI Summer School courseis to provide a comprehensive introduction to Monte Carlo Methods , with amix of theory, algorithms (pseudo + actual), and notes present a highly condensed version Kroese, T. Taimre, of Monte Carlo Series in Probability and Statistics, John Wiley & Sons, New York, also the Handbook s the Handbook is over 772 pages thick, with 21 chapters, I had toheavily cut back the contents of the Handbook to a size that is manageable toteach within one semester.

2 I have tried to make these notes fairly self-contained,while retaining the general flavour of the Handbook. However, it was not alwayspossible to keep the logical connections between chapters in the Handbook. Foran advanced understanding of some material, including bibliographic references,it will be necessary to consult the corresponding passages in the , 2011 Dirk KroeseCopyrightc 2011 Kroese4 Copyrightc KroeseContents1 Uniform random Number random Numbers .. Properties of a Good random Number Generator .. Choosing a Good random Number Generator .. Generators Based on Linear Recurrences .. Linear Congruential Generators .. Multiple-Recursive Generators .. Matrix Congruential Generators .. Modulo 2 Linear Generators .. Combined Generators.

3 Tests for random Number Generators .. Equidistribution (or Frequency) Tests .. Serial Tests .. Gap Tests .. Poker or Partition Tests .. Coupon Collector s Tests .. Permutation Tests .. Run Tests .. Maximum-of-dTests .. Collision Tests .. Rank of Binary Matrix Tests .. Birthday Spacings Tests .. Exercises .. 242 random Variable Generic Algorithms Based on Common Transformations .. Inverse-Transform Method .. Other Transformation Methods .. Table Lookup Method .. Alias Method .. Acceptance Rejection Method .. Generation Methods for Multivariate random Variables .. Generating random Vectors Uniformly Distributed in a UnitHyperball and Hypersphere .. Generating random Permutations .. Exercises.

4 42 Copyrightc 2011 Kroese6 CONTENTS3 Probability Discrete Distributions .. Bernoulli Distribution .. Binomial Distribution .. Geometric Distribution .. Poisson Distribution .. Uniform Distribution (Discrete Case) .. Continuous Distributions .. Beta Distribution .. Cauchy Distribution .. Exponential Distribution .. Gamma Distribution .. Normal Distribution .. Uniform Distribution (Continuous Case) .. Multivariate Distributions .. Dirichlet Distribution .. Multivariate Normal Distribution .. Multivariate Student stDistribution .. Exercises .. 594 random Process Gaussian Processes .. Markovian Gaussian Processes .. Markov Chains .. Markov Jump Processes .. Poisson Processes .. Wiener Process and Brownian Motion.

5 Stochastic Differential Equations and Diffusion Processes .. Euler s Method .. Brownian Bridge .. Geometric Brownian Motion .. Ornstein Uhlenbeck Process .. Exercises .. 845 Markov Chain Monte Metropolis Hastings Algorithm .. Independence Sampler .. random Walk Sampler .. Gibbs Sampler .. Hit-and-Run Sampler .. Exercises .. 1006 Variance Variance Reduction Example .. Antithetic random Variables .. Control Variables .. Conditional Monte Carlo .. 110 Copyrightc 2011 Importance Sampling .. Minimum-Variance Density .. Variance Minimization Method .. Cross-Entropy Method .. Exercises .. 1197 Estimation of Gradient Estimation .. Finite Difference Method .. Infinitesimal Perturbation Analysis.

6 Score Function Method .. Score Function Method With Importance Sampling .. 1328 Randomized Stochastic Approximation .. Stochastic Counterpart Method .. Simulated Annealing .. Evolutionary Algorithms .. Genetic Algorithms .. Differential Evolution .. Exercises .. 1539 Cross-Entropy Cross-Entropy Method .. Cross-Entropy Method for Estimation .. Cross-Entropy Method for Optimization .. Combinatorial Optimization .. Continuous Optimization .. Constrained Optimization .. Noisy Optimization .. Exercises .. 169 Copyrightc 2011 Kroese8 CONTENTSC opyrightc KroeseChapter 1 Uniform random NumberGenerationAny one who considers arithmetical Methods of producing randomdigits is, of course, in a state of von NeumannThis chapter gives an introduction of techniques and algorithms for generat-ing uniform random numbers.

7 Various empirical tests for randomness are random NumbersAt the heart of any Monte Carlo method is arandom number generator: aprocedure that produces an infinite streamU1,U2,U3,..iid Distof random variables that are independent and identically distributed (iid) ac-cording to some probability distributionDist. When this distribution is theuniform distribution on the interval (0,1) (that is,Dist=U(0,1)), the gener-ator is said to be auniform random number generator. Most computerlanguages already contain a built-in uniform random number generator. Theuser is typically requested only to input an initial number, called theseed, andupon invocation the random number generator produces a sequence of indepen-dent uniform random variables on the interval (0,1). In MATLAB, for example,this is provided by concept of an infinite iid sequence of random variables is a mathemati-cal abstraction that may be impossible to implement on a computer.

8 The bestone can hope to achieve in practice is to produce a sequence of random num-bers with statistical properties that are indistinguishable from those of a truesequence of iid random variables. Although physical generation Methods basedon universal background radiation or quantum mechanics seem to offer a stablesource of such true randomness, the vast majority of current random numberCopyrightc 2011 Kroese10 Uniform random Number Generationgenerators are based on simple algorithms that can be easily implemented on acomputer. Such algorithms can usually be represented as a tuple (S,f, ,U,g),where Sis a finite set ofstates, fis a function fromStoS, is a probability distribution onS, Uis theoutput space; for a uniform random number generatorUisthe interval (0,1),and we will assume so from now on, unless otherwisespecified, gis a function random number generator then has the following structure:Algorithm (Generic random Number Generator) : Draw the seedS0from the distribution onS.

9 Sett= : SetSt=f(St 1). : SetUt=g(St). : Sett=t+ 1and return to Step algorithm produces a sequenceU1,U2,U3,..ofpseudorandom num-bers we will refer to them simply asrandom numbers. Starting from acertain seed, the sequence of states (and hence of random numbers) must re-peat itself, because the state space is finite. The smallest number of steps takenbefore entering a previously visited state is called theperiod lengthof therandom number Properties of a Good random Number GeneratorWhat constitutes a good random number generator depends on many factors. Itis always advisable to have a variety of random number generators available, asdifferent applications may require different properties of the random are some desirable, or indeed essential, properties of a good uniformrandom number statistical tests: The ultimate goal is that the generator should pro-duce a stream of uniform random numbers that is indistinguishable froma genuine uniform iid sequence.

10 Although from a theoretical point ofview this criterion is too imprecise and even infeasible, from a practi-cal point of view this means that the generator should pass a battery ofsimple statistical tests designed to detect deviations from uniformity andindependence. We discuss such tests in Section support: A good generator should be based on sound math-ematical principles, allowing for a rigorous analysis of essential proper-ties of the generator. Examples are linear congruential generators andmultiple-recursive generators discussed in Sections and 2011 random eproducible: An important property is that the stream of random num-bers is reproducible without having to store the complete stream in mem-ory. This is essential for testing and variance reduction techniques.