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