Independent Random Sampling Methods

1 Introduction 11.1 The Monte Carlo method: a brief history . . . . . . . . . . . . 21.2 The need for Monte Carlo . . . . . . . . . . . . . . . . . . . . 41.2.1 Numerical integration . . . . . . . . . . . . . . . . . . . 51.2.2 Importance sampling . . . . . . . . . . . . . . . . . . . 71.2.3 Quasi Monte Carlo . . . . . . . . . . . . . . . . . . . . 91.2.4 Inverse Monte Carlo . . . . . . . . . . . . . . . . . . . 91.3 Random number generation . . . . . . . . . . . . . . . . . . . 101.3.1 Random, pseudo-random, quasi-random . . . . . . . . 111.4 Pseudo-random number generators . . . . . . . . . . . . . . . 131.4.1 Nonlinear recursions . . . . . . . . . . . . . . . . . . . 131.4.2 Chaotic pseudo-random number generators . . . . . . . 151.4.3 The middle-square generator . . . . . . . . . . . . . . . 171.4.4 Linear congruential generators . . . . . . . . . . . . . . 171.5 Random sampling methods . . . . . . . . . . . . . . . . . . . . 191.5.1 Direct methods . . . . . . . . . . . . . . . . . . . . . . 191.5.2 Accept/reject methods . . . . . . . . . . . . . . . . . . 201.5.3 Markov Chain Monte Carlo (MCMC) . . . . . . . . . . 211.5.4 Importance Sampling . . . . . . . . . . . . . . . . . . . 211.5.5 Hybrid techniques . . . . . . . . . . . . . . . . . . . . . 221.6 Goal and organization of this book . . . . . . . . . . . . . . . 221.6.1 Motivation and Goals . . . . . . . . . . . . . . . . . . . 221.6.2 Organization of the Book . . . . . . . . . . . . . . . . . 23References 252 Direct methods 372.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.2.1 Vectors, points and intervals . . . . . . . . . . . . . . . 392.2.2 Random variables, distributions and densities . . . . . 392.2.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.3 Transformations of random variables . . . . . . . . . . . . . . 402.3.1 One-to-one transformations . . . . . . . . . . . . . . . 402.3.2 Many-to-one transformations . . . . . . . . . . . . . . 442.3.3 Deconvolution method . . . . . . . . . . . . . . . . . . 482.3.4 Discrete mixtures . . . . . . . . . . . . . . . . . . . . . 492.3.5 Continuous mixtures: marginalization . . . . . . . . . . 502.3.6 Order statistics . . . . . . . . . . . . . . . . . . . . . . 512.4 Universal direct methods . . . . . . . . . . . . . . . . . . . . . 532.4.1 Inversion method . . . . . . . . . . . . . . . . . . . . . 532.4.2 Vertical density representation (VDR) . . . . . . . . . 572.4.3 The fundamental theorem of simulation . . . . . . . . . 622.4.4 Inverse-of-density method . . . . . . . . . . . . . . . . 632.5 Tailored techniques . . . . . . . . . . . . . . . . . . . . . . . . 672.5.1 Recursive methods . . . . . . . . . . . . . . . . . . . . 672.5.2 Convex Densities . . . . . . . . . . . . . . . . . . . . . 692.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.6.1 Multiplication of independent uniform random variates 702.6.2 Sum of independent uniform random variates . . . . . 732.6.3 Polynomial densities with non-negative coefficients . . 732.6.4 Polynomial densities with one or more negative constants 742.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753 Accept-Reject methods 813.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.2 Rejection sampling . . . . . . . . . . . . . . . . . . . . . . . . 833.2.1 Distribution of the rejected samples . . . . . . . . . . . 863.2.2 Distribution of the accepted and rejected samples with generic L > 0 . . . . . . . . . . . . . . . . . . . . . . . 873.2.3 Different application scenarios . . . . . . . . . . . . . . 873.2.4 Butcher's version of the rejection sampler . . . . . . . . 883.2.5 Vaduva's modification of the Butcher's method . . . . 893.2.6 Lux's extension . . . . . . . . . . . . . . . . . . . . . . 903.3 Computational cost . . . . . . . . . . . . . . . . . . . . . . . . 923.3.1 Acceptance Rate . . . . . . . . . . . . . . . . . . . . . 923.3.2 Squeezing . . . . . . . . . . . . . . . . . . . . . . . . . 953.3.3 Sibuya's modified rejection method . . . . . . . . . . . 963.4 Band rejection method . . . . . . . . . . . . . . . . . . . . . . 983.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 983.4.2 Generalized band rejection algorithm . . . . . . . . . . 1003.4.3 Payne-Dagpunar's band rejection . . . . . . . . . . . . 1043.5 Acceptance-complement method . . . . . . . . . . . . . . . . . 1053.6 RS with stepwise proposals . . . . . . . . . . . . . . . . . . . . 1093.6.1 Strip methods . . . . . . . . . . . . . . . . . . . . . . . 1093.6.2 Inversion-rejection method . . . . . . . . . . . . . . . . 1123.7 Transformed rejection method . . . . . . . . . . . . . . . . . . 1143.7.1 Transformed rejection and IoD method . . . . . . . . . 1183.8 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203.8.1 RS for generating order statistics . . . . . . . . . . . . 1203.8.2 Mixtures with negative coefficients . . . . . . . . . . . 1213.8.3 Pdfs expressed as sequence of functions . . . . . . . . . 1233.9 Monte Carlo estimation via RS . . . . . . . . . . . . . . . . . 1253.9.1 Recycling rejected samples . . . . . . . . . . . . . . . . 1263.9.2 RS with a generic constant L > 0 . . . . . . . . . . . . 1273.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1324 Adaptive rejection sampling methods 1374.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1384.2 Generic structure of an adaptive rejection sampler . . . . . . . 1394.2.1 Proposal densities . . . . . . . . . . . . . . . . . . . . . 1394.2.2 Generic adaptive algorithm . . . . . . . . . . . . . . . 1404.3 Constructions of the proposal densities . . . . . . . . . . . . . 1424.3.1 Standard adaptive rejection sampling . . . . . . . . . . 1424.3.2 Derivative-free constructions for log-concave pdfs . . . 1494.3.3 Concave-convex ARS . . . . . . . . . . . . . . . . . . . 1514.3.4 Transformed density rejection . . . . . . . . . . . . . . 1544.3.5 Extensions of TDR . . . . . . . . . . . . . . . . . . . . 1574.3.6 Generalized adaptive rejection sampling . . . . . . . . 1624.4 Performance and computational cost of the ARS schemes . . . 1754.4.1 Acceptance rate . . . . . . . . . . . . . . . . . . . . . . 1754.4.2 Probability of adding a new support point . . . . . . . 1764.5 Variants of the adaptive structure in the ARS scheme . . . . . 1774.5.1 Deterministic test for adding new support points . . . 1774.5.2 An adaptive rejection sampler with fixed number ofsupport points . . . . . . . . . . . . . . . . . . . . . . . 1794.6 Combining ARS and MCMC . . . . . . . . . . . . . . . . . . . 1824.6.1 Adaptive rejection Metropolis sampling . . . . . . . . . 1824.6.2 ARMS algorithm . . . . . . . . . . . . . . . . . . . . . 1824.6.3 A procedure to build proposal pdf's for the ARMSalgorithm . . . . . . . . . . . . . . . . . . . . . . . . . 1844.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1855 Ratio of Uniforms 1915.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1915.1.1 A remark on inverse densities . . . . . . . . . . . . . . 1935.2 Standard ratio of uniforms method . . . . . . . . . . . . . . . 1945.2.1 Some basic considerations . . . . . . . . . . . . . . . . 1955.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 1965.3 Envelope polygons and adaptive RoU . . . . . . . . . . . . . . 2005.4 Generalized ratio of uniforms method . . . . . . . . . . . . . . 2045.5 Properties of generalized RoU samplers . . . . . . . . . . . . . 2065.5.1 Boundary of Ag . . . . . . . . . . . . . . . . . . . . . . 2065.5.2 How to guarantee that Ag is bounded . . . . . . . . . 2065.5.3 Power functions . . . . . . . . . . . . . . . . . . . . . . 2095.6 Connections between GRoU and other classical techniques . . 2115.6.1 Extended inverse-of-density method . . . . . . . . . . . 2125.6.2 GRoU sampling and the transformed rejection method 2165.6.3 Role of the constant cA . . . . . . . . . . . . . . . . . . 2185.7 How does GRoU work for generic pdfs? . . . . . . . . . . . . . 2195.7.1 IoD for arbitrary pdfs . . . . . . . . . . . . . . . . . . 2205.7.2 GRoU for pdfs with a single mode at x = 0 . . . . . . 2215.7.3 GRoU for pdfs with a single mode at x 6= 0 . . . . . . 2225.7.4 GRoU for arbitrary pdfs . . . . . . . . . . . . . . . . . 2245.7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 2255.8 Rectangular region Ag . . . . . . . . . . . . . . . . . . . . . . 2265.8.1 Yet another connection between IoD and GRoU . . . . 2275.9 Relaxing assumptions: GRoU with decreasing g(u) . . . . . . 2285.9.1 General expression of a r.v. transformation . . . . . . . 2295.10 Another view of GRoU . . . . . . . . . . . . . . . . . . . . . . 2305.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2316 Independent sampling for multivariate densities 2376.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2376.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2396.3 Generic procedures . . . . . . . . . . . . . . . . . . . . . . . . 2396.3.1 Chain rule decomposition . . . . . . . . . . . . . . . . 2406.3.2 Dependence generation . . . . . . . . . . . . . . . . . . 2416.3.3 Rejection sampling . . . . . . . . . . . . . . . . . . . . 2446.3.4 RoU for multivariate densities . . . . . . . . . . . . . . 2476.4 Elliptically contoured distributions . . . . . . . . . . . . . . . 2486.4.1 Polar methods . . . . . . . . . . . . . . . . . . . . . . . 2506.5 Vertical density representation . . . . . . . . . . . . . . . . . . 2526.5.1 Inverse-of-density method . . . . . . . . . . . . . . . . 2546.6 Uniform distributions in dimension n . . . . . . . . . . . . . . 2546.6.1 Points uniformly distributed in a simplex . . . . . . . . 2556.6.2 Sampling uniformly within a hypersphere . . . . . . . . 2576.6.3 Points uniformly distributed within an hyperellipsoid . 2586.7 Transformations of a random variable . . . . . . . . . . . . . . 2596.7.1 Many-to-few transformations (m > n) . . . . . . . . . . 2606.7.2 Few-to-many transformations: Singular distributions (m < n) . . . . . . . . . . . . . . . . . . . . . . . . . . 2616.7.3 Sampling a uniform distribution on a differentiable manifold . . . . . . . . . . . . . . . . . . . . . . . . . . 2646.8 Sampling techniques for specific distributions . . . . . . . . . 2676.8.1 Multivariate Gaussian distribution . . . . . . . . . . . 2686.8.2 Multivariate Student's t-Distribution . . . . . . . . . . 2686.8.3 Wishart distribution . . . . . . . . . . . . . . . . . . . 2696.8.4 Inverse Wishart distribution . . . . . . . . . . . . . . . 2706.8.5 Multivariate Gamma samples . . . . . . . . . . . . . . 2706.8.6 Dirichlet distribution . . . . . . . . . . . . . . . . . . . 2716.8.7 Cook-Johnson's family . . . . . . . . . . . . . . . . . . 2716.8.8 Some relevant bivariate distributions . . . . . . . . . . 2736.9 Generation of stochastic processes . . . . . . . . . . . . . . . . 2766.9.1 Markov jump processes . . . . . . . . . . . . . . . . . . 2776.9.2 Gaussian processes . . . . . . . . . . . . . . . . . . . . 2796.9.3 Wiener processes . . . . . . . . . . . . . . . . . . . . . 2826.9.4 Brownian motion . . . . . . . . . . . . . . . . . . . . . 2846.9.5 Poisson processes . . . . . . . . . . . . . . . . . . . . . 2866.9.6 Dirichlet processes: "rich get richer" . . . . . . . . . . 2906.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2927 Asymptotically independent samplers 2977.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2977.2 Metropolis-Hastings (MH) methods . . . . . . . . . . . . . . . 2997.2.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . 3007.2.2 Invariant distribution of the MH algorithm . . . . . . . 3017.2.3 Acceptance rate in MH-type methods . . . . . . . . . . 3017.3 Independent generalized MH methods with multiple candidates 3037.3.1 Independent multiple try Metropolis algorithms . . . . 3037.3.2 Ensemble MCMC method . . . . . . . . . . . . . . . . 3057.4 Independent Doubly Adaptive Rejection Metropolis Sampling 3077.4.1 Adaptive rejection sampling (ARS) . . . . . . . . . . . 3077.4.2 Adaptive rejection Metropolis sampling . . . . . . . . . 3097.4.3 Structural limitations of ARMS . . . . . . . . . . . . . 3117.4.4 IA2RMS algorithm . . . . . . . . . . . . . . . . . . . . 3117.4.5 Convergence of the chain and computational cost . . . 3137.4.6 Examples of proposal constructions for IA2RMS . . . . 3147.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3168 Summary and outlook 321A Acronyms and abbreviations 327B Notation 331B.1 Vectors, points and intervals . . . . . . . . . . . . . . . . . . . 331B.2 Random variables, distributions and densities . . . . . . . . . 331B.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332B.4 Summary of Main Notation . . . . . . . . . . . . . . . . . . . 332C Jones' RoU generalization 335C.1 Possible choices of t(v; u) . . . . . . . . . . . . . . . . . . . . . 337D Polar transformation 341