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 I	Preliminaries			1
1	Introduction			3
2	General Principles in Random Variate Generation			13
2.1		The Inversion Method		13
2.2		The Rejection Method		16
2.2.1			The Basic Principle	16
2.2.2			The Squeeze Principle	20
2.2.3			Performance Characteristics	21
2.2.4			Finding (Good) Hat Functions	22
2.3		Composition		26
2.3.1			Composition-Rejection	27
2.3.2			Recycling Uniform Random Numbers	28
2.3.3			Immediate Acceptance	29
2.4		The Ratio-of-Uniforms Method (RoU)		32
2.5		Almost-Exact Inversion		35
2.6		Using Special Properties of the Distribution		37
2.7		Exercises		39
3	General Principles for Discrete Distributions			43
3.1		Inversion		43
3.1.1			Inversion by Sequential Search	43
3.1.2			Indexed Search (Guide Table Method)	45
3.2		The Alias Method		47
3.3		Discrete Rejection		50
3.4		Exercises		52
Part II	Continuous Univariate Distributions			53
4	Transformed Density Rejection (TDR)			55
4.1		The Main Idea		55
4.2		The Class Tc of Transformations		59
4.3		Tc-Concave Distributions		63
4.4		Construction Points		69
4.4.1			One Construction Point, Monotone Densities	70
4.4.2			Two and Three Points of Contact, Domain R	74
4.4.3			Asymptotically Optimal Constructions Points	78
4.4.4			Equiangular Points	80
4.4.5			Adaptive Rejection Sampling (ARS)	81
4.4.6			Derandomized Adaptive Rejection Sampling (DARS)	84
4.4.7			Convergence	85
4.4.8			Summary	86
4.5		Algorithms and Variants of Transformed Density Rejection		88
4.5.1			Use Shifted Secants for Constructing Hat	88
4.5.2			Proportional Squeeze	89
4.5.3			Region of Immediate Acceptance	91
4.5.4			Three Design Points	92
4.6		Other Transformations		95
4.7		Generalizations of Transformed Density Rejection		97
4.7.1			T-Convex Distributions	97
4.7.2			Non-T-Concave Distributions	99
4.7.3			Varying Values of c	100
4.7.4			Generalized Transformed Density Rejection	103
4.8		Automatic Ratio-of-Uniforms Method		103
4.8.1			The Relation to Transformed Density Rejection	104
4.8.2			Enveloping Polygons	105
4.8.3			The Algorithm	105
4.8.4			Construction Points and Performance	108
4.8.5			Non-Convex Region	108
4.9		Exercises		109
5	Strip Methods			113
5.1		Staircase-Shaped Hat Functions ("Ahrens Method")		114
5.1.1			The Algorithm	114
5.1.2			Equidistant Design Points	116
5.1.3			Optimal Design Points	117
5.1.4			(Derandomized) Adaptive Rejection Sampling	118
5.1.5			The Equal Area Approach	119
5.1.6			Comparison of the Different Variants	121
5.2		Horizontal Strips		123
5.3		Exercises		124
6	Methods Based on General Inequalities			125
6.1		Monotone Densities		126
6.1.1			Monotone Densities with Bounded Domains	126
6.1.2			Monotone Densities with Unbounded Domain	129
6.1.3			Other Hat Functions for Monotone Densities	133
6.2		Lipschitz Densities		134
6.3		Generators for T-1/2-Concave Densities		135
6.3.1			Generators Based on the Ratio-of-Uniforms Method	135
6.3.2			The Mirror Principle	138
6.3.3			Universal Hats for T-1/2-Concave Densities	139
6.4		Generators for Tc-Concave Densities		142
6.4.1			Generalized Ratio-of-Uniforms Method	142
6.4.2			Log-Concave Distributions	148
6.4.3			Heavy-Tailed Tc-Concave Distributions	149
6.5		Exercises		152
7	Numerical Inversion			155
7.1		Search Algorithms Without Tables		156
7.2		Fast Numerical Inversion		158
7.2.1			Approximation with Linear Interpolation	159
7.2.2			Iterated Linear Interpolation	159
7.2.3			Approximation with High-Order Polynomials	160
7.2.4			Approximation with Cubic Hermite Interpolation	160
7.3		Exercises		164
8	Comparison and General Considerations			165
8.1		The UNU.RAN Library		166
8.2		Timing Results		169
8.3		Quality of Generated Samples		173
8.3.1			Streams of Non-Uniform Random Variates	174
8.3.2			Inversion Method and Transformed Density Rejection	177
8.3.3			Discrepancy	180
8.3.4			Floating Point Arithmetic	182
8.4		Special Applications		184
8.4.1			Truncated Distributions	184
8.4.2			Correlation Induction	185
8.4.3			Order Statistics	186
8.5		Summary		188
9	Distributions Where the Density Is Not Known Explicitly			193
9.1		Known Hazard-Rate		193
9.1.1			Connection to the Poisson Process	194
9.1.2			The Inversion Method	194
9.1.3			The Composition Method	195
9.1.4			The Thinning Method	196
9.1.5			Algorithms for Decreasing Hazard Rate	197
9.1.6			Algorithms for Increasing Hazard Rate	198
9.1.7			Computational Experience	199
9.2		The Series Method		201
9.2.1			The Convergent Series Method	201
9.2.2			The Alternating Series Method	203
9.3		Known Fourier Coefficients		204
9.3.1			Computational Experience	206
9.4		Known Characteristic Function		206
9.4.1			Polya Characteristic Functions	207
9.4.2			Very Smooth Densities	208
9.4.3			Computational Experience	210
9.5		Exercises		210
Part III	Discrete Univariate Distributions			213
10	Discrete Distributions			215
10.1		Guide Table Method for Unbounded Domains		216
10.1.1			Indexed Search for Distributions with Right Tail	216
10.1.2			Indexed Search for Distributions with Two Tails	218
10.2		Transformed Probability Rejection (TPR)		219
10.2.1			The Principle of Rejection-Inversion	221
10.2.2			Rejection-Inversion and TPR	223
10.3		Short Algorithms Based on General Inequalities		227
10.3.1			Unimodal Probability Function with Known Second Moment	227
10.3.2			T-concave Distributions	228
10.4		Distributions Where the Probabilities Are Not Known Explicitly		232
10.4.1			Known Probability Generating Function	232
10.4.2			Known Moment Sequence	233
10.4.3			Known Discrete Hazard Rate	235
10.5		Computational Experience		236
10.6		Summary		239
10.7		Exercises		241
Part IV	Random Vectors			243
11	Multivariate Distributions			245
11.1		General Principles for Generating Random Vectors		246
11.1.1			The Conditional Distribution Method	246
11.1.2			The Multivariate Rejection Method	248
11.1.3			The Composition Method	249
11.1.4			The Ratio-of-Uniforms Method	249
11.1.5			Vertical Density Representation	249
11.1.6			The Multinormal Distribution	250
11.1.7			The Multivariate \textit {t-Distribution	252
11.2		Uniformly Distributed Random Vectors		252
11.2.1			The Unit Sphere	253
11.2.2			Simplices and Polytopes	255
11.2.3			Polytopes	258
11.2.4			Sweep-Plane Method for Simple Polytopes	260
11.3		Multivariate Transformed Density Rejection		264
11.3.1			Multivariate Tc-Concave Distributions	265
11.3.2			TDR with Polytope Regions	266
11.3.3			Bivariate Distributions	271
11.3.4			TDR with Cone Regions	276
11.4		Orthomonotone Densities		280
11.4.1			Notions of Unimodality	280
11.4.2			Generators Based on Global Inequalities	281
11.4.3			Table Methods	284
11.4.4			Generators Based on Inequalities Involving Conditional Densities	286
11.5		Computational Experience		294
11.6		Multivariate Discrete Distributions		295
11.6.1			The Conditional Distribution Method	295
11.6.2			Transformation into a Univariate Distribution	297
11.6.3			Rejection Method	299
11.7		Exercises		300
Part V	Implicit Modeling			303
12	Combination of Generation and Modeling			305
12.1		Generalizing a Sample		306
12.1.1			Empirical Distributions	306
12.1.2			Sampling from Empirical Distributions Using Kernel Density Estimation	307
12.1.3			Linear Interpolation of the Empirical Distribution Function	310
12.1.4			Comparison of Methods	311
12.1.5			Computational Experience for Three Simple Simulation Examples	315
12.2		Generalizing a Vector-Sample		319
12.2.1			Sampling from Multidimensional Kernel Density Estimates	319
12.2.2			Computational Experience	321
12.3		Modeling of Distributions with Limited Information		322
12.4		Distribution with Known Moments		323
12.4.1			Matching the First Four Moments	323
12.4.2			Unimodal Densities and Scale Mixtures	324
12.4.3			The Moment Problem	327
12.4.4			Computational Experience	328
12.5		Generation of Random Vectors where only Correlation and Marginal Distributions are Known		328
12.5.1			The Bivariate Case	330
12.5.2			The Multidimensional Problem	340
12.5.3			Computational Experience	343
12.6		Exercises		343
13	Time Series (Authors Michael Hauser and Wolfgang Hörmann)			345
13.1		Stationary Gaussian Time Series		347
13.1.1			The Conditional Distribution Method	347
13.1.2			Fourier Transform Method	350
13.1.3			Application of the Algorithms	354
13.2		Non-Gaussian Time Series		356
13.2.1			The Conditional Distribution Method	357
13.2.2			Memoryless Transformations	358
13.3		Exercises		362
14	Markov Chain Monte Carlo Methods			363
14.1		Markov Chain Sampling Algorithms		364
14.1.1			Metropolis-Hastings Algorithm	364
14.1.2			Gibbs Sampling	368
14.1.3			Hit-and-Run	371
14.2		Perfect Sampling for Markov Chain Monte Carlo		372
14.2.1			Coupling from the Past	372
14.3		Markov Chain Monte Carlo Methods for Random Vectors		376
14.3.1			Perfect Sampling Algorithms for the Rd	377
14.3.2			Approximate Algorithms	383
14.4		Exercises		385
15	Some Simulation Examples			387
15.1		Financial Simulation		387
15.1.1			Option Pricing	387
15.1.2			Value at Risk	394
15.2		Bayesian Statistics		400
15.2.1			Gibbs Sampling and Universal Random Variate Generation	401
15.2.2			Vector Generation of the Posterior Distribution	407
15.3		Exercises		409
List of Algorithms				411
References				415
Author index				429
Selected Notation				433
Subject Index and Glossary				435

Home

Project

Monograph

Literature

Links

Software

Wolfgang Hörmann and Josef Leydold   (October 21st, 2003)

Research supported by