ARVAG - Automatic nonuniform Random VAriate Generation

W. Hörmann, J. Leydold, and G. Derflinger
Automatic Nonuniform Random Variate Generation
Series: Statistics and Computing
2004, X, 442pp, Hardcover
ISBN: 3-540-40652-2
Springer, Berlin

About this book   |   Table of Contents   |   Introduction   |   Errata   |   Demo of Algorithms

Table of Contents

Part IPreliminaries1
2General Principles in Random Variate Generation13
2.1The Inversion Method13
2.2The Rejection Method16
2.2.1The Basic Principle16
2.2.2The Squeeze Principle20
2.2.3Performance Characteristics21
2.2.4Finding (Good) Hat Functions22
2.3.2Recycling Uniform Random Numbers28
2.3.3Immediate Acceptance29
2.4The Ratio-of-Uniforms Method (RoU)32
2.5Almost-Exact Inversion35
2.6Using Special Properties of the Distribution37
3General Principles for Discrete Distributions43
3.1.1Inversion by Sequential Search43
3.1.2Indexed Search (Guide Table Method)45
3.2The Alias Method47
3.3Discrete Rejection50
Part IIContinuous Univariate Distributions53
4Transformed Density Rejection (TDR)55
4.1The Main Idea 55
4.2The Class Tc of Transformations 59
4.3Tc-Concave Distributions 63
4.4Construction Points 69
4.4.1One Construction Point, Monotone Densities70
4.4.2Two and Three Points of Contact, Domain R74
4.4.3Asymptotically Optimal Constructions Points78
4.4.4Equiangular Points80
4.4.5Adaptive Rejection Sampling (ARS)81
4.4.6Derandomized Adaptive Rejection Sampling (DARS)84
4.5Algorithms and Variants of Transformed Density Rejection88
4.5.1Use Shifted Secants for Constructing Hat88
4.5.2Proportional Squeeze89
4.5.3Region of Immediate Acceptance91
4.5.4Three Design Points92
4.6Other Transformations95
4.7Generalizations of Transformed Density Rejection97
4.7.1T-Convex Distributions97
4.7.2Non-T-Concave Distributions99
4.7.3Varying Values of c100
4.7.4Generalized Transformed Density Rejection103
4.8Automatic Ratio-of-Uniforms Method103
4.8.1The Relation to Transformed Density Rejection104
4.8.2Enveloping Polygons105
4.8.3The Algorithm105
4.8.4Construction Points and Performance108
4.8.5Non-Convex Region108
5Strip Methods113
5.1Staircase-Shaped Hat Functions ("Ahrens Method")114
5.1.1The Algorithm114
5.1.2Equidistant Design Points116
5.1.3Optimal Design Points117
5.1.4(Derandomized) Adaptive Rejection Sampling118
5.1.5The Equal Area Approach119
5.1.6Comparison of the Different Variants121
5.2Horizontal Strips123
6Methods Based on General Inequalities125
6.1Monotone Densities126
6.1.1Monotone Densities with Bounded Domains126
6.1.2Monotone Densities with Unbounded Domain129
6.1.3Other Hat Functions for Monotone Densities133
6.2Lipschitz Densities134
6.3Generators for T-1/2-Concave Densities135
6.3.1Generators Based on the Ratio-of-Uniforms Method135
6.3.2The Mirror Principle138
6.3.3Universal Hats for T-1/2-Concave Densities139
6.4Generators for Tc-Concave Densities142
6.4.1Generalized Ratio-of-Uniforms Method142
6.4.2Log-Concave Distributions148
6.4.3Heavy-Tailed Tc-Concave Distributions149
7Numerical Inversion155
7.1Search Algorithms Without Tables156
7.2Fast Numerical Inversion158
7.2.1Approximation with Linear Interpolation159
7.2.2Iterated Linear Interpolation159
7.2.3Approximation with High-Order Polynomials160
7.2.4Approximation with Cubic Hermite Interpolation160
8Comparison and General Considerations165
8.1The UNU.RAN Library166
8.2Timing Results169
8.3Quality of Generated Samples173
8.3.1Streams of Non-Uniform Random Variates174
8.3.2Inversion Method and Transformed Density Rejection177
8.3.4Floating Point Arithmetic182
8.4Special Applications184
8.4.1Truncated Distributions184
8.4.2Correlation Induction185
8.4.3Order Statistics186
9Distributions Where the Density Is Not Known Explicitly193
9.1Known Hazard-Rate193
9.1.1Connection to the Poisson Process194
9.1.2The Inversion Method194
9.1.3The Composition Method195
9.1.4The Thinning Method196
9.1.5Algorithms for Decreasing Hazard Rate197
9.1.6Algorithms for Increasing Hazard Rate198
9.1.7Computational Experience199
9.2The Series Method201
9.2.1The Convergent Series Method201
9.2.2The Alternating Series Method203
9.3Known Fourier Coefficients204
9.3.1Computational Experience206
9.4Known Characteristic Function206
9.4.1Polya Characteristic Functions207
9.4.2Very Smooth Densities208
9.4.3Computational Experience210
Part IIIDiscrete Univariate Distributions213
10Discrete Distributions215
10.1Guide Table Method for Unbounded Domains216
10.1.1Indexed Search for Distributions with Right Tail216
10.1.2Indexed Search for Distributions with Two Tails218
10.2Transformed Probability Rejection (TPR)219
10.2.1The Principle of Rejection-Inversion221
10.2.2Rejection-Inversion and TPR223
10.3Short Algorithms Based on General Inequalities227
10.3.1Unimodal Probability Function with Known Second Moment227
10.3.2T-concave Distributions228
10.4Distributions Where the Probabilities Are Not Known Explicitly232
10.4.1Known Probability Generating Function232
10.4.2Known Moment Sequence233
10.4.3Known Discrete Hazard Rate235
10.5Computational Experience236
Part IV  Random Vectors243
11Multivariate Distributions245
11.1General Principles for Generating Random Vectors246
11.1.1The Conditional Distribution Method246
11.1.2The Multivariate Rejection Method248
11.1.3The Composition Method249
11.1.4The Ratio-of-Uniforms Method249
11.1.5Vertical Density Representation249
11.1.6The Multinormal Distribution250
11.1.7The Multivariate \textit {t-Distribution252
11.2Uniformly Distributed Random Vectors252
11.2.1The Unit Sphere253
11.2.2Simplices and Polytopes255
11.2.4Sweep-Plane Method for Simple Polytopes260
11.3Multivariate Transformed Density Rejection264
11.3.1Multivariate Tc-Concave Distributions265
11.3.2TDR with Polytope Regions266
11.3.3Bivariate Distributions271
11.3.4TDR with Cone Regions276
11.4Orthomonotone Densities280
11.4.1Notions of Unimodality280
11.4.2Generators Based on Global Inequalities281
11.4.3Table Methods284
11.4.4Generators Based on Inequalities Involving Conditional Densities286
11.5Computational Experience294
11.6Multivariate Discrete Distributions295
11.6.1The Conditional Distribution Method295
11.6.2Transformation into a Univariate Distribution297
11.6.3Rejection Method299
Part VImplicit Modeling303
12Combination of Generation and Modeling305
12.1Generalizing a Sample306
12.1.1Empirical Distributions306
12.1.2Sampling from Empirical Distributions Using Kernel Density Estimation307
12.1.3Linear Interpolation of the Empirical Distribution Function310
12.1.4Comparison of Methods311
12.1.5Computational Experience for Three Simple Simulation Examples315
12.2Generalizing a Vector-Sample319
12.2.1Sampling from Multidimensional Kernel Density Estimates319
12.2.2Computational Experience321
12.3Modeling of Distributions with Limited Information322
12.4Distribution with Known Moments323
12.4.1Matching the First Four Moments323
12.4.2Unimodal Densities and Scale Mixtures324
12.4.3The Moment Problem327
12.4.4Computational Experience328
12.5Generation of Random Vectors where only Correlation and
Marginal Distributions are Known
12.5.1The Bivariate Case330
12.5.2The Multidimensional Problem340
12.5.3Computational Experience343
13Time Series (Authors Michael Hauser and Wolfgang Hörmann)345
13.1Stationary Gaussian Time Series347
13.1.1The Conditional Distribution Method347
13.1.2Fourier Transform Method350
13.1.3Application of the Algorithms354
13.2Non-Gaussian Time Series356
13.2.1The Conditional Distribution Method357
13.2.2Memoryless Transformations358
14Markov Chain Monte Carlo Methods363
14.1Markov Chain Sampling Algorithms364
14.1.1Metropolis-Hastings Algorithm364
14.1.2Gibbs Sampling368
14.2Perfect Sampling for Markov Chain Monte Carlo372
14.2.1Coupling from the Past372
14.3Markov Chain Monte Carlo Methods for Random Vectors376
14.3.1Perfect Sampling Algorithms for the Rd377
14.3.2Approximate Algorithms383
15Some Simulation Examples387
15.1Financial Simulation387
15.1.1Option Pricing387
15.1.2Value at Risk394
15.2Bayesian Statistics400
15.2.1Gibbs Sampling and Universal Random Variate Generation401
15.2.2Vector Generation of the Posterior Distribution407
List of Algorithms411
Author index429
Selected Notation433
Subject Index and Glossary435

[ARVAG]     Wolfgang Hörmann and Josef Leydold   (October 21st, 2003) Research supported by FWF