Independent Random Sampling Methods

1 Introduction 1 1.1 The Monte Carlo method: a brief history . . . . . . . . . . . . 2 1.2 The need for Monte Carlo . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Numerical integration . . . . . . . . . . . . . . . . . . . 5 1.2.2 Importance sampling . . . . . . . . . . . . . . . . . . . 7 1.2.3 Quasi Monte Carlo . . . . . . . . . . . . . . . . . . . . 9 1.2.4 Inverse Monte Carlo . . . . . . . . . . . . . . . . . . . 9 1.3 Random number generation . . . . . . . . . . . . . . . . . . . 10 1.3.1 Random, pseudo-random, quasi-random . . . . . . . . 11 1.4 Pseudo-random number generators . . . . . . . . . . . . . . . 13 1.4.1 Nonlinear recursions . . . . . . . . . . . . . . . . . . . 13 1.4.2 Chaotic pseudo-random number generators . . . . . . . 15 1.4.3 The middle-square generator . . . . . . . . . . . . . . . 17 1.4.4 Linear congruential generators . . . . . . . . . . . . . . 17 1.5 Random sampling methods . . . . . . . . . . . . . . . . . . . . 19 1.5.1 Direct methods . . . . . . . . . . . . . . . . . . . . . . 19 1.5.2 Accept/reject methods . . . . . . . . . . . . . . . . . . 20 1.5.3 Markov Chain Monte Carlo (MCMC) . . . . . . . . . . 21 1.5.4 Importance Sampling . . . . . . . . . . . . . . . . . . . 21 1.5.5 Hybrid techniques . . . . . . . . . . . . . . . . . . . . . 22 1.6 Goal and organization of this book . . . . . . . . . . . . . . . 22 1.6.1 Motivation and Goals . . . . . . . . . . . . . . . . . . . 22 1.6.2 Organization of the Book . . . . . . . . . . . . . . . . . 23 References 25 2 Direct methods 37 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.1 Vectors, points and intervals . . . . . . . . . . . . . . . 39 2.2.2 Random variables, distributions and densities . . . . . 39 2.2.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3 Transformations of random variables . . . . . . . . . . . . . . 40 2.3.1 One-to-one transformations . . . . . . . . . . . . . . . 40 2.3.2 Many-to-one transformations . . . . . . . . . . . . . . 44 2.3.3 Deconvolution method . . . . . . . . . . . . . . . . . . 48 2.3.4 Discrete mixtures . . . . . . . . . . . . . . . . . . . . . 49 2.3.5 Continuous mixtures: marginalization . . . . . . . . . . 50 2.3.6 Order statistics . . . . . . . . . . . . . . . . . . . . . . 51 2.4 Universal direct methods . . . . . . . . . . . . . . . . . . . . . 53 2.4.1 Inversion method . . . . . . . . . . . . . . . . . . . . . 53 2.4.2 Vertical density representation (VDR) . . . . . . . . . 57 2.4.3 The fundamental theorem of simulation . . . . . . . . . 62 2.4.4 Inverse-of-density method . . . . . . . . . . . . . . . . 63 2.5 Tailored techniques . . . . . . . . . . . . . . . . . . . . . . . . 67 2.5.1 Recursive methods . . . . . . . . . . . . . . . . . . . . 67 2.5.2 Convex Densities . . . . . . . . . . . . . . . . . . . . . 69 2.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.6.1 Multiplication of independent uniform random variates 70 2.6.2 Sum of independent uniform random variates . . . . . 73 2.6.3 Polynomial densities with non-negative coefficients . . 73 2.6.4 Polynomial densities with one or more negative constants 74 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3 Accept-Reject methods 81 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2 Rejection sampling . . . . . . . . . . . . . . . . . . . . . . . . 83 3.2.1 Distribution of the rejected samples . . . . . . . . . . . 86 3.2.2 Distribution of the accepted and rejected samples with generic L 0 . . . . . . . . . . . . . . . . . . . . . . . 87 3.2.3 Different application scenarios . . . . . . . . . . . . . . 87 3.2.4 Butcher's version of the rejection sampler . . . . . . . . 88 3.2.5 Vaduva's modification of the Butcher's method . . . . 89 3.2.6 Lux's extension . . . . . . . . . . . . . . . . . . . . . . 90 3.3 Computational cost . . . . . . . . . . . .