"The book contains more than 300 references and has more than 50 coloured figures for better understanding. The book can be recommended to all readers, who are interested in this field, e.g. 'engineers working in signal theory or statisticians interested in computational methods or scientists working in the fields of biology, quantitative finance or physics, where complex models that demand Monte Carlo computations are needed'." (Ludwig Paditz, zbMATH 1414.62007, 2019)

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 . . . . . . . . . . . . . . . . . . . . . . . . 92

3.3.1 Acceptance Rate . . . . . . . . . . . . . . . . . . . . . 92

3.3.2 Squeezing . . . . . . . . . . . . . . . . . . . . . . . . . 95

3.3.3 Sibuya's modified rejection method . . . . . . . . . . . 96

3.4 Band rejection method . . . . . . . . . . . . . . . . . . . . . . 98

3.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 98

3.4.2 Generalized band rejection algorithm . . . . . . . . . . 100

3.4.3 Payne-Dagpunar's band rejection . . . . . . . . . . . . 104

3.5 Acceptance-complement method . . . . . . . . . . . . . . . . . 105

3.6 RS with stepwise proposals . . . . . . . . . . . . . . . . . . . . 109

3.6.1 Strip methods . . . . . . . . . . . . . . . . . . . . . . . 109

3.6.2 Inversion-rejection method . . . . . . . . . . . . . . . . 112

3.7 Transformed rejection method . . . . . . . . . . . . . . . . . . 114

3.7.1 Transformed rejection and IoD method . . . . . . . . . 118

3.8 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

3.8.1 RS for generating order statistics . . . . . . . . . . . . 120

3.8.2 Mixtures with negative coefficients . . . . . . . . . . . 121

3.8.3 Pdfs expressed as sequence of functions . . . . . . . . . 123

3.9 Monte Carlo estimation via RS . . . . . . . . . . . . . . . . . 125

3.9.1 Recycling rejected samples . . . . . . . . . . . . . . . . 126

3.9.2 RS with a generic constant L > 0 . . . . . . . . . . . . 127

3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

4 Adaptive rejection sampling methods 137

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

4.2 Generic structure of an adaptive rejection sampler . . . . . . . 139

4.2.1 Proposal densities . . . . . . . . . . . . . . . . . . . . . 139

4.2.2 Generic adaptive algorithm . . . . . . . . . . . . . . . 140

4.3 Constructions of the proposal densities . . . . . . . . . . . . . 142

4.3.1 Standard adaptive rejection sampling . . . . . . . . . . 142

4.3.2 Derivative-free constructions for log-concave pdfs . . . 149

4.3.3 Concave-convex ARS . . . . . . . . . . . . . . . . . . . 151

4.3.4 Transformed density rejection . . . . . . . . . . . . . . 154

4.3.5 Extensions of TDR . . . . . . . . . . . . . . . . . . . . 157

4.3.6 Generalized adaptive rejection sampling . . . . . . . . 162

4.4 Performance and computational cost of the ARS schemes . . . 175

4.4.1 Acceptance rate . . . . . . . . . . . . . . . . . . . . . . 175

4.4.2 Probability of adding a new support point . . . . . . . 176

4.5 Variants of the adaptive structure in the ARS scheme . . . . . 177

4.5.1 Deterministic test for adding new support points . . . 177

4.5.2 An adaptive rejection sampler with fixed number of

support points . . . . . . . . . . . . . . . . . . . . . . . 179

4.6 Combining ARS and MCMC . . . . . . . . . . . . . . . . . . . 182

4.6.1 Adaptive rejection Metropolis sampling . . . . . . . . . 182

4.6.2 ARMS algorithm . . . . . . . . . . . . . . . . . . . . . 182

4.6.3 A procedure to build proposal pdf's for the ARMS

algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 184

4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

5 Ratio of Uniforms 191

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

5.1.1 A remark on inverse densities . . . . . . . . . . . . . . 193

5.2 Standard ratio of uniforms method . . . . . . . . . . . . . . . 194

5.2.1 Some basic considerations . . . . . . . . . . . . . . . . 195

5.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 196

5.3 Envelope polygons and adaptive RoU . . . . . . . . . . . . . . 200

5.4 Generalized ratio of uniforms method . . . . . . . . . . . . . . 204

5.5 Properties of generalized RoU samplers . . . . . . . . . . . . . 206

5.5.1 Boundary of Ag . . . . . . . . . . . . . . . . . . . . . . 206

5.5.2 How to guarantee that Ag is bounded . . . . . . . . . 206

5.5.3 Power functions . . . . . . . . . . . . . . . . . . . . . . 209

5.6 Connections between GRoU and other classical techniques . . 211

5.6.1 Extended inverse-of-density method . . . . . . . . . . . 212

5.6.2 GRoU sampling and the transformed rejection method 216

5.6.3 Role of the constant cA . . . . . . . . . . . . . . . . . . 218

5.7 How does GRoU work for generic pdfs? . . . . . . . . . . . . . 219

5.7.1 IoD for arbitrary pdfs . . . . . . . . . . . . . . . . . . 220

5.7.2 GRoU for pdfs with a single mode at x = 0 . . . . . . 221

5.7.3 GRoU for pdfs with a single mode at x 6= 0 . . . . . . 222

5.7.4 GRoU for arbitrary pdfs . . . . . . . . . . . . . . . . . 224

5.7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 225

5.8 Rectangular region Ag . . . . . . . . . . . . . . . . . . . . . . 226

5.8.1 Yet another connection between IoD and GRoU . . . . 227

5.9 Relaxing assumptions: GRoU with decreasing g(u) . . . . . . 228

5.9.1 General expression of a r.v. transformation . . . . . . . 229

5.10 Another view of GRoU . . . . . . . . . . . . . . . . . . . . . . 230

5.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

6 Independent sampling for multivariate densities 237

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

6.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

6.3 Generic procedures . . . . . . . . . . . . . . . . . . . . . . . . 239

6.3.1 Chain rule decomposition . . . . . . . . . . . . . . . . 240

6.3.2 Dependence generation . . . . . . . . . . . . . . . . . . 241

6.3.3 Rejection sampling . . . . . . . . . . . . . . . . . . . . 244

6.3.4 RoU for multivariate densities . . . . . . . . . . . . . . 247

6.4 Elliptically contoured distributions . . . . . . . . . . . . . . . 248

6.4.1 Polar methods . . . . . . . . . . . . . . . . . . . . . . . 250

6.5 Vertical density representation . . . . . . . . . . . . . . . . . . 252

6.5.1 Inverse-of-density method . . . . . . . . . . . . . . . . 254

6.6 Uniform distributions in dimension n . . . . . . . . . . . . . . 254

6.6.1 Points uniformly distributed in a simplex . . . . . . . . 255

6.6.2 Sampling uniformly within a hypersphere . . . . . . . . 257

6.6.3 Points uniformly distributed within an hyperellipsoid . 258

6.7 Transformations of a random variable . . . . . . . . . . . . . . 259

6.7.1 Many-to-few transformations (m > n) . . . . . . . . . . 260

6.7.2 Few-to-many transformations: Singular distributions (m < n) . . . . . . . . . . . . . . . . . . . . . . . . . . 261

6.7.3 Sampling a uniform distribution on a differentiable manifold . . . . . . . . . . . . . . . . . . . . . . . . . . 264

6.8 Sampling techniques for specific distributions . . . . . . . . . 267

6.8.1 Multivariate Gaussian distribution . . . . . . . . . . . 268

6.8.2 Multivariate Student's t-Distribution . . . . . . . . . . 268

6.8.3 Wishart distribution . . . . . . . . . . . . . . . . . . . 269

6.8.4 Inverse Wishart distribution . . . . . . . . . . . . . . . 270

6.8.5 Multivariate Gamma samples . . . . . . . . . . . . . . 270

6.8.6 Dirichlet distribution . . . . . . . . . . . . . . . . . . . 271

6.8.7 Cook-Johnson's family . . . . . . . . . . . . . . . . . . 271

6.8.8 Some relevant bivariate distributions . . . . . . . . . . 273

6.9 Generation of stochastic processes . . . . . . . . . . . . . . . . 276

6.9.1 Markov jump processes . . . . . . . . . . . . . . . . . . 277

6.9.2 Gaussian processes . . . . . . . . . . . . . . . . . . . . 279

6.9.3 Wiener processes . . . . . . . . . . . . . . . . . . . . . 282

6.9.4 Brownian motion . . . . . . . . . . . . . . . . . . . . . 284

6.9.5 Poisson processes . . . . . . . . . . . . . . . . . . . . . 286

6.9.6 Dirichlet processes: “rich get richer" . . . . . . . . . . 290

6.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

7 Asymptotically independent samplers 297

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

7.2 Metropolis-Hastings (MH) methods . . . . . . . . . . . . . . . 299

7.2.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . 300

7.2.2 Invariant distribution of the MH algorithm . . . . . . . 301

7.2.3 Acceptance rate in MH-type methods . . . . . . . . . . 301

7.3 Independent generalized MH methods with multiple candidates 303

7.3.1 Independent multiple try Metropolis algorithms . . . . 303

7.3.2 Ensemble MCMC method . . . . . . . . . . . . . . . . 305

7.4 Independent Doubly Adaptive Rejection Metropolis Sampling 307

7.4.1 Adaptive rejection sampling (ARS) . . . . . . . . . . . 307

7.4.2 Adaptive rejection Metropolis sampling . . . . . . . . . 309

7.4.3 Structural limitations of ARMS . . . . . . . . . . . . . 311

7.4.4 IA2RMS algorithm . . . . . . . . . . . . . . . . . . . . 311

7.4.5 Convergence of the chain and computational cost . . . 313

7.4.6 Examples of proposal constructions for IA2RMS . . . . 314

7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

8 Summary and outlook 321

A Acronyms and abbreviations 327

B Notation 331

B.1 Vectors, points and intervals . . . . . . . . . . . . . . . . . . . 331

B.2 Random variables, distributions and densities . . . . . . . . . 331

B.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

B.4 Summary of Main Notation . . . . . . . . . . . . . . . . . . . 332

C Jones' RoU generalization 335

C.1 Possible choices of t(v; u) . . . . . . . . . . . . . . . . . . . . . 337

D Polar transformation 341

Luca Martino is currently a research fellow at the University of Valencia, Spain, after having held positions at the Carlos III University of Madrid, Spain, the University of Helsinki, Finland and the University of São Paulo, Brazil. His research interests are in the fields of statistical signal processing and computational statistics, especially in connection with Bayesian analysis and Monte Carlo approximation methods.

David Luengo is an Associate Professor at the Technical University of Madrid, Spain. His research interests are in the broad fields of statistical signal processing and machine learning, especially Bayesian learning and inference, Gaussian processes, Monte Carlo algorithms, sparse signal processing and Bayesian non-parametrics. Dr. Luengo has co-authored over 70 research papers, which were published in international journals and conference volumes.

Joaquín Míguez is an Associate Professor at the Carlos III University of Madrid, Spain. His interests are in the fields of applied probability, computational statistics, dynamical systems and the theory and applications of the Monte Carlo methods. Having published extensively and lectured internationally on his research, he was a co-recipient of the IEEE Signal Processing Magazine Best Paper Award in 2007.

This book systematically addresses the design and analysis of efficient techniques for independent random sampling. Both general-purpose approaches, which can be used to generate samples from arbitrary probability distributions, and tailored techniques, designed to efficiently address common real-world practical problems, are introduced and discussed in detail. In turn, the monograph presents fundamental results and methodologies in the field, elaborating and developing them into the latest techniques. The theory and methods are illustrated with a varied collection of examples, which are discussed in detail in the text and supplemented with ready-to-run computer code.

The main problem addressed in the book is how to generate independent random samples from an arbitrary probability distribution with the weakest possible constraints or assumptions in a form suitable for practical implementation. The authors review the fundamental results and methods in the field, address the latest methods, and emphasize the links and interplay between ostensibly diverse techniques.

Krainaksiazek.pl w programie rzetelna firma

Krainaksiaze.pl - płatności przez paypal

Czytaj nas na:

Zobacz:

1997-2025 DolnySlask.com Agencja Internetowa