Independent Random Sampling Methods (eBook)
XII, 280 Seiten
Springer International Publishing (Verlag)
978-3-319-72634-2 (ISBN)
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.
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.
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.
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 6.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
| Erscheint lt. Verlag | 31.3.2018 |
|---|---|
| Reihe/Serie | Statistics and Computing | Statistics and Computing |
| Zusatzinfo | XII, 280 p. 55 illus., 52 illus. in color. |
| Verlagsort | Cham |
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Statistik |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Schlagworte | Accept-reject methods • Adaptive rejection sampling • Independent sampling • Markov Chain Monte Carlo • Multidimensional random sampling • Quantitative Finance • Random Sampling • Ratio of uniforms • Ratio-of-uniforms • Rejection samplers |
| ISBN-10 | 3-319-72634-X / 331972634X |
| ISBN-13 | 978-3-319-72634-2 / 9783319726342 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
