Independent Random Sampling Methods

<div><div>1 Introduction 1</div><div>1.1 The Monte Carlo method: a brief history . . . . . . . . . . . . 2</div><div>1.2 The need for Monte Carlo . . . . . . . . . . . . . . . . . . . . 4</div><div>1.2.1 Numerical integration . . . . . . . . . . . . . . . . . . . 5</div><div>1.2.2 Importance sampling . . . . . . . . . . . . . . . . . . . 7</div><div>1.2.3 Quasi Monte Carlo . . . . . . . . . . . . . . . . . . . . 9</div><div>1.2.4 Inverse Monte Carlo . . . . . . . . . . . . . . . . . . . 9</div><div>1.3 Random number generation . . . . . . . . . . . . . . . . . . . 10</div><div>1.3.1 Random, pseudo-random, quasi-random . . . . . . . . 11</div><div>1.4 Pseudo-random number generators . . . . . . . . . . . . . . . 13</div><div>1.4.1 Nonlinear recursions . . . . . . . . . . . . . . . . . . . 13</div><div>1.4.2 Chaotic pseudo-random number generators . . . . . . . 15</div><div>1.4.3 The middle-square generator . . . . . . . . . . . . . . . 17</div><div>1.4.4 Linear congruential generators . . . . . . . . . . . . . . 17</div><div>1.5 Random sampling methods . . . . . . . . . . . . . . . . . . . . 19</div><div>1.5.1 Direct methods . . . . . . . . . . . . . . . . . . . . . . 19</div><div>1.5.2 Accept/reject methods . . . . . . . . . . . . . . . . . . 20</div><div>1.5.3 Markov Chain Monte Carlo (MCMC) . . . . . . . . . . 21</div><div>1.5.4 Importance Sampling . . . . . . . . . . . . . . . . . . . 21</div><div>1.5.5 Hybrid techniques . . . . . . . . . . . . . . . . . . . . . 22</div><div>1.6 Goal and organization of this book . . . . . . . . . . . . . . . 22</div><div>1.6.1 Motivation and Goals . . . . . . . . . . . . . . . . . . . 22</div><div>1.6.2 Organization of the Book . . . . . . . . . . . . . . . . . 23</div><div>References 25</div><div>2 Direct methods 37</div><div>2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37</div><div>2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39</div><div>2.2.1 Vectors, points and intervals . . . . . . . . . . . . . . . 39</div><div>2.2.2 Random variables, distributions and densities . . . . . 39</div><div>2.2.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40</div><div>2.3 Transformations of random variables . . . . . . . . . . . . . . 40</div><div>2.3.1 One-to-one transformations . . . . . . . . . . . . . . . 40</div><div>2.3.2 Many-to-one transformations . . . . . . . . . . . . . . 44</div><div>2.3.3 Deconvolution method . . . . . . . . . . . . . . . . . . 48</div><div>2.3.4 Discrete mixtures . . . . . . . . . . . . . . . . . . . . . 49</div><div>2.3.5 Continuous mixtures: marginalization . . . . . . . . . . 50</div><div>2.3.6 Order statistics . . . . . . . . . . . . . . . . . . . . . . 51</div><div>2.4 Universal direct methods . . . . . . . . . . . . . . . . . . . . . 53</div><div>2.4.1 Inversion method . . . . . . . . . . . . . . . . . . . . . 53</div><div>2.4.2 Vertical density representation (VDR) . . . . . . . . . 57</div><div>2.4.3 The fundamental theorem of simulation . . . . . . . . . 62</div><div>2.4.4 Inverse-of-density method . . . . . . . . . . . . . . . . 63</div><div>2.5 Tailored techniques . . . . . . . . . . . . . . . . . . . . . . . . 67</div><div>2.5.1 Recursive methods . . . . . . . . . . . . . . . . . . . . 67</div><div>2.5.2 Convex Densities . . . . . . . . . . . . . . . . . . . . . 69</div><div>2.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70</div><div>2.6.1 Multiplication of independent uniform random variates 70</div><div>2.6.2 Sum of independent uniform random variates . . . . . 73</div><div>2.6.3 Polynomial densities with non-negative coefficients . . 73</div><div>2.6.4 Polynomial densities with one or more negative constants 74</div><div>2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75</div><div>3 Accept-Reject methods 81</div><div>3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81</div><div>3.2 Rejection sampling . . . . . . . . . . . . . . . . . . . . . . . . 83</div><div>3.2.1 Distribution of the rejected samples . . . . . . . . . . . 86</div><div>3.2.2 Distribution of the accepted and rejected samples with generic L &gt; 0 . . . . . . . . . . . . . . . . . . . . . . . 87</div><div>3.2.3 Different application scenarios . . . . . . . . . . . . . . 87</div><div>3.2.4 Butcher's version of the rejection sampler . . . . . . . . 88</div><div>3.2.5 Vaduva's modification of the Butcher's method . . . . 89</div><div>3.2.6 Lux's extension . . . . . . . . . . . . . . . . . . . . . . 90</div><div>3.3 Computational cost . . . . . . . . . . . . . . . . . . . . . . . . 92</div><div>3.3.1 Acceptance Rate . . . . . . . . . . . . . . . . . . . . . 92</div><div>3.3.2 Squeezing . . . . . . . . . . . . . . . . . . . . . . . . . 95</div><div>3.3.3 Sibuya's modified rejection method . . . . . . . . . . . 96</div><div>3.4 Band rejection method . . . . . . . . . . . . . . . . . . . . . . 98</div><div>3.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 98</div><div>3.4.2 Generalized band rejection algorithm . . . . . . . . . . 100</div><div>3.4.3 Payne-Dagpunar's band rejection . . . . . . . . . . . . 104</div><div>3.5 Acceptance-complement method . . . . . . . . . . . . . . . . . 105</div><div>3.6 RS with stepwise proposals . . . . . . . . . . . . . . . . . . . . 109</div><div>3.6.1 Strip methods . . . . . . . . . . . . . . . . . . . . . . . 109</div><div>3.6.2 Inversion-rejection method . . . . . . . . . . . . . . . . 112</div><div>3.7 Transformed rejection method . . . . . . . . . . . . . . . . . . 114</div><div>3.7.1 Transformed rejection and IoD method . . . . . . . . . 118</div><div>3.8 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120</div><div>3.8.1 RS for generating order statistics . . . . . . . . . . . . 120</div><div>3.8.2 Mixtures with negative coefficients . . . . . . . . . . . 121</div><div>3.8.3 Pdfs expressed as sequence of functions . . . . . . . . . 123</div><div>3.9 Monte Carlo estimation via RS . . . . . . . . . . . . . . . . . 125</div><div>3.9.1 Recycling rejected samples . . . . . . . . . . . . . . . . 126</div><div>3.9.2 RS with a generic constant L &gt; 0 . . . . . . . . . . . . 127</div><div>3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132</div><div>4 Adaptive rejection sampling methods 137</div><div>4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138</div><div>4.2 Generic structure of an adaptive rejection sampler . . . . . . . 139</div><div>4.2.1 Proposal densities . . . . . . . . . . . . . . . . . . . . . 139</div><div>4.2.2 Generic adaptive algorithm . . . . . . . . . . . . . . . 140</div><div>4.3 Constructions of the proposal densities . . . . . . . . . . . . . 142</div><div>4.3.1 Standard adaptive rejection sampling . . . . . . . . . . 142</div><div>4.3.2 Derivative-free constructions for log-concave pdfs . . . 149</div><div>4.3.3 Concave-convex ARS . . . . . . . . . . . . . . . . . . . 151</div><div>4.3.4 Transformed density rejection . . . . . . . . . . . . . . 154</div><div>4.3.5 Extensions of TDR . . . . . . . . . . . . . . . . . . . . 157</div><div>4.3.6 Generalized adaptive rejection sampling . . . . . . . . 162</div><div>4.4 Performance and computational cost of the ARS schemes . . . 175</div><div>4.4.1 Acceptance rate . . . . . . . . . . . . . . . . . . . . . . 175</div><div>4.4.2 Probability of adding a new support point . . . . . . . 176</div><div>4.5 Variants of the adaptive structure in the ARS scheme . . . . . 177</div><div>4.5.1 Deterministic test for adding new support points . . . 177</div><div>4.5.2 An adaptive rejection sampler with fixed number of</div><div>support points . . . . . . . . . . . . . . . . . . . . . . . 179</div><div>4.6 Combining ARS and MCMC . . . . . . . . . . . . . . . . . . . 182</div><div>4.6.1 Adaptive rejection Metropolis sampling . . . . . . . . . 182</div><div>4.6.2 ARMS algorithm . . . . . . . . . . . . . . . . . . . . . 182</div><div>4.6.3 A procedure to build proposal pdf's for the ARMS</div><div>algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 184</div><div>4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185</div><div>5 Ratio of Uniforms 191</div><div>5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191</div><div>5.1.1 A remark on inverse densities . . . . . . . . . . . . . . 193</div><div>5.2 Standard ratio of uniforms method . . . . . . . . . . . . . . . 194</div><div>5.2.1 Some basic considerations . . . . . . . . . . . . . . . . 195</div><div>5.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 196</div><div>5.3 Envelope polygons and adaptive RoU . . . . . . . . . . . . . . 200</div><div>5.4 Generalized ratio of uniforms method . . . . . . . . . . . . . . 204</div><div>5.5 Properties of generalized RoU samplers . . . . . . . . . . . . . 206</div><div>5.5.1 Boundary of Ag . . . . . . . . . . . . . . . . . . . . . . 206</div><div>5.5.2 How to guarantee that Ag is bounded . . . . . . . . . 206</div><div>5.5.3 Power functions . . . . . . . . . . . . . . . . . . . . . . 209</div><div>5.6 Connections between GRoU and other classical techniques . . 211</div><div>5.6.1 Extended inverse-of-density method . . . . . . . . . . . 212</div><div>5.6.2 GRoU sampling and the transformed rejection method 216</div><div>5.6.3 Role of the constant cA . . . . . . . . . . . . . . . . . . 218</div><div>5.7 How does GRoU work for generic pdfs? . . . . . . . . . . . . . 219</div><div>5.7.1 IoD for arbitrary pdfs . . . . . . . . . . . . . . . . . . 220</div><div>5.7.2 GRoU for pdfs with a single mode at x = 0 . . . . . . 221</div><div>5.7.3 GRoU for pdfs with a single mode at x 6= 0 . . . . . . 222</div><div>5.7.4 GRoU for arbitrary pdfs . . . . . . . . . . . . . . . . . 224</div><div>5.7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 225</div><div>5.8 Rectangular region Ag . . . . . . . . . . . . . . . . . . . . . . 226</div><div>5.8.1 Yet another connection between IoD and GRoU . . . . 227</div><div>5.9 Relaxing assumptions: GRoU with decreasing g(u) . . . . . . 228</div><div>5.9.1 General expression of a r.v. transformation . . . . . . . 229</div><div>5.10 Another view of GRoU . . . . . . . . . . . . . . . . . . . . . . 230</div><div>5.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231</div><div>6 Independent sampling for multivariate densities 237</div><div>6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237</div><div>6.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239</div><div>6.3 Generic procedures . . . . . . . . . . . . . . . . . . . . . . . . 239</div><div>6.3.1 Chain rule decomposition . . . . . . . . . . . . . . . . 240</div><div>6.3.2 Dependence generation . . . . . . . . . . . . . . . . . . 241</div><div>6.3.3 Rejection sampling . . . . . . . . . . . . . . . . . . . . 244</div><div>6.3.4 RoU for multivariate densities . . . . . . . . . . . . . . 247</div><div>6.4 Elliptically contoured distributions . . . . . . . . . . . . . . . 248</div><div>6.4.1 Polar methods . . . . . . . . . . . . . . . . . . . . . . . 250</div><div>6.5 Vertical density representation . . . . . . . . . . . . . . . . . . 252</div><div>6.5.1 Inverse-of-density method . . . . . . . . . . . . . . . . 254</div><div>6.6 Uniform distributions in dimension n . . . . . . . . . . . . . . 254</div><div>6.6.1 Points uniformly distributed in a simplex . . . . . . . . 255</div><div>6.6.2 Sampling uniformly within a hypersphere . . . . . . . . 257</div><div>6.6.3 Points uniformly distributed within an hyperellipsoid . 258</div><div>6.7 Transformations of a random variable . . . . . . . . . . . . . . 259</div><div>6.7.1 Many-to-few transformations (m &gt; n) . . . . . . . . . . 260</div><div>6.7.2 Few-to-many transformations: Singular distributions (m &lt; n) . . . . . . . . . . . . . . . . . . . . . . . . . . 261</div><div>6.7.3 Sampling a uniform distribution on a differentiable manifold . . . . . . . . . . . . . . . . . . . . . . . . . . 264</div><div>6.8 Sampling techniques for specific distributions . . . . . . . . . 267</div><div>6.8.1 Multivariate Gaussian distribution . . . . . . . . . . . 268</div><div>6.8.2 Multivariate Student's t-Distribution . . . . . . . . . . 268</div><div>6.8.3 Wishart distribution . . . . . . . . . . . . . . . . . . . 269</div><div>6.8.4 Inverse Wishart distribution . . . . . . . . . . . . . . . 270</div><div>6.8.5 Multivariate Gamma samples . . . . . . . . . . . . . . 270</div><div>6.8.6 Dirichlet distribution . . . . . . . . . . . . . . . . . . . 271</div><div>6.8.7 Cook-Johnson's family . . . . . . . . . . . . . . . . . . 271</div><div>6.8.8 Some relevant bivariate distributions . . . . . . . . . . 273</div><div>6.9 Generation of stochastic processes . . . . . . . . . . . . . . . . 276</div><div>6.9.1 Markov jump processes . . . . . . . . . . . . . . . . . . 277</div><div>6.9.2 Gaussian processes . . . . . . . . . . . . . . . . . . . . 279</div><div>6.9.3 Wiener processes . . . . . . . . . . . . . . . . . . . . . 282</div><div>6.9.4 Brownian motion . . . . . . . . . . . . . . . . . . . . . 284</div><div>6.9.5 Poisson processes . . . . . . . . . . . . . . . . . . . . . 286</div><div>6.9.6 Dirichlet processes: “rich get richer" . . . . . . . . . . 290</div><div>6.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292</div><div>7 Asymptotically independent samplers 297</div><div>7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297</div><div>7.2 Metropolis-Hastings (MH) methods . . . . . . . . . . . . . . . 299</div><div>7.2.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . 300</div><div>7.2.2 Invariant distribution of the MH algorithm . . . . . . . 301</div><div>7.2.3 Acceptance rate in MH-type methods . . . . . . . . . . 301</div><div>7.3 Independent generalized MH methods with multiple candidates 303</div><div>7.3.1 Independent multiple try Metropolis algorithms . . . . 303</div><div>7.3.2 Ensemble MCMC method . . . . . . . . . . . . . . . . 305</div><div>7.4 Independent Doubly Adaptive Rejection Metropolis Sampling 307</div><div>7.4.1 Adaptive rejection sampling (ARS) . . . . . . . . . . . 307</div><div>7.4.2 Adaptive rejection Metropolis sampling . . . . . . . . . 309</div><div>7.4.3 Structural limitations of ARMS . . . . . . . . . . . . . 311</div><div>7.4.4 IA2RMS algorithm . . . . . . . . . . . . . . . . . . . . 311</div><div>7.4.5 Convergence of the chain and computational cost . . . 313</div><div>7.4.6 Examples of proposal constructions for IA2RMS . . . . 314</div><div>7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316</div><div>8 Summary and outlook 321</div><div>A Acronyms and abbreviations 327</div><div>B Notation 331</div><div>B.1 Vectors, points and intervals . . . . . . . . . . . . . . . . . . . 331</div><div>B.2 Random variables, distributions and densities . . . . . . . . . 331</div><div>B.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332</div><div>B.4 Summary of Main Notation . . . . . . . . . . . . . . . . . . . 332</div><div>C Jones' RoU generalization 335</div><div>C.1 Possible choices of t(v; u) . . . . . . . . . . . . . . . . . . . . . 337</div><div>D Polar transformation 341</div></div>