by
James E. Gentle
Table of Contents
1 Simulating Random Numbers from a Uniform Distribution ... 1
1.1 Simple Linear Congruential Generators ... 8
- 1.1.1 Structure in the Generated Numbers ... 11
- 1.1.2 Tests of Linear Congruential Generators ... 16
- 1.1.3 Skipping Ahead in Linear Congruential Generators ... 18
- 1.1.4 Shuffling the Output Stream ... 20
1.2 Computer Implementation of Linear Congruential Generators
... 22
- 1.2.1 Ensuring Exact Computations ... 23
- 1.2.2 Restriction that the Output Be in the Open Interval ... 24
- 1.2.3 Efficiency Considerations ... 24
- 1.2.4 Vector Processors ... 25
1.3 Other Congruential Generators ... 26
- 1.3.1 Multiple Recursive Generators ... 26
- 1.3.2 Lagged Fibonacci ... 26
- 1.3.3 Matrix Congruential Generators ... 28
- 1.3.4 Add-with-Carry and Subtract-with-Borrow Generators ... 29
- 1.3.5 Inversive Congruential Generators ... 29
- 1.3.6 Other Nonlinear Congruential Generators ... 30
1.4 Feedback Shift Register Generators ... 31
- 1.4.1 Generalized Feedback Shift Registers and Variations ... 33
- 1.4.2 Skipping Ahead in GFSR Generators ... 36
1.5 Other Sources of Uniform Random Numbers ... 36
- 1.5.1 Generators Based on Cellular Automata ... 36
- 1.5.2 Generators Based on Chaotic Systems ... 37
- 1.5.3 Other Recursive Generators ... 37
- 1.5.4 Tables of Random Numbers ... 38
1.6 Portable Random Number Generators ... 38
1.7 Combining Generators ... 40
1.8 Properties of Combined Generators ... 41
1.9 Independent Streams and Parallel Random Number Generation ... 44
- 1.9.1 Lehmer Trees ... 44
- 1.9.2 Combination Generators ... 45
- 1.9.3 Monte Carlo on Parallel Processors ... 46
1.10 Summary ... 46
Exercises ... 46
2 Quality of Random Number Generators ... 51
2.1 Properties of Random Numbers ... 52
2.2 Measures of Lack of Fit ... 54
2.3 Empirical Assessments ... 57
- 2.3.1 Statistical Goodness of Fit Tests ... 57
- 2.3.2 Comparisons of Simulated Results with Statistical Models ... 65
- 2.3.2 Annecdotal Evidence ... 66
- 2.3.1 Tests of Random Number Generators Used in Parallel ... 66
2.4 Programming Issues ... 67
2.5 Summary ... 67
Exercises ... 68
3 Quasirandom Numbers ... 71
3.1 Low Discrepancy ... 71
3.2 Types of Sequences ... 72
- 3.2.1 Halton Sequences ... 72
- 3.2.2 Sobol' Sequences ... 73
- 3.2.3 Comparisons ... 74
- 3.2.4 Variations ... 75
- 3.2.5 Computations ... 75
3.3 Applications and Comparisons... 75
Exercises ... 76
4 Transformations of Uniform Deviates: General Methods ... 77
4.1 Inverse CDF Method ... 78
4.2 Transformations That Use More Than One Deivate ... 85
4.3 Mixtures of Distributions ... 86
4.4 Acceptance/Rejection Methods ... 87
4.5 Mixtures and Acceptance Methods ... 98
4.6 Ratio of Uniforms Method ... 101
4.7 Alias Method ... 104
4.8 Use of Characteristic Functions ... 107
4.9 Use of Stationary Distributions of Markov Chains ... 108
4.10 Use of Conditional Distributions ... 117
4.11 Weighted Resampling ... 117
4.12 Methods for Distributions with Certain Special Properties ... 118
4.13 General Methods for Multivariate Distributions ... 122
4.14 Generating Samples from a Given Distribution ... 127
Exercises ... 127
5 Simulating Random Numbers from Specific Distributions ... 131
5.1 Modifications of Standard Distributions ... 133
5.2 Some Specific Univariate Distributions ... 135
- 5.2.1 Normal Distribution ... 136
- 5.2.2 Exponential, Double Exponential, and Exponential Power Distributions ... 141
- 5.2.3 Gamma Distribution ... 142
- 5.2.4 Beta Distribution ... 147
- 5.2.5 Student's t, Chi-Squared, and F Distributions ... 148
- 5.2.6 Weibull Distribution ... 150
- 5.2.7 Binomial Distribution ... 151
- 5.2.8 Poisson Distribution ... 152
- 5.2.9 Negative Binomial and Geometric Distributions ... 152
- 5.2.10 Hypergeometric Distribution ... 153
- 5.2.11 Logarithmic Distribution ... 154
- 5.2.12 Other Specific Univariate Distributions ... 154
- 5.2.13 General Families of Univariate Distributions ... 157
5.3 Some Specific Multivariate Distributions ... 159
- 5.3.1 Multivariate Normal Distribution ... 160
- 5.3.2 Multinomial Distribution ... 161
- 5.3.3 Correlation Matrices and Variance-Covariance Matrices ... 161
- 5.3.4 Points on a Sphere ... 164
- 5.3.5 Two-Way Tables ... 165
- 5.3.6 Other Specific Multivariate Distributions ... 166
5.4 General Multivariate Distributions ... 171
- 5.4.1 Distributions with Specified Correlations ... 171
- 5.4.2 Data-Based Random Number Generation ... 172
5.5 Geometric Objects ... 174
Exercises ... 174
6 Generation of Random Samples, Permutations and Stochastic Processes... 177
6.1 Random Samples ... 177
6.2 Permutations ... 180
6.3 Limitations of Random Number Generators ... 180
6.4 Generation of Nonindependent Samples ... 181
- 6.4.1 Order Statistics ... 181
- 6.4.3 Censored Data ... 183
6.5 Generation of Nonindependent Sequences ... 184
- 6.5.1 Markov Process ... 184
- 6.5.2 Nonhomogeneous Poisson Process ... 185
- 6.5.3 Autoregressive and Moving Average Time Series Models ... 186
- 6.5.4 State Space Models of Multiple Series ... 186
Exercises ... 186
7 Monte Carlo Methods ... 189
7.1 Evaluating an Integral ... 190
7.2 Sequential Monte Carlo Methods ... 192
7.3 Experimental Error in Monte Carlo Methods ... 192
7.4 Variance of Monte Carlo Estimators ... 194
7.5 Variance Reduction ... 196
- 7.5.1 Analytic Reduction ... 197
- 7.5.2 Stratified and Importance Sampling ... 197
- 7.5.3 Use of Covariates ... 199
- 7.5.4 Constrained Sampling ... 202
- 7.5.5 Latin Hypercube Sampling ... 202
7.6 Computational Statistics ... 203
- 7.6.1 Monte Carlo Methods for Inference ... 204
- 7.6.2 Bootstrap Methods ... 205
- 7.6.3 Evaluating a Posterior Distribution ... 208
7.7 Computer Experiments ... 209
7.8 Computational Physics ... 210
7.9 Computational Finance ... 213
Exercises ... 224
8 Software for Random Number Generation ... 231
7.1 The User Interface for Random Number Generators ... 233
7.2 Controlling the Seeds in Monte Carlo Studies ... 234
7.3 Random Number Generation in Programming Languages ... 234
7.4 Random Number Generation in IMSL Libraries ... 235
7.5 Random Number Generation in S-Plus and R... 238
Exercises ... 242
9 Monte Carlo Studies in Statistics ... 245
9.1 Simulation as an Experiment ... 246
9.2 Reporting Simulation Experiments ... 248
9.3 An Example ... 248
Exercises ... 258
Appendix A: Notation and Definitions ... 261
Appendix B: Solutions and Hints for Selected Exercises ... 273
Bibliography ... 279
The Literature in the Computational Statistics ... 280
World Wide Web, News Groups, List Servers, and Bulletin Boards
... 282
The References ... 286
Author Index ... 319
Subject Index ... 325