Non-Uniform Random Variate Generation
Non-Uniform Random Variate Generation
(originally published with Springer-Verlag, New York, 1986)
Luc Devroye
School of Computer Science
McGill University
Preface to the Web Edition
When I wrote this book in 1986, I had to argue
long and hard with Springer Verlag to publish it.
They printed a small number of copies, and never
bothered with a second printing, even though,
surprisingly, there seemed to be some continued
demand for the book. I have asked Springer to
print more copies, but they flatly refused, unless
I was willing to publish a second edition with
them in the near future. Burnt once, why would
I trust them with a second edition? Also,
I figured that since Springer had gross income
about 500,000 US dollars from my books with them,
that they would be more generous with their
royalties and more responsive to demands for
second printings. The contrary is true in fact:
royalties are decreasing (they stand now at 7.5%
per book), and I feel that I am just one of the
many academic rape victims.
As the book is out of print, the copyright
and ownership is mine, so I do with it what I want.
On these web pages, you will find a fine
scan of my book in text searchable PDF format (thanks, HK).
This is the original text. A list of errata
is here.
Furthermore, I give anyone the permission, even without
asking me, to take these PDF files to a printer,
print as many copies as you like, and sell them
for profit.
If you would like me to advertise
the sales points of the hard copies, please let me
know.
To the libraries: Please do not
charge patrons for copying this book. I grant everyone
the right to copy at will, for free.
So, there you have it. Eventually, I will do this
with all my books. While I love Springer, my honeymoon
with them is over. I will of course never start any affairs
with the champion bloodsuckers like Elsevier, Kluwer
or Dekker. Outfits I like are SIAM (nonprofit),
Dover (great pricing) and Oxford University Press
(allowing authors to post books on the web).
With the arrival of Amazon, book advertising is no
longer necessary, and one can publish with any
company, really. So, it will be a matter of a few years
before the old publishers will come back to the
academics on their hands and knees asking for
manuscripts. Too late.
The zip file
with all PDF files is provided for your convenience. Below, you
will find a table of contents and an index, both in HTML
format: look for a keyword, note the page number, go
to the right chapter via the table, and you are done.
Luc Devroye
Montreal, September 29, 2003
Table of contents
PREFACE
TABLE OF CONTENTS
I.
INTRODUCTION 1
1. General outline. 1
2. About our notation. 5
2.1. Definitions. 5
2.2. A few important univariate densities. 7
3. Assessment of random variate generators. 8
3.1. Distributions with no variable parameters. 9
3.2. Parametric families. 9
4. Operations on random variables. 11
4.1. Transformations. 11
4.2. Mixtures. 16
4.3. Order statistics. 17
4.4. Convolutions. Sums of independent random variables. 19
4.5. Sums of independent uniform random variables. 21
4.6. Exercises. 23
II.
GENERAL PRINCIPLES IN RANDOM VARIATE GENERATION 27
1. Introduction. 27
2. The inversion method. 27
2.1. The inversion principle. 27
2.2. Inversion by numerical solution of $F(X)=U$. 31
2.3. Explicit approximations. 35
2.4. Exercises. 36
3. The rejection method. 40
3.1. Definition. 40
3.2. Development of good rejection algorithms. 43
3.3. Generalizations of the rejection method. 47
3.4. Wald's equation. 50
3.5. Letac's lower bound. 52
3.6. The squeeze principle. 53
3.7. Recycling random variates. 58
3.8. Exercises. 60
4. Decomposition as discrete mixtures. 66
4.1. Definition. 66
4.2. Decomposition into simple components. 66
4.3. Partitions into intervals. 67
4.4. The waiting time method for asymmetric mixtures. 71
4.5. Polynomial densities on $[0,1]$. 71
4.6. Mixtures with negative coefficients. 74
5. The acceptance-complement method. 75
5.1. Definition. 75
5.2. Simple acceptance-complement methods. 77
5.3. Acceleration by avoiding the ratio computation. 78
5.4. An example : nearly flat densities on $[0,1]$. 79
5.5. Exercises. 81
III.
DISCRETE RANDOM VARIATES 83
1. Introduction. 83
2. The inversion method. 85
2.1. Introduction. 85
2.2. Inversion by truncation of a continuous random variate. 87
2.3. Comparison-based inversions. 88
2.4. The method of guide tables. 96
2.5. Inversion by correction. 98
2.6. Exercises. 101
3. Table look-up methods. 102
3.1. The table look-up principle. 102
3.2. Multiple table look-ups. 104
4. The alias method. 107
4.1. Definition. 107
4.2. The alias-urn method. 110
4.3. Geometrical puzzles. 111
4.4. Exercises. 112
5. Other general principles. 113
5.1. The rejection method. 113
5.2. The composition and acceptance-complement methods. 116
5.3. Exercises. 116
IV.
SPECIALIZED ALGORITHMS 118
1. Introduction. 118
1.1. Motivation for the chapter. 118
1.2. Exercises. 118
2. The Forsythe-von Neumann method. 121
2.1. Description of the method. 121
2.2. Von Neumann's exponential random variate generator. 125
2.3. Monahan's generalization. 127
2.4. An example : Vaduva's gamma generator. 130
2.5. Exercises. 132
3. Almost-exact inversion. 133
3.1. Definition. 133
3.2. Monotone densities on $[0, inf )$. 134
3.3. Polya's approximation for the normal distribution. 135
3.4. Approximations by simple functions of normal random variates. 136
3.5. Exercises. 143
4. Many-to-one transformations. 145
4.1. The principle. 145
4.2. The absolute value transformation. 147
4.3. The inverse gaussian distribution. 148
4.4. Exercises. 150
5. The series method. 151
5.1. Description. 151
5.2. Analysis of the alternating series algorithm. 154
5.3. Analysis of the convergent series algorithm. 156
5.4. The exponential distribution. 157
5.5. The Raab-Green distribution. 158
5.6. The Kolmogorov-Smirnov distribution. 161
5.7. Exercises. 168
6. Representations of densities as integrals. 171
6.1. Introduction. 171
6.2. Khinchine's and related theorems. 171
6.3. The inverse-of-$f$ method for monotone densities. 178
6.4. Convex densities. 179
6.5. Recursive methods based upon representations. 180
6.6. A representation for the stable distribution. 183
6.7. Densities with Polya type characteristic functions. 186
6.8. Exercises. 191
7. The ratio-of-uniforms method. 194
7.1. Introduction. 194
7.2. Several examples. 197
7.3. Exercises. 203
V.
UNIFORM AND EXPONENTIAL SPACINGS 206
1. Motivation. 206
2. Uniform and exponential spacings. 207
2.1. Uniform spacings. 207
2.2. Exponential spacings. 211
2.3. Exercises. 213
3. Generating ordered samples. 213
3.1. Generating uniform $[0,1]$ order statistics. 214
3.2. Bucket sorting. Bucket searching. 215
3.3. Generating exponential order statistics. 219
3.4. Generating order statistics with distribution function F. 220
3.5. Generating exponential random variates in batches. 223
3.6. Exercises. 223
4. The polar method. 225
4.1. Radially symmetric distributions. 225
4.2. Generating random vectors uniformly distributed on $C sub d$. 230
4.3. Generating points uniformly in and on $C sub 2$. 233
4.4. Generating normal random variates in batches. 235
4.5. Generating radially symmetric random vectors. 236
4.6. The deconvolution method. 239
4.7. Exercises. 240
VI.
THE POISSON PROCESS 246
1. The Poisson process. 246
1.1. Introduction. 246
1.2. Simulation of homogeneous Poisson processes. 248
1.3. Nonhomogeneous Poisson processes. 250
1.4. Global methods for nonhomogeneous Poisson
process simulation. 257
1.5. Exercises. 258
2. Generation of random variates with a given hazard rate. 260
2.1. Hazard rate. Connection with Poisson processes. 260
2.2. The inversion method. 261
2.3. The composition method. 262
2.4. The thinning method. 264
2.5. DHR distributions. Dynamic thinning. 267
2.6. Analysis of the dynamic thinning algorithm. 269
2.7. Exercises. 276
3. Generating random variates with a given
discrete hazard rate. 278
3.1. Introduction. 278
3.2. The sequential test method. 279
3.3. Hazard rates bounded away from 1. 280
3.4. Discrete dynamic thinning. 283
3.5. Exercises. 284
VII.
UNIVERSAL METHODS 286
1. Black box philosophy. 286
2. Log-concave densities. 287
2.1. Definition. 287
2.2. Inequalities for log-concave densities. 288
2.3. A black box algorithm. 290
2.4. The optimal rejection algorithm. 293
2.5. The mirror principle. 295
2.6. Non-universal rejection methods. 298
2.7. Exercises. 308
3. Inequalities for families of densities. 310
3.1. Motivation. 310
3.2. Bounds for unimodal densities. 310
3.3. Densities satisfying a Lipschitz condition. 320
3.4. Normal scale mixtures. 325
3.5. Exercises. 328
4. The inversion-rejection method. 331
4.1. The principle. 331
4.2. Bounded densities. 332
4.3. Unimodal and monotone densities. 334
4.4. Monotone densities on $[0,1]$. 335
4.5. Bounded monotone densities : inversion-rejection
based on Newton-Raphson iterations. 341
4.6. Bounded monotone densities : geometrically
increasing interval sizes. 344
4.7. Lipschitz densities on $[0, inf )$. 348
4.8. Exercises. 355
VIII.
TABLE METHODS FOR CONTINUOUS RANDOM VARIATES 358
1. Composition versus rejection. 358
2. Strip methods. 359
2.1. Definition. 359
2.2. Example 1 : monotone densities on $[0,1]$. 362
2.3. Other examples. 366
2.4. Exercises. 367
3. Grid methods. 368
3.1. Introduction. 368
3.2. Generating a point uniformly in a compact set $A$. 368
3.3. Avoidance problems. 372
3.4. Fast random variate generators. 375
IX.
CONTINUOUS UNIVARIATE DENSITIES 379
1. The normal density. 379
1.1. Definition. 379
1.2. The tail of the normal density. 380
1.3. Composition/rejection methods. 382
1.4. Exercises. 391
2. The exponential density. 392
2.1. Overview. 392
2.2. Marsaglia's exponential generator. 394
2.3. The rectangle-wedge-tail method. 397
2.4. Exercises. 401
3. The gamma density. 401
3.1. The gamma family. 401
3.2. Gamma variate generators. 404
3.3. Uniformly fast rejection algorithms for $a>= 1$. 407
3.4. The Weibull density. 414
3.5. Johnk's theorem and its implications. 416
3.6. Gamma variate generators when $a <= 1$. 419
3.7. The tail of the gamma density. 420
3.8. Stacy's generalized gamma distribution. 423
3.9. Exercises. 423
4. The beta density. 428
4.1. Properties of the beta density. 428
4.2. Overview of beta generators. 431
4.3. The symmetric beta density. 433
4.4. Uniformly fast rejection algorithms. 437
4.5. Generators when $min (a,b) <= 1$. 439
4.6. Exercises. 444
5. The t distribution. 445
5.1. Overview. 445
5.2. Ordinary rejection methods. 447
5.3. The Cauchy density. 450
5.4. Exercises. 451
6. The stable distribution. 454
6.1. Definition and properties. 454
6.2. Overview of generators. 458
6.3. The Bergstrom-Feller series. 460
6.4. The series method for stable random variates. 463
6.5. Exercises. 467
7. Nonstandard distributions. 468
7.1. Bessel function distributions. 468
7.2. The logistic and hyperbolic secant distributions. 471
7.3. The von Mises distribution. 473
7.4. The Burr distribution. 476
7.5. The generalized inverse gaussian distribution. 478
7.6. Exercises. 480
X.
DISCRETE UNIVARIATE DISTRIBUTIONS 485
1. Introduction. 485
1.1. Goals of this chapter. 485
1.2. Generating functions. 486
1.3. Factorials. 489
1.4. A universal rejection method. 493
1.5. Exercises. 496
2. The geometric distribution. 498
2.1. Definition and genesis. 498
2.2. Generators. 499
2.3. Exercises. 500
3. The Poisson distribution. 501
3.1. Basic properties. 501
3.2. Overview of generators. 502
3.3. Simple generators. 502
3.4. Rejection methods. 506
3.5. Exercises. 518
4. The binomial distribution. 520
4.1. Properties. 520
4.2. Overview of generators. 523
4.3. Simple generators. 523
4.4. The rejection method. 526
4.5. Recursive methods. 536
4.6. Symmetric binomial random variates. 538
4.7. The negative binomial distribution. 543
4.8. Exercises. 543
5. The logarithmic series distribution. 545
5.1. Introduction. 545
5.2. Generators. 546
5.3. Exercises. 549
6. The Zipf distribution. 550
6.1. A simple generator. 550
6.2. The Planck distribution. 552
6.3. The Yule distribution. 553
6.4. Exercises. 553
XI.
MULTIVARIATE DISTRIBUTIONS 554
1. General principles. 554
1.1. Introduction. 554
1.2. The conditional distribution method. 555
1.3. The rejection method. 557
1.4. The composition method. 557
1.5. Discrete distributions. 559
1.6. Exercises. 562
2. Linear transformations. The multinormal distribution. 563
2.1. Linear transformations. 563
2.2. Generators of random vectors with a
given covariance matrix. 564
2.3. The multinormal distribution. 566
2.4. Points uniformly distributed in a hyperellipsoid. 567
2.5. Uniform polygonal random vectors. 568
2.6. Time series. 571
2.7. Singular distributions. 571
2.8. Exercises. 572
3. Dependence. Bivariate distributions. 573
3.1. Creating and measuring dependence. 573
3.2. Bivariate uniform distributions. 576
3.3. Bivariate exponential distributions. 583
3.4. A case study: bivariate gamma distributions. 586
3.5. Exercises. 588
4. The Dirichlet distribution. 593
4.1. Definitions and properties. 593
4.2. Liouville distributions. 596
4.3. Exercises. 599
5. Some useful multivariate families. 600
5.1. The Cook-Johnson family. 600
5.2. Multivariate Khinchine mixtures. 603
5.3. Exercises. 604
6. Random matrices. 605
6.1. Random correlation matrices. 605
6.2. Random orthogonal matrices. 607
6.3. Random $R times C$ tables. 608
6.4. Exercises. 610
XII.
RANDOM SAMPLING 611
1. Introduction. 611
2. Classical sampling. 612
2.1. The swapping method. 612
2.2. Classical sampling with membership checking 613
2.3. Exercises. 619
3. Sequential sampling. 619
3.1. Standard sequential sampling. 619
3.2. The spacings method for sequential sampling. 621
3.3. The inversion method for sequential sampling. 624
3.4. Inversion-with-correction. 625
3.5. The ghost point method. 626
3.6. The rejection method. 631
3.7. Exercises. 635
4. Oversampling. 635
4.1. Definition. 635
4.2. Exercises. 638
5. Reservoir sampling. 638
5.1. Definition. 638
5.2. The reservoir method with geometric jumps. 640
5.3. Exercises. 641
XIII.
RANDOM COMBINATORIAL OBJECTS 642
1. General principles. 642
1.1. Introduction. 642
1.2. The decoding method. 643
1.3. Generation based upon recurrences. 645
2. Random permutations. 648
2.1. Simple generators. 648
2.2. Random binary search trees. 648
2.3. Exercises. 650
3. Random binary trees. 652
3.1. Representations of binary trees. 652
3.2. Generation by rejection. 655
3.3. Generation by sequential sampling. 656
3.4. The decoding method. 657
3.5. Exercises. 657
4. Random partitions. 657
4.1. Recurrences and codewords. 657
4.2. Generation of random partitions. 660
4.3. Exercises. 661
5. Random free trees. 662
5.1. Prufer's construction. 662
5.2. Klingsberg's algorithm. 664
5.3. Free trees with a given number of leaves. 665
5.4. Exercises. 666
6. Random graphs. 667
6.1. Random graphs with simple properties. 667
6.2. Connected graphs. 668
6.3. Tinhofer's graph generators. 669
6.4. Bipartite graphs. 671
6.5. Excercises. 673
XIV.
PROBABILISTIC SHORTCUTS AND ADDITIONAL TOPICS 674
1. The maximum of iid random variables. 674
1.1. Overview of methods. 674
1.2. The quick elimination principle. 675
1.3. The record time method. 679
1.4. Exercises. 681
2. Random variates with given moments. 682
2.1. The moment problem. 682
2.2. Discrete distributions. 686
2.3. Unimodal densities and scale mixtures. 687
2.4. Convex combinations. 689
2.5. Exercises. 693
3. Characteristic functions. 695
3.1. Problem statement. 695
3.2. The rejection method for characteristic functions. 696
3.3. A black box method. 700
3.4. Exercises. 715
4.
The simulation of sums. 716
4.1. Problem statement. 716
4.2. A detour via characteristic functions. 718
4.3. Rejection based upon a local central limit theorem. 719
4.4. A local limit theorem. 720
4.5. The mixture method for simulating sums. 731
4.6. Sums of independent uniform random variables. 732
4.7. Exercises. 734
5. Discrete event simulation. 735
5.1. Future event set algorithms. 735
5.2. Reeves's model. 738
5.3. Linear lists. 740
5.4. Tree structures. 747
5.5. Exercises. 748
6. Regenerative phenomena. 749
6.1. The principle. 749
6.2. Random walks. 749
6.3. Birth and death processes. 755
6.4. Phase type distributions. 757
6.5. Exercises. 758
7. The generalization of a sample. 759
7.1. Problem statement. 759
7.2. Sample independence. 760
7.3. Consistency of density estimates. 762
7.4. Sample indistinguishability. 763
7.5. Moment matching. 764
7.6. Generators for $f sub n$. 765
7.7. Exercises. 766
XV.
THE RANDOM BIT MODEL 768
1. The random bit model. 768
1.1. Introduction. 768
1.2. Some examples. 769
2. The Knuth-Yao lower bound. 771
2.1. DDG trees. 771
2.2. The lower bound. 771
2.3. Exercises. 775
3. Optimal and suboptimal DDG-tree algorithms. 775
3.1. Suboptimal DDG-tree algorithms. 775
3.2. Optimal DDG-tree algorithms. 777
3.3. Distribution-free inequalities for the performance
of optimal DDG-tree algorithms. 780
3.4. Exercises. 782
REFERENCES 784
INDEX 817
2-3 tree 613
2-3 tree
in discrete event simulation 747
Abramowitz, M. 297 302 391 415 678
absolute continuity 172
absolute value transformation 147
absorbing Markov chain 757
acceptance complement method
for discrete distributions 116
acceptance-complement method 75
accelerated 78
for Cauchy distribution 81 451
for Poisson distribution 502
for t distribution 446
of Ahrens and Dieter 77 79
squeeze principle for 78
aceptance-complement method
for nearly flat densities 79
adaptive inversion method 38
adaptive strip method 367
adjacency list 669
admissible algorithm 9
admissible generator 9 10
Afifi, A.A. 606
Aho, A.V. 90 92 214 372 669
Ahrens, J.H. 36 72 76 77 84 98 121 145 359 379 380 383 391 396 397 405 413 420 423 424 425 432 502 507 518 523 538 617
Ahrens-Dieter generator
for exponential distribution 397
Aitchison, J. 594
Akima, H. 763
Alder, B.J. 372
algorithm B2PE
for beta distribution 305 309
algorithm B4PE
for beta distribution 305
algorithm of Nijenhuis and Wilf
for classical sampling 618
algorithm 2
Ali, M.M. 578
alias method
algorithm 108
bit-based 777
set-up 109
with two tables 109
alias-urn method 110
almost-exact inversion method 133
for exponential distribution 134
for gamma distribution 137 139 141 145
for monotone densities 134
for normal distribution 135 380
for t distribution 143
alternating series method 153
analysis of 154
exponential version of 154
for exponential distribution 158
for Kolmogorov-Smirnov distribution 162
for Raab-Green distribution 158
analytic characteristic function 685
Ananthanarayanan, K. 359
Anderson, T.W. 168 716
Anderson-Darling statistic 168
Andrews, D.F. 326
approximations for inverse of normal distribution function 36
arc sine distribution 429 481
as the projection of a radially symmetric random vector 230
deconvolution method 239
polar method for 482
properties of 482
Archer, N.P. 687
Arfwedson's distribution 497
Arfwedson, G. 497
Arnason, A.N. 432
Arnold, B.C. 482 583
Arnold, D.B. 592 656
Asau, Y. 96
assessment of generators 8
association 574 576 589
asymmetric Kolmogorov-Smirnov statistics 167
asymmetric mixtures 71
asymptotic independence 760
Atkinson's algorithm
for Poisson distribution 518
Atkinson, A.C. 121 379 380 404 432 439 440 443 480 502 505 507 518
Atkinson-Whittaker method
for beta distribution 440 443
autocorrelation matrix 571
AVL tree
in discrete event simulation 747
avoidance problems 372
grid method for 373
Baase, S. 214
Babu, A.J.G. 304 305 309 432
Badel, M. 571
Bailey, B.J.R. 36
balanced binary search tree
in discrete event simulation 746
balanced parentheses 652
ball-in-urn method 608 609
for multinomial distribution 558
for random bipartite graphs 671
Banks, J. 4 736
Barbu, G. 204
Barlow, R.E. 260 277 343 356 742
Barnard, D.R. 367
Barndorff-Nielsen, O. 329 330 478 483
Barnett, V. 582
Barr, D.R. 566
Bartels's bounds 460 461
Bartels, R. 458 459 460 462
Bartlett's kernel 762 765 767
inversion method for 767
order statistics method for 766
rejection method for 765
Bartlett, M.S. 762
Barton, D.E. 168 519
Basu, D. 594
batch method
for exponential distribution 223
Beasley, J.D. 36
Beckman, R.J. 175
Bell, J.R. 236 380
Bendel, R.B. 606
Bene, B. 4
Bentley, J.L. 215
Berenson, M.L. 215 220
Bergstrom, H. 459 460
Bergstrom-Feller series
for stable distribution 459 460 461
Berman's method
analysis of 419
for beta distribution 418
for gamma distribution 419 420
Berman's theorem 416
Berman, M.B. 416 420
Bernoulli distribution 486 521
properties of 689
Bernoulli generator 769
Bernoulli number 490 493 550
Bernoulli trial 521
Berry-Esseen theorem
application of 225
Besag, J.E. 372
Bessel function distribution 469
type I 469
type II 469
Bessel function 469
integral representation for 470
modified 469
of the first kind 473 755
of the second kind 469
Best's rejection method
for gamma distribution 410
Best, D.J. 379 380 405 407 410 420 426 436 447 450 473 474 476
beta distribution 428
algorithm B2PE for 305 309
algorithm B4PE for 305
algorithm BA for 438
algorithm BB for 438
algorithm BC for 439
as an IHR distribution 343
Atkinson-Whittaker method for 440 443
Berman's method for 418
Cheng's rejection method for 438
definition 7
Forsythe's method for 432
inversion-rejection method for 339 347
Johnk's method for 418 432 439
log-concavity of 287
of second kind 25
of the second kind 428 429 437 444
properties of 416 428 429
rejection method for 432
relation to binomial distribution 536
relation to Cauchy distribution 429
relation to Dirichlet distribution 595
relation to F distribution 429
relation to gamma distribution 429 432 595
relation to multivariate Pearson II distribution 237
relation to multivariate Pearson VII distribution 238
relation to order statistics 17
relation to Pearson VI distribution 429
relation to Snedecor distribution 429
relation to t distribution 429
relation to uniform distribution on unit sphere 227
relation to uniform order statistics 210 431
relation to z distribution 330
shape of 428
strip method for 432
uniform order statistics method for 431
universal method for 432
with one or two parameters less than one 439
Beyer, W.H. 245
Bhagavan, B.K. 571
Bhattacharjee, G.P. 678
Bhattacharyya, B.C. 482
Bignami, A. 74
binary search tree 89 613
in discrete event simulation 747 748
inorder traversal of 89
nearly optimal 94
set-up of 90
binary tree
equivalent 652
inorder traversal of 653
representation of 652
similar 652
Binet's series 491 497
for the log-gamma function 491
binomial distribution 486 496 520
coin flip method for 524
convergence to normal distribution 526
definition 84
first waiting time method for 525
first waiting time property 522
generating function of 521
genesis 521
inequalities for 527 544
inversion method for 524
properties of 497 521 526
recursive method for 523 536 537 545
rejection method for 115 523 526 529 533 543
relation to beta distribution 536
relation to geometric distribution 522
relation to hypergeometric distribution 545
relation to Poisson distribution 543
second waiting time method for 525
second waiting time property 522
sequential search method for 89
splitting algorithm for 527
table method for 523
universal rejection method for 495
bipartite graph 671
birth and death process 755
bisection method 32 38
analysis 38
bit vector 613
bivariate dependence 576
bivariate distributions
transformations of 577
bivariate exponential distribution 583 584
of Johnson and Tenenbein 585 591
of Lawrance and Lewis 585
of Marshall and Olkin 585
of Moran 585
trivariate reduction for 592
bivariate extreme value distribution 563
bivariate gamma distribution 586
composition method for 587
trivariate reduction for 587 588
bivariate geometric distribution
trivariate reduction for 592
bivariate Hermite distribution 592
bivariate multinormal distribution 566
bivariate normal distribution 581
bivariate Poisson distribution 592
trivariate reduction for 592
bivariate uniform distribution 576 578 589
bivariate Weibull distribution
trivariate reduction for 592
black box method 286
for characteristic function 696
for log-concave densities 290
Blaesild, P. 478
Blum, M. 431
Bolshev, L.N. 25 136 144 518
Bondesson, L. 458
Boole's rule 701
bootstrap estimate 766
Borel-Tanner distribution 520
Boswell, M.T. 4 759
bounded densities 43
grid method for 376
inversion-rejection method for 332
rejection method for 43
strip method for 360
bounded monotone densities
inversion-rejection method for 345
Box, G.E.P. 206 235 380
Box-Muller method
for normal distribution 235
Boyett, J.M. 608
Bratley, P. 4 29 251 736 767
Bray, T.A. 359 380 383 388 392 397
Brent, R. 295
Brent, R.P. 121 380
Brown, G.W. 457
Bryson, M.C. 603 604
bucket searching 215 218
bucket sorting 215 219
analysis of 216 224
bucket structure 613
in discrete event simulation 743 744 745
Burr distribution 476 477
inversion method for 477
Burr family 476 477 685
Burr XII distribution 423 432 437
generator for 411
Burr, I.W. 476
busy period
of a queue 755
Butcher, J.C. 391
Butler, E.L. 763
Cacoullos's theorem 452
Cacoullos, T. 446 452
Cannon, L.E. 106
Cantelli's inequality 33
car parking problem 372
search tree for 374
Carleman's condition 684
Carlton, A.G. 24
Carson, J.S. 4 736
Catalan's constant 120
Cauchy distribution 445 450
acceptance-complement method for 81 451
as a normal scale mixture 326
as a stable distribution 183 455
as dominating distribution 45
closure under addition 25
definition 7
inversion method for 29 450
Kronmal-Peterson generator for 82
polar method for 451
properties of 452
ratio-of-uniforms method for 201
relation to beta distribution 429
relation to gamma distribution 427
relation to normal distribution 240 451 452
relation to uniform distribution in unit circle 234
tail of 453
Cawdery, M.N. 367
Cayley's theorem 662
central limit theorem 21 136 222
for binomial distribution 526
local 719
Chalmers, C.P. 606
Chambers, J.M. 184 185 459
characteristic function 6 19 695
black box method for 696
definition 5
inequalities for 707 721
of uniform distribution 708
Polya 718
rejection method for 697
with compact support 706 712
Chebyshev's inequality 321
Chen, H.C. 96
Cheng's rejection method
for beta distribution 438
for gamma distribution 411 413 423
Cheng, R.C.H. 194 203 405 406 411 412 413 423 432 437 438 439 477
Cherian, K.C. 587
Chernin, K.E. 183 184 455 459
Chhikara, R.S. 148
chi-square distribution 403
properties 13
Chmielewski, M.A. 226
Chow, Y.S. 5 21 50 63 225 323
Cinlar, E. 246 251 257 261
circle avoidance problem 372
circle parking problem 374
circular array
in discrete event simulation 741
Cislak, P.J. 476
classical sampling 612
algorithm of Nijenhuis and Wilf for 618
analysis of 614 615
with membership checking based on a hash table 616
with membership checking 613
closed hashing 613 617
codeword 662
coding function 559 643
for binary tree 657 658
for edges in a graph 668
for random partition 661
Cohen, J. 673
coin flip method
for binomial distribution 524
coin flips
simulation of 104
compact support 43
comparison-based inversion methods 88
compiled code 8
complete binary tree 90
complexity 2
composition method with quick acceptance 263
composition method 66 68
analysis of 69
based upon hazard rates 262
for bivariate gamma distribution 587
for discrete distributions 116
for multivariate distributions 557
for normal distribution 67
for order statistics 224
for Poisson processes 253
for polynomial densities 71 72
modified 69
composition-rejection method
for gamma distribution 420
for normal distribution 380 382
for t distribution 446 453
compound Poisson distribution 487
compound Weibull distribution 414
comprehensive family 581
concave distribution 172
concave monotone densities
inequalities for 328
universal rejection method for 329
conditional density 555
conditional distribution method 555
for Gumbel's bivariate exponential family 584
for Morgenstern's family 580
for multinomial distribution 558 559 731
for multinormal distribution 556
for multivariate Cauchy distribution 555
for normal distribution 556
for random $R times C$ table 610
tables for 561
connected graph 668
consistency 762
consistent density estimate 762
context-free language 673
contingency table 608
continuous mixtures
definition 16
convergence to the stable distribution 468
convergent series method 152
analysis of 156
convex characteristic function 186
convex densities 179
generator for 180
inequalities for 311
inversion-rejection method for 355
universal rejection method for 313
convex density
inequalities for 322
convex distribution 172
convex hull 571
convex polygon in the plane 570
convex polytope 568
convolutions 19
Cook, J.M. 241
Cook, R.D. 600 602
Cook-Johnson distribution 600 602
properties of 601
Cooper, B.E. 678
Cornish-Fisher approximation 136
correlated random variates 29
correlation coefficient 573
covariance matrix 564
random vector with given 565
Cox, D.R. 258
Cramer, H. 733
cumulative hazard rate 260
cyclic rate function 256
Dagpunar, J.S. 426
Dahl, O.J. 743
Darboux's formula 460 462
Darboux, M. 460 462
Darling, D.A. 168 716
Davey, D. 743 746
David, F.N. 587
Davidovic, Ju.S. 309
Davis, P.J. 701 704
DDG tree algorithm 771
analysis of 772
optimal 777
suboptimal 775
DDG tree 771
for rejection method 777
relation to finite state machine 782
de Balbine, G. 648 651
de Matteis, A. 74
Deak, I. 4 77 232 566
decoding function 559
decoding method 643
for random binary tree 657
for random permutation 644
Robson's 648
decoding with rejection 645
decomposition of a polytope 570
deconvolution method 239
for arc sine distribution 239
Denardo, E.V. 746
densities with known moments 324
density estimate 759
consistency of 762
density 5
inequalities for 696 698 705
dependence 573
depth of a node 649
derivatives of characteristic function
inequalities for 703
Devroye, L. 4 35 49 151 162 167 169 187 216 218 261 264 268 277 278 288 331 334 406 422 502 507 523 544 568 621 624 625 626 675 676 680 696 759 762 763 764 766 767
DHR distributions 261
dynamic thinning method for 268 283
inversion method for 267
inversion-rejection method for 342 344
properties of 277
diagonal matrix 605
dice
simulation of 103
Dieter, U. 72 76 77 121 145 379 380 383 391 396 397 405 413 420 423 424 425 432 502 507 518 523 538 617
digamma distribution 553
Diggle, P.J. 372
Dirichlet distribution 593
generalization of 596
relation to beta distribution 595
relation to gamma distribution 594
relation to uniform spacings 593
Dirichlet tessellation 374
discrete distribution generating tree 771
discrete distribution 83
inequalities for 497
universal rejection method for 497
discrete dynamic thinning method 283
discrete event simulation 735
discrete hazard rate function 278
discrete Markov chain 757 758
discrete mixtures 66
definition 16
discrete normal distribution
rejection method for 117
discrete random variable 83
discrete t distribution 497
discrete thinning method
analysis of 282
for logarithmic series distribution 282
for negative binomial distribution 284
discrete uniform distribution 88
distribution function 5
inequalities for 321
distributions on hyperspheres 571
Dubey, S.D. 414
Dudewicz, E.J. 483
Dugue, D. 186
Dumouchel, W.H. 458
Durstenfeld, R. 648
Duval, P. 743 744 746
Dvoretzky, A. 373
dynamic hashing 38
dynamic thinning method
analysis of 269
for DHR distributions 268
Easton, M.C. 619
economical method 77
eigenvalue 605
empiric distribution function 167
energy spectrum of fission neutrons 191
Englebrecht-Wiggans, R. 743
entropy 771 775
equiprobable mixture 106
Erdos, P. 170 668
Erdos-Kac distribution 170
series method for 170
Ernvall, J. 617
error estimates
for inversion formula 702
Euler's constant 424 552 639 680
Evans, J.O. 36
event simulator 673
event-driven simulation 736
expected complexity 2
experimental method
for geometric distribution 499
explicit approximations for inverse of distribution function 35
explicit factorial model 631
exponential class of distributions 38
exponential distribution
Ahrens-Dieter generator for 397
almost-exact inversion method for 134
alternating series method for 158
as an IHR distribution 343
batch method for 223
definition 7
generating iid random variates 223
inequalities for 157
inversion method for 29
Marsaglia's generator for 394 396
memoryless property of 219 393
memoryless property 212
mixtures of 16
Monahan's algorithm for 132
order statistics of 219
properties of 125 393 395
properties 12
ratio-of-uniforms method for 200
rectangle-wedge-tail method for 397
relation to exponential integral distribution 176
relation to normal distribution 240
relation to Poisson process 248
relation to Weibull distribution 414
series method for 168
truncated 157
uniform spacings method for 394
von Neumann's method for 125
exponential function
inequalities for 721
exponential inequalities 142
exponential integral distribution
properties of 191
relation to exponential distribution 176
exponential inter-arrival time method
for Poisson distribution 504
exponential mixtures 176
exponential order statistics 219
exponential power distribution 174
log-concavity of 287
multivariate properties of 244
rejection method for 302
relation to gamma distribution 175 193 420
exponential scale mixture 329
exponential spacings method
for exponential order statistics 219
for Poisson process 249
for uniform order statistics 214
exponential spacings 211
extendible hashing 104
extremal value distribution
relation to logistic distribution 39
extreme value distribution
bivariate 563
log-concavity of 287
relation to Weibull distribution 414
F distribution
definition 23
relation to beta distribution 429
relation to gamma distribution 23 428
relation to t distribution 446
factorial moment generating function 486
factorial moment 486
factorial representation 644
factorials
evaluation of 489
Faddeeva, V.N. 565
Fagin, R. 104
Fama, E. 458
Fan, C.T. 620 624
Farlie, D.J.G. 578 589
Feast, G.M. 194 203 406
Fejer-de la Vallee Poussin density 187 459 718
rejection method for 187
Fejer-de la Vallee Poussin distribution 169
Feller, W. 161 168 172 184 246 326 329 452 453 454 455 457 459 460 468 469 470 563 654 684 693 715 721
Ferreri's system 482
Ferreri, C. 482
finite mixtures 66
finite state machine
relation to DDG tree 782
first passage time distribution 150
first waiting time method
for binomial distribution 525
first-passage-time in M/M/1 queue
rejection method for 757
first-passage-time 755
distribution of 755
Fisher's approximation 136
Fisher's transformation 406
Fisher, N.I. 473 474 476
Fisher-von Mises distribution 571
Fishman, G.S. 4 502 505 523 543
Fix, E. 587
Fleishman's family 694
Fleishman, A.I. 694
Floyd, R.W. 431 747
folded normal distribution 469
Folks, J.L. 148
Forsythe's method 123
analysis of 124 132
for beta distribution 432
for normal distribution 380
for the exponential distribution 125
Monahan's generalization of 127
Forsythe, G.E. 121 123 380
Forsythe-von Neumann method 121
for gamma distribution 130 420
Fox, B.L. 4 29 251 431 580 736 746 747 767
Fraker, J.R. 571
Franklin, J.N. 571
Franta, W.R. 746 747
Frechet bounds 586
Frechet distributions 578 579
Frechet's extremal distributions 579 580 581 600
discrete form for 593
Frechet's family 581
Frechet's inequalities 579 586 593
Frechet, M. 578 581
Fredkin, E. 104
free tree 662
Freeman, M.F. 136
Freeman-Tukey approximation 136
Friday, D.S. 4
full correlation range 582
future event set algorithm 736
future event set 736
gambler's ruin problem 758 759
gamma distribution 401
algorithm G4PE for 426
algorithm GB for 405 411 413 420 423
algorithm GBH for 406
algorithm GC for 405
algorithm GO for 405 413 423
algorithm GRUB for 406
algorithm GS for 420 424 425 426
algorithm RGS for 426
algorithm TAD2 for 405
algorithm XG for 405 410
almost-exact inversion method for 137 145
as a DHR distribution 267
as an IHR distribution 343
as an NBUE distribution 742
as an NWUE distribution 742
Berman's method for 419 420
Best's rejection method for 410
characteristic function of 734
Cheng's rejection method for 411 413 423
closure under addition 20
composition-rejection method for 420
convergence to normal distribution 58
definition 7
distribution of ratio 25
Forsythe-von Neumann method for 130 420
generator for 182
inequalities for 408 425 734
Johnk's method for 418 420
local central limit theorem for 404
log-concavity of 287 406
Marsaglia's algorithm RGAMA for 406
normal approximations for 136
properties of 182 402 423 428
properties 13 23
ratio-of-uniforms method for 203 406
recursive properties of 181
rejection method for 132 304 405 415 419 426
relation to beta distribution 403 429 595
relation to Cauchy distribution 427
relation to Dirichlet distribution 594
relation to exponential distribution 402
relation to exponential power distribution 175 193 420
relation to generalized inverse gaussian distribution 478
relation to Johnson-Tietjen-Beckman distribution 175
relation to normal distribution 23 402
relation to Pareto distribution 194
relation to Pearson VI distribution 427
relation to Stacy's generalized gamma distribution 423
relation to t distribution 15 427 445
relation to uniform distribution on unit sphere 227
relation to uniform order statistics 210
sample maximum of 678
strip method for 406
thinning method for 277
Wilson-Hilferty approximation-based method for 139 141
Wilson-Hilferty transformation for 137
with parameter less than one 415 419 424 425
gamma function 490 491 493
gamma-integral distribution 191
Gaver, D.P. 261 277
Gebelein, H. 574
Gehrke, H. 631
general alias algorithm 111
general position 568
generalization of a sample 759
generalized Cauchy distribution 452
generalized gaussian distribution 323
inequalities for 323
universal rejection method for 324
generalized hyperbolic distribution 478
generalized inverse gaussian distribution 478
log-concavity of 287 479
properties of 479
rejection method for 479 480
generalized Liouville distribution 599
generalized logarithmic series distribution 549
generalized logistic distribution 330 480
relation to beta distribution 480
generating function 83 486
generator
admissible 9 10
portability 8
readability 8
set-up time 8
speed 8
Gentle, J.E. 4
geometric distribution 487 498
definition 84
experimental method for 499
inversion method for 87 499 500
memoryless property of 500
properties of 498
relation to binomial distribution 522
relation to logarithmic series distribution 547
sequential test method for 280
geometrical puzzles 111
Gerontides, I. 215 220
ghost point method
analysis of 629
in sequential sampling 626 628
ghost sample method
in sequential sampling 621 626
Gibbons, J.D. 574
Girault, M. 186
Gleaves, J.T. 372
Glick, N. 649
Godwin, H.J. 322 685 691
Gonnet, G.H. 747
Gordon's inequality 681
Gordon, R.D. 681
grade correlation 574
Gram-Charlier series 735
Grassia's distribution 444 445
Grassia, A. 444
Graybill, F.A. 565
Green, E.H. 158
Green, P.J. 372 374
Greenwood, A.J. 63 141 406
Grenander, U. 171
grid method 368
analysis of 370 371
for bounded densities 376
for Riemann integrable densities 377
for unimodal density 377
in avoidance problems 373
size of directory 370
grid
directory 368
Groeneveld, R.A. 482
grouping method
for order statistics 220
Guerra, V.O. 763
guide tables
algorithm 97
definition 96
set-up 98
Gumbel's bivariate exponential family 583 591
conditional distribution method for 584
Gumbel's bivariate logistic distribution
relation to Cook-Johnson distribution 602
Gumbel's family 578
Gumbel, E.J. 287 330 578 583 584
Guralnik, G. 232
Gyorfi, L. 759 762 763 764 766 767
Haas, R.W. 145
Hacet, B.I. 309
halfnormal distribution
as an IHR distribution 343
Halgreen, C. 478
Hall, P. 733
Hammersley, J.M. 29
Hammond, J.L. 571
Handscomb, D.C. 29
Hankel determinant 683
Haq, M.S. 578
Hardy, G.H. 338
Harris, C.M. 194
Hart, J.F. 626
Hartley, H.O. 215
hashing with chaining 617
Hastings, C. 36
hazard rate 260 341
relation to nonhomogeneous Poisson process 260
heap 92
in discrete event simulation 747 748
heapsort 214
Heiberger, R.M. 607
height-balanced tree 613
Henriksen's algorithm 746
Henriksen, J.O. 746
Hermite distribution 592
Hermite polynomial 733
Heyde's family 693
Heyde, C. 693
Heyman, D.P. 749 755
Hickey, T. 673
Hicks, J.S. 243
hierarchical bucket structure
in discrete event simulation 746
Hilferty, M.M. 136
Hill, I.D. 678
Hill, T.W. 685
histogram method 103
histogram 685 687
Hitchin, D. 678
Hoeffding, W. 580 588
Hoffman, R.G. 571
Holcomb, E.W. 458
HOLD model 742 743
analysis of 748
Holliday, E.M. 571
Hopcroft, J.E. 90 92 214 372 669
Hora, S.C. 763
Horner's rule 141
Horspool, N. 101
Hsuan, F.C. 570
Hu, T.C. 91 657
Hu-Tucker algorithm 91
Huffman tree 91 776
analysis of 93
construction of 92
Huffman, D. 91
Hutchinson, T.P. 558 600 602
hybrid rejection method 115
hyperbola distribution 483
hyperbolic cosine distribution 330
hyperbolic distribution 483
log-concavity of 483
rejection method for 483
relation to generalized inverse gaussian distribution 483 484
hyperbolic secant distribution 471
inequalities for 472
inversion method for 472
log-concavity of 287
properties of 472
rejection method for 472
relation to Cauchy distribution 472
relation to normal distribution 472
hypergeometric distribution 544
properties of 545 619
rejection method for 545
relation to binomial distribution 545
universal rejection method for 545
hyperrectangle parking problem 374
hypoexponential distribution
generators for 121
Ibragimov, I.A. 183 184 288 455 459 720
IHR distributions 261
inversion-rejection method for 342
properties of 343 356
incidence matrix 671
inclusion-exclusion principle 21 519
incremental method
for uniform distribution on hypersphere 243
independence 6
indicator function 8
inequalities
for exponential distribution 55
for tails of distribution functions 321
inequality
Chebyshev's 321
Markov's 321
Narumi's 321
integral representation
for Bessel function of first kind 756
for stable distribution 459
invariance under monotone transformations 574
inverse gaussian distribution 148 478
generator of Michael, Schucany and Haas for 149
properties of 148 150
inverse-of-f method 178
application of 315
for normal distribution 178
inversion by correction
algorithm 99
analysis 99
modified algorithms 100
inversion formula 700 719
inversion inequalities 625
inversion method 27 28 261
approximations 35
by sequential search 776
for Bartlett's kernel 767
for binomial distribution 524
for Burr distribution 477
for Cauchy distribution 29 450
for DHR distributions 267
for discrete distributions 85
for exponential distribution 29
for exponential family of distributions 38
for generating the maximum 675
for geometric distribution 87 499 500
for hyperbolic secant distribution 472
for logarithmic series distribution 546
for logistic distribution 39 471
for maxima 30
for multivariate discrete distributions 560
for normal distribution 380
for order statistics 30
for Pareto distribution 29 262
for Poisson distribution 502 505
for Poisson processes 251 252
for power function distribution 262
for Rayleigh distribution 29
for stable distribution 458
for t distribution 445
for t3 distribution 37
for tail of extreme value distribution 276
for tail of Rayleigh distribution 29
for tail of the Cauchy distribution 453
for triangular density 29
for Weibull distribution 262
for wrapped Cauchy density 474
in sequential sampling 621 624
numerical approximation algorithms for 31
inversion of a many-to-one transformation 146
inversion
by binary search 89 93
by correction 98
by hashing 96
by sequential search 85
by truncation of a continuous random variable 87
inversion-rejection method 331
analysis of 337 342 345 351
for beta distribution 339 347
for bounded densities 332
for bounded monotone densities 345
for convex densities 355
for DHR distributions 342
for IHR distributions 342
for Lipschitz densities 348
for monotone densities 336 341
optimization of 339 347
inversion-with-correction 625
Inzevitov, P. 720 731
Irving, D.C. 4 480
Jackson-de la Vallee Poussin distribution 169
Jacobian 14
Jacobs, P.A. 571
Jansson, B. 4 648
jigsaw puzzle method 67
Johnk's method
analysis of 419
for beta distribution 418 432 439
for gamma distribution 418 420
Johnk's theorem 416
Johnk, M.D. 416 420 432
Johnson's family 484
Johnson's system 484 685
Johnson, D.G. 606
Johnson, M.E. 175 237 244 404 576 582 583 585 586 587 590 591 592 600 602 603 604
Johnson, M.M. 175
Johnson, N.L. 7 84 379 480 484 496 498 552 555 600 602 604 688
Johnson-Ramberg bivariate uniform family 592
Johnson-Ramberg method
for normal distribution 244
for radially symmetric distributions 237
Johnson-Tenenbein family 582 583
properties of 590
Johnson-Tietjen-Beckman distribution 175
relation to gamma distribution 175
Jonassen, A. 743
Jones, T.G. 620
Jorgensen, B. 287 478
k-excellence 764
Kac, M. 170
Kachitvichyanukul, V. 502 507 523 545
Kadoya, M. 583 590
Kaminsky, F.C. 261
Kanter, M. 183 184 455 459
Kapadia, C.H. 322
Kawarasaki, J. 631
Kawata, T. 731
Keilson, J. 329
Kelker, D. 226 228 326
Kelly, F.P. 372
Kelton, W.D. 4 736
Kemp's generator
for logarithmic series distribution 548
Kemp, A.W. 86 546 547 559 560 593 759
Kemp, C.D. 559 560 561 592 593 759
Kendall's tau 574
Kendall, D.G. 547
Kendall, M. 678 691 694
Kendall-Stuart density 694
Kennedy, W.J. 4
Kent, J. 329 330
kernel estimate 687 762
analysis of 767
consistency of 767
in Monte Carlo integration 766
mixture method for 765
Khinchine's theorem 172 687
Kimeldorf, G. 574 575 576 589 590
Kimeldorf-Sampson bivariate uniform distribution 589
Kinderman, A.J. 194 195 201 203 379 380 383 390 391 406 446 454
Kinderman-Ramage generator
for normal distribution 391
Kingston, J.H. 737 746 747
Klincsek, T. 216 218
Klingsberg's algorithm 664 665
Klingsberg, P. 663
Knopp's series 493
for the log-gamma function 493
Knopp, K. 493 498
Knott, G.D. 657
Knuth, D.E. 4 214 502 618 638 743 747 768 771 774 777 779 781
Knuth-Yao lower bound 772
Kohrt, K.D. 36 84 98 359
Kolmogorov, A.N. 161 168
Kolmogorov-Smirnov distribution 161
alternating series method for 162
series expansions for 161
Kolmogorov-Smirnov statistic 168
Korenbljum, B.I. 309
Kotz, S. 7 84 379 469 480 496 498 552 555 600 602 604
Kowalski, C.J. 603
Krein's condition 684
Kronmal, R.A. 75 81 82 108 110 359 369 451
Kruskal, W.H. 574
Kuiper's statistic 168
Kuiper, N.H. 168
Kullback, S. 402 423
labeled free tree 665
Laha's distribution 451
Laha, R.G. 451 469
Lakhan, V.C. 571
Lal, R. 426 587 588 591
Lancaster, H.O. 589
Laplace distribution
as a normal scale mixture 326
as dominating distribution 44
generators for 119
properties of 401
relation to normal distribution 25
Law, A.M. 4 736
Lawrance, A.J. 571 583 585 586 591
Lawrance-Lewis bivariate exponential distribution 585
Lehmer's factorial representation 644
Lehmer, D.H. 644
Leipnik, R. 694
Leitch, R.A. 458
Lekkerkerker, C.G. 288
Letac's lower bound 52
application of 124
Letac, G. 52
Levy's representation
for stable distribution 454
Levy, P. 457
Lewis, P.A.W. 251 253 256 258 259 261 264 571 583 585 586 591
Li, F.S. 136
Li, S.T. 571
library traversal 561
Lieblein, J. 26
line distribution 571 572
linear list
back search in 742
front search in 742
in discrete event simulation 740
linear selection algorithm 431
linear transformations 12 563
Linnik's distribution 186
generator for 190
properties of 189
Linnik, Yu.V. 186 720
Liouville distribution 596
generalization of 599
of the first kind 596
properties of 598
relation to Dirichlet distribution 598
Lipschitz condition 63 320
Lipschitz densities
inequalities for 320 322
inversion-rejection method for 348
proportional squeeze method for 63
strip method for 366
universal rejection method for 323
Littlewood, J.E. 338
local central limit theorem 719 720
application of 58
for gamma distribution 404
Loeve, M. 697
log-concave densities 287
black box method for 290
inequalities for 288 290 295 296 299 321 325
optimal rejection method for 293 294
properties of 309
rejection method for 291 292 298 301
tail inequalities for 308
universal rejection method for 301 325
logarithm
inequalities for 140 168 198 508 540 722
logarithmic series distribution 488 545
definition 84
discrete thinning method for 282
inversion method for 546
Kemp's generator for 548
properties of 284 546 547
rejection method for 546 549
relation to geometric distribution 547
sequential test method for 282
logistic distribution 471 518
as a normal scale mixture 326
as a z distribution 330
definition 39
generators for 119
inequalities for 471
inversion method for 39 471
log-concavity of 287
properties of 472 480
properties 39
rejection method for 471
relation to extremal value distribution 39
relation to extreme value distribution 472
lognormal distribution 392 484
moments of 693
lost-games distribution 758 759
Lotwick, H.W. 372 374
Loukas, S. 559 560 561 592 593
lower triangular matrix 564
Lukacs, E. 186 469 694
Lurie, D. 215
Lusk, E.J. 733
Lux's algorithm 61
Lux, I. 60 176
Lyapunov's inequality 324
m-ary heap
in discrete event simulation 747
M/M/1 queue 755 759
Maclaren, M.D. 359 380 397
Maclaurin series 460
Maejima, M. 720 731
Magnus, W. 470 756
Mallows, C.L. 168 184 185 326 459
Malmquist's theorem 212
Malmquist, S. 212
Maly, K. 746 747
Mandelbrot, B. 454
Mannion, D. 373
Mantel, N. 25
many-to-one transformations 145
Mardia's generator
for Plackett's family 589
Mardia, K.V. 473 576 581 587 588 589
marginal density 555
marginal distribution 6
marginal random variable 6
Markov chain
transition matrix 758
Markov's inequality 321
Marsaglia's algorithm RGAMA
for gamma distribution 406
Marsaglia's almost-exact inversion method 136
Marsaglia's approximation 136
Marsaglia's generator
for exponential distribution 394 396
Marsaglia's method
for tail of the normal distribution 381
Marsaglia's table look-up method 106
Marsaglia, G. 4 53 67 106 133 135 136 137 141 143 144 236 241 242 359 378 380 381 382 383 388 392 394 395 397 406 446 605 606
Marsaglia-Bray generator
for normal distribution 390 392
Marshall, A.W. 277 343 356 563 576 583 585 774
Mason, R.L. 215
matched moment generator 690
for unimodal distribution 691
matching distribution 519
rejection method for 520
maximal correlation 29 574 580
maximum of a uniform sample 210
maximum
distribution of 19
inversion method for 30 675
of a gamma sample 678
of a normal sample 678
quick elimination algorithm for 676
record time method for 679 680
simulation of 674
Maxwell distribution
relation to normal distribution 176
Maxwell, W.L. 743
May, J.H. 568
McCallum, D. 112
McCormack, W.M. 737 743 747
McGrath, E.J. 4 480
McKay, A.T. 482
McKay, J.K.S. 661
McMullen, P. 571
mean value 5
median of a uniform sample 18
median 5
density of 18
mergesort 214
method of guide tables 96 97
analysis of 97
method of Lewis and Shedler 264
method of Michael, Schucany and Haas 146
method of percentiles 484
Michael, J.R. 145
Mickey, M.R. 606
Mikhail, N.N. 578
Mikhailov's theorem 177
Mikhailov, G.A. 176 177 191 571
minimal spacing 213
minimax strategy 762
mirror principle 295
for random walk 654
for unimodal densities 329
Mirsky, L. 682
Mitchell, R.L. 367
Mitra, S.S. 457
Mitrinovic, D.S. 681
mixture method
for kernel estimate 765
for simulating sum 731
mixtures of distributions 16
mixtures of triangles 179
mixtures with negative coefficients 74
mode 5
modified Bessel function
of the first kind 473
of the third kind 478 483 484
modified composition method 69
moment generating function 322 486
moment matching
in density estimates 764
moment mismatch 764
moment problem 682
moment 5
Monahan's algorithm 127
for exponential distribution 132
Monahan's theorem 127
Monahan, J.F. 127 132 194 195 201 203 406 446 454
monotone correlation 574
monotone densities
almost-exact inversion method for 134
generator for 174
inequalities for 311 313 321 330 331
inverse-of-f method for 178
inversion method for 39
inversion-rejection method for 336 341
order statistics of 224
splitting algorithm for 335
strip method for 362
universal rejection method for 312 316 317
monotone dependence 575
monotone discrete distributions 114
rejection method for 115
monotone distributions
inequalities for 173
properties of 173
monotone transformations 220
Monte Carlo integration 766
Monte Carlo simulation 580
Moonan, W.J. 565
Moran's bivariate exponential distribution 585
Moran, P.A.P. 518 583 585 586
Morgan, B.J.T. 4
Morgenstern's family 578 590
conditional distribution method for 580
Morgenstern, D. 578
Moses, L.E. 648
Mudholkar, G.S. 472
Muller, M.E. 206 235 379 380 617 620 624
multinomial distribution 558
ball-in-urn method for 558
conditional distribution method for 558 559 731
relation to binomial distribution 558
relation to Poisson distribution 518 563
multinomial method
for Poisson distribution 563
multinormal distribution 566
conditional distribution method for 556
multiple pointer method
in discrete event simulation 743 746
multiple table look-up 104
multiplicative method
for Poisson distribution 504
multivariate Burr distribution 558 600
relation to Cook-Johnson distribution 602
multivariate Cauchy distribution 238 555
conditional distribution method for 555
multivariate Cauchy dsistribution 589
multivariate density 6
multivariate discrete distributions 559
inversion method for 560
multivariate inversion method
analysis of 560 561
multivariate Khinchine mixtures 603
multivariate logistic distribution 600
relation to Cook-Johnson distribution 602
multivariate normal distribution 603 604
relation to Cook-Johnson distribution 602
multivariate Pareto distribution 589 600 604
relation to Cook-Johnson distribution 602 604
multivariate Pearson II distribution 237
relation to beta distribution 237
multivariate Pearson VII distribution 238
relation to beta distribution 238
multivariate transformations of random variables 14
Murty, V.N. 26
Mykytka, E.F. 483
Naderisamani, A. 523 544
Nagao, M. 583 590
Nagao-Kadoya distribution 583 590
naive method
for sum of independent random variables 717
Nance, R.E. 4
Narula, S.C. 136
Narumi's inequality 321 329
Nataf, A. 576
NBUE distribution 742
nearly flat densities
aceptance-complement method for 79
rejection method for 80
negative binomial distribution 284 488 543
as an IHR distribution 284
definition 84
discrete thinning method for 284
generators for 543
properties of 488
negative mixture algorithm of Bignami and de Matteis 74
negative stable distribution 455
Neuts, M.F. 758
Nevalainen, O. 617
Newby, M.J. 220
Newman, T.G. 4 416
Newton-Cotes integration formulas 701
Newton-Raphson iterations 341
Newton-Raphson method 33
convergence of 36 37
Neyman, J. 24
Nievergelt, J. 104
Nijenhuis, A. 617 618 642 645 661
non-lattice distributions 496
nonhomogeneous Poisson process
properties of 254
normal distribution 379
almost-exact inversion method for 135 380
approximation by sum of uniform random variables 25 144
as a stable distribution 183 455
as an NBUE distribution 742
Box-Muller method for 235
closure under addition 19
composition method for 67
composition-rejection method for 380 382
conditional distribution method for 556
convergence to 22
definition 7
Forsythe's method for 380
inequalities for 169 384 385 386
inverse-of-f method for 178
inversion method for 36 380
Johnson-Ramberg method for 244
Kinderman-Ramage generator for 391
log-concavity of 287
Marsaglia-Bray generator for 390 392
moments of 693
polar method for 235 242 380
Polya's approximation for 135
properties 13 23 26
radial symmetry of 228
ratio-of-uniforms method for 199 380
rectangle-wedge-tail method for 380
rejection from Cauchy density 45
rejection from Laplace density 44
rejection method for 56 62 380 391
relation to Cauchy distribution 240
relation to exponential distribution 240
relation to Rayleigh distribution 240 381
relation to t distribution 15
sample maximum of 678
series method for 169 380
table method for 380
tail of the 380
transformations of 136
trapezoidal method for 383 391
normal random vector method
for uniform distribution on hypersphere 230
normal scale mixtures 325 687
inequalities for 327
normalizing transformations 136
Norman, J.E. 106
Norton, R.M. 482
numerical integration 700
numerical inversion algorithms 31
convergence of 35
NWUE distribution 742
Oakford, R.V. 648
Oberhettinger, F. 470 756
Odeh, R.E. 36
Odell, P.L. 4 416
Ojo, M.O. 480
Olds, E.G. 733
Olkin, I. 563 576 583 585 605 606 774
Olusegun George, E. 472 480
open hashing 613
operations on random variables 11
optimal binary search tree 91
optimal DDG tree algorithm
analysis of 778 780
optimal rejection method
for log-concave densities 293 294
Ord, J.K. 84 469 497 735
order statistics method
for Bartlett's kernel 766
for Poisson processes 258
order statistics 207
definition 17
exponential 211
from an arbitrary distribution 220
inversion method for 30
of a mixture 224
of a monotone densities 224
of the Weibull distribution 220
ordered polytope 571
ordinal measures of association 574
Ostrowski, A.M. 34
overflow bucket
in discrete event simulation 746
overflow list
in discrete event simulation 746
oversampling 635 636
analysis of 637
Overstreet, C. 4
Owen, D.B. 322
Padgett, W.J. 149
Pagano, M.E. 758
Papageorgiou, H. 593
parametric form of a density 13
Pareto distribution
as a DHR distribution 267 344
definition 7
dynamic thinning method for 270
inversion method for 29 262
relation to gamma distribution 194
partitions into intervals 67
Parzen, E. 762
Pascal's triangle 659
Patefield, W.M. 609 610
Patel, I.D. 549
Patel, J.K. 322
Paterson, M. 431
Patil, G.P. 4 518 759
Paul, N.J. 359
Paulauskas, V. 458
Paulson, E.S. 458
Payne, J.A. 4
Payne, W.H. 379
Pearce, M.C. 121 379 380 404 432
Pearson family 480 481
Pearson IV distribution 308 480
Pearson product moment correlation coefficient 573
Pearson system 480 481
Pearson V distribution 456
Pearson VI distribution
relation to beta distribution 429
relation to gamma distribution 427
Pearson's system 685
Pearson, E.S. 24
Peizer-Pratt approximation 136
Perks distribution 472
log-concavity of 287
rejection method for 472
Perks, W.F. 287
perturbation matrix 606
Peterson, A.V. 75 81 82 108 110 359 369 451
Petrov, V.V. 58 225 496 720 733
PH-distribution 757
phase type distribution 757
Pippenger, N. 104 431
Plackett's family 578 581 582 588 590
Mardia's generator for 589
Plackett, R.L. 578 588 590 648
Planck distribution 552
relation to Zipf distribution 552
Poisson distribution 487 501
acceptance-complement method for 502
Atkinson's algorithm for 518
convergence to normal distribution 501 518
definition 84
exponential inter-arrival time method for 504
inequalities for 506 509 515
inversion method for 502 505
multinomial method for 563
multiplicative method for 504
properties of 501 503 504 506 518
recursive method for 518
rejection method for 502 511 518
relation to multinomial distribution 518
sequential search method for 86
Poisson point process 246
Poisson process 246 755
composition method for 253
exponential spacings method for 249
homogeneous 246 252
inversion method for 251 252
nonhomogeneous 250
on unit circle 250
order statistics method for 258
properties of 247 738
relation to exponential distribution 248
the uniform distribution method for 248
thinning method for 253 255
polar method 225
for arc sine distribution 482
for Cauchy distribution 451
for normal distribution 235 242 380
for symmetric beta distribution 437
polar representation
for stable distribution 455
Polge, R.J. 571
Polya characteristic function 186 695 718
Polya characteristic functions
representation of 186
Polya, G. 135 338
Polya-Aeppli distribution 468
polynomial densities
composition method for 71 72
polynomial density algorithm of Ahrens and Dieter 73
portability 8 9
positive stable distribution 455 463
power distribution
definition 24
properties of 24
power function distribution
inversion method for 262
power of a gamma random variable 423
power transformations 13
Pratt, V. 431
Prekopa, A. 309
Press, S.J. 454
Price, T.G. 571
Pritsker, A.A.B. 743
probabilistic shortcut 674
probability vector 83
projection method 572
proportional squeeze method 57
application of 63
proportional squeezing 56
Proschan, F. 260 277 343 356 742
Prufer's construction 662 663
quantile 5
quasi-empirical method of Bratley, Fox and Schrage 767
Quenouille, M.H. 488
queueing system 735 755
quick acceptance step 54
quick elimination algorithm
analysis of 676
for generating the maximum 676
quick elimination principle 675
quick-and-dirty estimate 763
quicksort 214
Raab, D.H. 158
Raab-Green density 147
Raab-Green distribution
alternating series method for 158
improved alternating series method for 160
Rabinowitz, M. 215 220
Rabinowitz, P. 701 704
radial transformations 229
radially symmetric distributions 225
Johnson-Ramberg method for 237
properties of 227
Rahman, N.A. 24
Ramage, J.G. 379 380 383 390 391 446 454
Ramberg, J.S. 215 237 244 482 483 587 592
random $R times C$ table 608
conditional distribution method for 610
random binary search tree 649 650
height of 651
random binary tree 652
decoding method for 657
rejection method for 655
sequential sampling for 656 657
random bipartite graph 671
random bipartite graphs
ball-in-urn method for 671
random bit model 768
random codeword 659
random combinatorial objects 642
random connected graph
rejection method for 669
random correlation matrix 605
random cubic graph 672
random free tree 662 663
with given number of nodes and leaves 666
random graph 667
rejection method for 672
random heap 651
random labeled free tree 663
random orthogonal matrix 606 607
random orthonormal matrix 607
random partition 658 659
coding function for 661
of integers 661
recurrence-based method for 660
random permutation 612 644 648
decoding method for 644
Robson's decoding method for 648
swapping method for 646
random r-regular graph 672
random rooted tree 658
random rotation 607
random sampling 611
random string of balanced parentheses
sequential sampling for 657
random string 673
random subset
recurrence-based method for 647
random sum 487
random trie 651
random uniform rotation 607
random unlabeled free tree 666
random variable 5
random variate 2
random vector 6
random walk 470 654 749
first return to origin 754
properties of 751 752
range of a uniform sample 213
rank correlation 574
rate function 250
cyclic 256
log-linear 259
log-quadratic 259
piecewise constant 259
ratio of gamma random variables 428
ratio-of-uniforms method 194
algorithm 196
analysis of 204
for Cauchy distribution 201
for exponential distribution 200
for gamma distribution 203 406
for normal distribution 199 380
for t distribution 200 204 446
for t3 distribution 202 449
with two-sided squeezing 197
Rayleigh distribution 176 469
inversion method for 29
relation to normal distribution 240 381
record time method
for generating the maximum 679 680
record 649
rectangle-wedge-tail method
analysis of 399
for exponential distribution 397
for normal distribution 380
rectangular rule 700
recurrence
for combinatorial objects 646
recurrence-based method
for random partition 660
for random subset 647
recursive generator 181
recursive method
for binomial distribution 523 536 537 545
for Poisson distribution 518
recursive methods based upon representations 180
recycling random variates 58
Reeves's model 738 740
analysis of 741 744 745 748
Reeves, C.M. 737 741 743 747
regenerative phenomena 749
regula falsi method 33
regular density 719
rejection constant 42
rejection method for order statistics
analysis of 222
rejection method
bit-based 770
definition 42
development of 43
for Bartlett's kernel 765
for beta distribution 432
for binomial distribution 115 523 526 529 533 543
for bounded densities with compact support 43
for characteristic function 697
for discrete normal distribution 117
for discrete random variates 113
for exponential power distribution 302
for Fejer-de la Vallee Poussin density 187
for first return to origin in random walk 754
for first-passage-time in M/M/1 queue 757
for gamma distribution 48 132 304 405 415 419 426
for generalized inverse gaussian distribution 479 480
for hyperbolic distribution 483
for hyperbolic secant distribution 472
for hypergeometric distribution 545
for Lipschitz densities 63
for log-concave densities 291 292 298 301
for logarithmic series distribution 546 549
for logistic distribution 471
for matching distribution 520
for monotone discrete distributions 115
for multivariate distributions 557
for nearly flat densities 80
for normal distribution 44 45 380 391
for order statistics 221
for Perks distribution 472
for Poisson distribution 502 511 518
for random binary tree 655
for random connected graph 669
for random graph 672
for Stacy's generalized gamma distribution 423
for symmetric beta distribution 60 193 434
for symmetric binomial distribution 539
for t distribution 446 447 450
for tail of the Cauchy distribution 453
for tail of the gamma density 421 422 425
for truncated gamma distribution 166
for uniform distribution in unit circle 233
for uniform distribution on hypersphere 231
for uniform distribution on unit circle 235
for von Mises distribution 473 476
for Zipf distribution 550
generalization of 49 60
in avoidance problems 372
in sequential sampling 621 631 634
optimization of 62 512
properties 42
Sibuya's modified 62
Vaduva's generalization of 47
validation 40
with recycling 59
reliability theory 260
Relles, D.A. 523 538
Renyi, A. 373 574 589 668
representations of densities as integrals 171
reservoir sampling 638 639
with geometric jumps 640
residual density 382 385
residual life density 330
inequalities for 330
universal rejection method for 330
restricted density 67
Rezucha, I. 620 624
Rider, P.R. 24
Riemann integrability 362
Riemann integrable densities
grid method for 377
strip method for 362
Riemann zeta function 550
Ripley, B.D. 4 84 372 374 473
Rippy, D.V. 571
Rivest, R.L. 431
Roach, S.A. 733
Robbins, H. 373
Robertson, I. 203
Robinson, C.L. 648
Robson's decoding method
for random permutation 648
Robson, J.M. 648
robust scale estimate 763
Rogers, C.A. 688
Rogozin, B.A. 496
Roll, R. 458
Ronning, G. 588
Rosenblatt, M. 171 762
rotation 563
Roy, M.K. 150
Royden, H. 172
Royden, H.L. 686 687
Rubin, P.A. 570
Rubinstein, R.Y. 3 4 232 243 567 570
Rumpf, D.L. 261
Ruskey, F. 657
Ryan, T.P. 606
Sahai, H. 4
Sahler, W. 168
Sakasegawa, H. 380
sample independence 760
sample indistinguishability 763
sampling without replacement 544 611
Sampson, A. 574 575 576 589 590
Sargent, R.G. 737 743 747
Sarmanov, O.V. 574
Satterthwaite, S.P. 600 602
Savage, I.R. 322
Saxe, J.B. 215
scale mixture 557
scale parameter 7
Scheffe's lemma 760
Scheffe's theorem 575 590 760
Scheffe, H. 590 760
Scheuer, E.M. 566
Schmeiser, B.W. 4 84 304 305 308 309 426 432 482 483 502 507 545 562 571 587 588 591
Schonhage, A. 431
Schrage, L.E. 4 29 251 736 767
Schreck, H. 657
Schucany, W.R. 145 215
Schur convexity 774
Schuster, E.F. 392
search tree
in car parking problem 374
secant method 33 38
convergence of 36
second waiting time method
for binomial distribution 525
Seidel, R. 571
Seigerstetter, J. 473
selection sort 217
sequential sampling 619
for random binary tree 656 657
for random string of balanced parentheses 657
ghost point method in 626 628
ghost sample method in 621 626
inversion method in 621 624
rejection method in 621 631 634
spacings method for 621
sequential search method 85
for binomial distribution 89
for Poisson distribution 86
Kemp's improvement of 86
reorganization of 88
sequential search 776
sequential test method 279
analysis of 279
for geometric distribution 280
for logarithmic series distribution 282
series method 151
based upon numerical integration 709
for characteristic functions with compact support 713
for characteristic functions 709
for Erdos-Kac distribution 170
for exponential distribution 168
for normal distribution 169 380
for symmetric stable distribution 465 466 467
for very smooth densities 700
Seshadri, V. 518
set-up time 8 9 10
Severo, N.C. 4
Severo-Zelen approximation 136
Shanthikumar, J.G. 279 280 281 283 284
shape parameter 7
Shedler, G.S. 251 253 256 259 261 264
Shohat, J.A. 682 685 686
Shorrock, R.W. 120
Shuster, J. 148
Sibson, R. 372 374
Sibuya's modified rejection method 62
Sibuya, M. 62 232 380 396 553 631
Simon, H.A. 553
simple distribution 8
simple random variable 8
simplex 207 568 593
Simpson's rule 701
simulation of sum 716
singular distribution 571
Sivazlian, B.D. 596 598 599
skewness-kurtosis plane 484 688
Sleep, M.R. 656
Slezak, N.L. 566
Smirnov, N.V. 161 168
Smith, R.L. 215 220 568
smoothing parameter 762
Snedecor distribution 429
Sobel, M.J. 749 755
Soni, R.P. 470 756
Sorensen, M. 329 330
sorting 214
Sowey, E.R. 4
spacings method
for sequential sampling 621
for uniform distribution on hypersphere 242
Spearman's rho 574
speed 8
splitting algorithm
for binomial distribution 527
for monotone densities 335
Springer, M.D. 11 25 469 562 685
Springer, S.G. 36
square root method 565
square root transformations 13
squeeze method 54
analysis of 65
application of 57
for normal distribution 56
for symmetric beta distribution 64
for uniform distribution in unit circle 233
squeeze principle 53
application of 141
for strip method 360
Srinivasan, R. 469
stable distribution 454
closure under additions 455
convergence to 468
generator of Chambers, Mallows and Stuck for 185 459
inequalities for 461 463
integral representation for 185 459
inversion method for 458
Kanter's method for 183 459
Levy's representation for 454
polar representation for 455
properties of 183 184 185 455 456 457
representation for 183
with exponent 1ドル/2$ 150
Stacy's generalized gamma distribution 423
rejection method for 423
relation to gamma distribution 423
Stacy, E.W. 423
Stadlober, E. 10 77 446
standard sequential sampling 619 620
Standish, T.A. 741 747
Steffensen's inequality 338
Steffensen, J.F. 338
Stegun, I.A. 297 302 391 415 678
Steutel, F.W. 329
Stieltjes's counterexample 694
Stirling number 658 660
of the second kind 658
recurrence for 659
Stirling's series 490
Stoller, D.S. 566
stopping time 50
strip method 359
adaptive 367
analysis of 361 363
for beta distribution 432
for bounded densities 360
for gamma distribution 406
for Lipschitz densities 366
for monotone densities 362
for Riemann integrable densities 362
Strong, H.R. 104
Stuart's theorem 182 420 423 596
Stuart, A. 182 420 423 596 678 691 694
Stuck, B.W. 184 185 459
Subbotin, M.T. 175
suboptimal DDG tree algorithm 775
Sukhatme, P.V. 211
sum of independent random variables 19 708 714 716
convergence to stable law 734
mixture method for 731
naive method for 717
simulation of 496
sum of independent uniform random variables 21
sum of uniform random variables 732
uniformly fast method for 735
sum-of-uniforms method 204
sup correlation 574
Survila, P. 720
swapping method 612
for random permutation 646
symmetric beta distribution 193 433
analysis of 433
convergence to normal distribution 433
generators for 63 65
inequalities for 434 441 442
polar method for 437
rejection from normal density for 193
rejection method for 60 434
relation to t distribution 436 446
squeeze method for 64
Ulrich's polar method for 437
symmetric binomial distribution 538
inequalities for 540
rejection method for 539
symmetric stable distribution 186 455
as a normal scale mixture 326
generator for 188
properties of 189
series method for 465 466 467
t distribution 10 445
acceptance-complement method for 446
almost-exact inversion method for 143
as a normal scale mixture 326
composition-rejection method for 446 453
convergence to normal distribution 447
discrete 497
inequalities for 203 447 448 453 454
inversion method for 445
properties 15
ratio-of-uniforms method for 200 204 446
rejection method for 446 447 450
relation to beta distribution 429
relation to F distribution 446
relation to gamma distribution 427 445 452
relation to multivariate Cauchy distribution 555
relation to symmetric beta distribution 436 446
table method for 446
with three degrees of freedom 37
with two degrees of freedom 407 408 429
t3 distribution 446
ratio-of-uniforms method for 202 449
table look-up method 102
Marsaglia's 106
table look-up 102
multilevel 106
table method
for binomial distribution 523
for normal distribution 380
for t distribution 446
Tadikamalla, P.R. 215 404 405 420 423 445 477 483 518
tail of extreme value distribution
inversion method for 276
tail of log-concave densities 308
tail of Rayleigh distribution
inversion method for 29
tail of the Cauchy distribution 453
inversion method for 453
rejection method for 453
tail of the gamma density 420
rejection method for 421 422 425
tail of the normal distribution 681
Marsaglia's method for 381
properties of 391
Takahasi, K. 558 600 602
Talacko, J. 287 471 472
Talbot, D.R.S. 372
Tamarkin, J.D. 682 685 686
Tanner, J.C. 520
Tanner, M.A. 607
Tapia, R.A. 763
Tarjan, R.E. 431
Tashiro, Y. 232
Taylor's series 55
for characteristic function 684
for densities 698
for logarithm 508
for normal distribution 384
Teicher, H. 5 21 50 63 225
Teichroew's distribution 391
Teichroew, D. 391
Tenenbein, A. 576 582 583 585 586 590 591
Teuhola, J. 617
thinning method 264
analysis of 264 266
for discrete distributions 280
for gamma distribution 277
for Poisson processes 253 255
Thisted, R.A. 607
Thompson, J.R. 763
Tietjen, J.L. 175
time series 571
Tinhofer's graph generators 669
Tinhofer's random graph generator 670
Tinhofer, G. 657 669 670
Titchmarsh, E.C. 550
Tiwari, R.C. 594
Toranzos's system 482
Toranzos, F.I. 482
transformation of a homogeneous Poisson process 257
transformation
of beta random variables 444
transformations of random variables 11
transition matrix 758
translation parameter 7
trapezoidal method
for normal distribution 383 391
trapezoidal rule 701
triangle 569
triangular density 22 23
inversion method for 29
triangulation 570
trie 104
trigamma distribution 553
trivariate reduction 587
for bivariate exponential distribution 592
for bivariate gamma distribution 587 588
for bivariate geometric distribution 592
for bivariate Poisson distribution 592
for bivariate Weibull distribution 592
Trivedi, K.S. 246
Trojanowski, A.E. 657
truncated distributions 38
truncated exponential distribution 401
truncated extreme value distribution
as an IHR distribution 343
truncated gamma distribution
rejection method for 166
Tsang, W.W. 359
Tucker, A.C. 91
Tukey's lambda distribution 482
convergence to exponential distribution 483
convergence to logistic distribution 483
generalization of 482 483
properties of 483
Tukey, J.W. 136 457 482
two-way contingency table 608
Ullman, J.D. 90 92 214 372 669
Ulrich's polar method
for symmetric beta distribution 437
Ulrich, E.G. 571 747
Ulrich, G. 436
uniform distribution in hyperellipsoid 567
uniform distribution in simplex 568
uniform distribution in triangle 569
uniform distribution in unit circle 556
properties of 234
rejection method for 233
relation to Cauchy distribution 234
squeeze method for 233
uniform distribution on 3d hypersphere
generator for 241
uniform distribution on 4d hypersphere
generator for 241
uniform distribution on a compact set 368
uniform distribution on a convex set 371
uniform distribution on a star 243
uniform distribution on convex polytope 568
uniform distribution on hypersphere
incremental method for 243
normal random vector method for 230
properties of 227
rejection method for 231
spacings method for 242
uniform spacings method for 231
uniform distribution on unit circle
efficient rejection method for 235
uniform distribution 732
as a beta distribution 428
as an NBUE distribution 742
as the projection of a radially symmetric random vector 230
characteristic function of 708
definition 7
distribution of midrange 24
distribution of products 24
distribution of ratio of maxima 26
distribution of sum 21
in and on circle 233
mixtures of 16
properties 25
sum of independent random variables 144
uniform line density 572
uniform order statistics method
for beta distribution 431
uniform order statistics 636
exponential spacings method for 214
relation to beta distribution 431
sorting method for 214
uniform spacings method for 214
uniform Poisson process
on unit circle 250
uniform scale mixture 687 688
uniform spacings method
for exponential distribution 394
for uniform distribution on hypersphere 231
for uniform order statistics 214
uniform spacings 207
properties of 208 210 212
relation to Dirichlet distribution 593
relation to exponential distribution 208
uniform sum 732
density of 732 733
unimodal density
grid method for 377
unimodal distribution 172 687 707
inequalities for 173 494
matched moment generator for 691
rectangular decomposition of 734
universal rejection method for 495
unit sphere
volume of 226
universal generator
a la Letac 65
universal method 286
for beta distribution 432
universal rejection method
analysis of 317
for binomial distribution 495
for convex densities 313
for discrete distribution 497
for generalized gaussian distribution 324
for hypergeometric distribution 545
for Lipschitz densities 323
for log-concave densities 301 325
for monotone densities 312 316 317
for residual life density 330
for unimodal distribution 495
Vaduva's gamma generator 130 424
analysis of 131
Vaduva's rejection method 48
Vaduva, I. 47 130 404 415 419 420 424
variance reduction 580
variance 5
Vaucher, J.G. 737 743 744 746
very smooth densities
series method for 700
Vitter, J.S. 621 631 635 638
volume
of unit sphere 226
von Mises distribution 473
inequalities for 474
rejection method for 473 476
von Mises's statistic 168
von Mises, R. 685 686
von Neumann's exponential generator 125 182
analysis of 126
von Neumann, J. 121 126 380 391
Wainwright, T.E. 372
waiting time method 71
waiting time 749 759
Wald's distribution 148
Wald's equation 50
application of 54
second moment analog 63
Walker, A.J. 107 369
Wallace, C.S. 380
Walls, L.A. 203
Warnock, T. 232
Wasan, L.T. 150
Watson's statistic 168
Watson, G.N. 161 377 435 489 490 491 508 552
Watson, G.S. 168
Weibull distribution 414
as a DHR distribution 267
as an IHR distribution 343
inversion method for 262
log-concavity of 287
order statistics of 220
properties of 424
relation to exponential distribution 414
relation to extreme value distribution 414
relation to multivariate Burr distribution 558
weighted sampling without replacement 619
Welch, W.J. 606
Wheeden, R.L. 217
Wheeling, R.F. 243
Whitt, W. 574 580 586 588
Whittaker, E.T. 161 377 435 489 490 491 508 552
Whittaker, J. 416 432 439 440 443
Whitworth's formula 213
Whitworth, W.A. 213
Widder, D.V. 682 683 685 694
Wilf, H.S. 617 618 642 645 661 666
Wilks, S.S. 594
Willis, J.R. 372
Wilson, E.B. 136
Wilson-Hilferty approximation 136
Wilson-Hilferty transformation 137 406
Wong, C.K. 619
Wormald, N.C. 671 672
wrapped Cauchy density 473
inversion method for 474
Wright, H. 733
Wyman, F.P. 746
Yakowitz, S.J. 4
Yao, A.C. 768 771 774 777 779 781
Young's inequality 338
Yuen, C. 38 621 624 625 626
Yule distribution 553
Yule process 755
z distribution 329
as a normal scale mixture 330
generators for 330
relation to beta distribution 330
Zelen, M. 4
Zemach, C. 232
Zigangirov, K.S. 150
Zimmerman, S. 91
Zipf distribution 550
rejection method for 550
Zolotarev, V.M. 183 184 185 455 459
Zygmund, A. 217
