by
James E. Gentle
Table of Contents
1 Simulating Random Numbers from a Uniform Distribution ... 1
1.1 Linear Congruential Generators ... 6
- 1.1.1 Structure in the Generated Numbers ... 8
- 1.1.2 Skipping Ahead in Linear Congruential Generators ... 14
- 1.1.3 Shuffling the Output Stream ... 16
- 1.1.4 Tests of Linear Congruential Generators ... 17
- 1.1.5 Computer Implementation of Linear Congruential Generators
... 19
1.2 Combining Generators ... 22
1.3 Other Congruential Generators ... 24
- 1.3.1 Multiple Recursive Generators ... 24
- 1.3.2 Matrix Congruential Generators ... 25
- 1.3.3 Lagged Fibonacci ... 26
- 1.3.4 Wichmann/Hill Generator ... 26
- 1.3.5 L'Ecuyer Combined Generator ... 27
- 1.3.6 Add-with-Carry and Subtract-with-Borrow Generators ... 27
- 1.3.7 Inversive Congruential Generators ... 28
- 1.3.8 Other Nonlinear Congruential Generators ... 29
1.4 Feedback Shift Register Generators ... 29
- 1.4.1 Generalized Feedback Shift Registers and Variations ... 31
- 1.4.2 Skipping Ahead in GFSR Generators ... 33
1.5 Other Sources of Uniform Random Numbers ... 33
- 1.5.1 Generators Based on Chaotic Systems ... 34
- 1.5.2 Tables of Random Numbers ... 34
1.6 Portable Random Number Generators ... 34
1.7 Independent Streams and Parallel Random Number Generation ... 35
- 1.7.1 Lehmer Trees ... 36
- 1.7.2 Combination Generators ... 37
- 1.7.3 Monte Carlo on Parallel Processors ... 37
Exercises ... 37
2 Transformations of Uniform Deviates: General Methods ... 41
2.1 Inverse CDF Method ... 42
2.2 Acceptance/Rejection Methods ... 47
2.3 Mixtures of Distributions ... 56
2.4 Mixtures and Acceptance Methods ... 57
2.5 Ratio of Uniforms Method ... 59
2.6 Alias Method ... 62
2.7 Use of Stationary Distributions of Markov Chains ... 65
2.8 Weighted Resampling ... 73
2.9 Methods for Distributions with Certain Special Properties ... 74
2.10 General Methods for Multivariate Distributions ... 78
2.11 Generating Samples from a Given Distribution ... 82
Exercises ... 82
3 Simulating Random Numbers from Specific Distributions ... 87
3.1 Some Specific Univariate Distributions ... 89
- 3.1.1 Standard Distributions and Folded Distributions ... 89
- 3.1.2 Normal Distribution ... 90
- 3.1.3 Exponential, Double Exponential, and Exponential Power Distributions ... 94
- 3.1.4 Gamma Distribution ... 95
- 3.1.5 Beta Distribution ... 99
- 3.1.6 Student's $t$, Chi-Squared, and $F$ Distributions ... 99
- 3.1.7 Weibull Distribution ... 101
- 3.1.8 Binomial Distribution ... 102
- 3.1.9 Poisson Distribution ... 102
- 3.1.10 Negative Binomial and Geometric Distributions ... 103
- 3.1.11 Hypergeometric Distribution ... 103
- 3.1.12 Logarithmic Distribution ... 104
- 3.1.13 Other Specific Univariate Distributions ... 104
- 3.1.14 General Families of Univariate Distributions ... 106
3.2 Some Specific Multivariate Distributions ... 107
- 3.2.1 Multivariate Normal Distribution ... 107
- 3.2.2 Multinomial Distribution ... 108
- 3.2.3 Correlation Matrices and Variance-Covariance Matrices ... 109
- 3.2.4 Points on a Sphere ... 111
- 3.2.5 Two-Way Tables ... 112
- 3.2.6 Other Specific Multivariate Distributions ... 113
3.3 General Multivariate Distributions ... 114
- 3.3.1 Distributions with Specified Correlations ... 114
- 3.3.2 Data-Based Random Number Generation ... 117
3.4 Geometric Objects ... 119
Exercises ... 120
4 Generation of Random Samples and Permutations ... 123
4.1 Random Samples ... 123
4.2 Permutations ... 126
4.3 Generation of Nonindependent Samples ... 127
- 4.3.1 Order Statistics ... 127
- 4.3.2 Nonindependent Sequences: Nonhomogeneous Poisson Process ... 128
- 4.3.3 Censored Data ... 129
Exercises ... 130
5 Monte Carlo Methods ... 133
5.1 Evaluating an Integral ... 133
5.2 Variance of Monte Carlo Estimators ... 135
5.3 Variance Reduction ... 137
- 5.3.1 Analytic Reduction ... 137
- 5.3.2 Antithetic Variates ... 138
- 5.3.3 Importance and Stratified Sampling ... 139
- 5.3.4 Common Variates ... 139
- 5.3.5 Constrained Sampling ... 140
- 5.3.6 Latin Hypercube Sampling ... 140
5.4 Computer Experiments ... 141
5.5 Computational Statistics ... 143
- 5.5.1 Monte Carlo Tests ... 143
- 5.5.2 Bootstrap Methods ... 144
5.6 Evaluating a Posterior Distribution ... 147
Exercises ... 148
6 Quality of Random Number Generators ... 153
6.1 Analysis of the Algorithm ... 153
6.2 Empirical Assessments ... 156
- 6.2.1 Statistical Tests ... 156
- 6.2.2 Annecdotal Evidence ... 160
6.3 Quasirandom Numbers ... 161
- 6.3.1 Halton Sequences ... 162
- 6.3.2 Sobol' Sequences ... 163
- 6.3.3 Comparisons ... 164
- 6.3.4 Variations ... 165
- 6.3.5 Some Examples of Applications ... 165
- 6.3.6 Computations ... 165
6.4 Programming Issues ... 165
Exercises ... 166
7 Software for Random Number Generation ... 169
7.1 The User Interface for Random Number Generators ... 170
7.2 Controlling the Seeds in Monte Carlo Studies ... 171
7.3 Random Number Generation in IMSL Libraries ... 171
7.4 Random Number Generation in S-Plus ... 174
Exercises ... 177
8 Monte Carlo Studies in Statistics ... 179
8.1 Simulation as an Experiment ... 180
8.2 Reporting Simulation Experiments ... 182
8.3 An Example ... 182
Exercises ... 192
Appendix A: Notation and Definitions ... 195
Appendix B: Solutions and Hints for Selected Exercises ... 201
Bibliography ... 205
The Literature in the Computational Statistics ... 206
World Wide Web, News Groups, List Servers, and Bulletin Boards
... 208
The References ... 210
Author Index ... 235
Subject Index ... 241