Contents
Preface vii
1 Simulating Random Numbers from a Uniform Distribution 1
1.1 Uniform Integers and an Approximate
Uniform Density . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Simple Linear Congruential Generators . . . . . . . . . . . . . . . 11
1.2.1 Structure in the Generated Numbers . . . . . . . . . . . . 14
1.2.2 Tests of Simple Linear Congruential Generators . . . . . . 20
1.2.3 Shuffling the Output Stream . . . . . . . . . . . . . . . . 21
1.2.4 Generation of Substreams in Simple Linear
Congruential Generators . . . . . . . . . . . . . . . . . . . 23
1.3 Computer Implementation of Simple Linear
Congruential Generators . . . . . . . . . . . . . . . . . . . . . . . 27
1.3.1 Ensuring Exact Computations . . . . . . . . . . . . . . . 28
1.3.2 Restriction that the Output Be in the
Open Interval (0,1) . . . . . . . . . . . . . . . . . . . . . 29
1.3.3 Efficiency Considerations . . . . . . . . . . . . . . . . . . 30
1.3.4 Vector Processors . . . . . . . . . . . . . . . . . . . . . . . 30
1.4 Other Linear Congruential Generators . . . . . . . . . . . . . . . 31
1.4.1 Multiple Recursive Generators . . . . . . . . . . . . . . . 32
1.4.2 Matrix Congruential Generators . . . . . . . . . . . . . . 34
1.4.3 Add-with-Carry, Subtract-with-Borrow, and
Multiply-with-Carry Generators . . . . . . . . . . . . . . 35
1.5 Nonlinear Congruential Generators . . . . . . . . . . . . . . . . . 36
1.5.1 Inversive Congruential Generators . . . . . . . . . . . . . 36
1.5.2 Other Nonlinear Congruential Generators . . . . . . . . . 37
1.6 Feedback Shift Register Generators . . . . . . . . . . . . . . . . . 38
1.6.1 Generalized Feedback Shift Registers and Variations . . . 40
1.6.2 Skipping Ahead in GFSR Generators . . . . . . . . . . . . 43
1.7 Other Sources of Uniform Random Numbers . . . . . . . . . . . 43
1.7.1 Generators Based on Cellular Automata . . . . . . . . . . 44
1.7.2 Generators Based on Chaotic Systems . . . . . . . . . . . 45
1.7.3 Other Recursive Generators . . . . . . . . . . . . . . . . . 45
1.7.4 Tables of Random Numbers . . . . . . . . . . . . . . . . . 46
1.8 Combining Generators . . . . . . . . . . . . . . . . . . . . . . . . 46
1.9 Properties of Combined Generators . . . . . . . . . . . . . . . . . 48
1.10 Independent Streams and Parallel Random Number Generation . 51
1.10.1 Skipping Ahead with Combination Generators . . . . . . 52
1.10.2 Different Generators for Different Streams . . . . . . . . . 52
1.10.3 Quality of Parallel Random Number Streams . . . . . . . 53
1.11 Portability of Random Number Generators . . . . . . . . . . . . 54
1.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2 Quality of Random Number Generators 61
2.1 Properties of Random Numbers . . . . . . . . . . . . . . . . . . . 62
2.2 Measures of Lack of Fit . . . . . . . . . . . . . . . . . . . . . . . 64
2.2.1 Measures Based on the Lattice Structure . . . . . . . . . 64
2.2.2 Differences in Frequencies and Probabilities . . . . . . . . 67
2.2.3 Independence . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3 Empirical Assessments . . . . . . . . . . . . . . . . . . . . . . . . 71
2.3.1 Statistical Goodness-of-Fit Tests . . . . . . . . . . . . . . 71
2.3.2 Comparisons of Simulated Results with
Statistical Models in Physics . . . . . . . . . . . . . . . . 86
2.3.3 Anecdotal Evidence . . . . . . . . . . . . . . . . . . . . . 86
2.3.4 Tests of Random Number Generators Used in Parallel . . 87
2.4 Programming Issues . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3 Quasirandom Numbers 93
3.1 Low Discrepancy . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.2 Types of Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.2.1 Halton Sequences . . . . . . . . . . . . . . . . . . . . . . . 94
3.2.2 Sobol’ Sequences . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.3 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.2.4 Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.2.5 Computations . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.3 Further Comments . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4 Transformations of Uniform Deviates: General Methods 101
4.1 Inverse CDF Method . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.2 Decompositions of Distributions . . . . . . . . . . . . . . . . . . . 109
4.3 Transformations that Use More than One Uniform Deviate . . . 111
4.4 Multivariate Uniform Distributions with Nonuniform Marginals . 112
4.5 Acceptance/Rejection Methods . . . . . . . . . . . . . . . . . . . 113
4.6 Mixtures and Acceptance Methods . . . . . . . . . . . . . . . . . 125
CONTENTS xiii
4.7 Ratio-of-Uniforms Method . . . . . . . . . . . . . . . . . . . . . . 129
4.8 Alias Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.9 Use of the Characteristic Function . . . . . . . . . . . . . . . . . 136
4.10 Use of Stationary Distributions of Markov Chains . . . . . . . . . 137
4.11 Use of Conditional Distributions . . . . . . . . . . . . . . . . . . 149
4.12 Weighted Resampling . . . . . . . . . . . . . . . . . . . . . . . . 149
4.13 Methods for Distributions with Certain Special Properties . . . . 150
4.14 General Methods for Multivariate Distributions . . . . . . . . . . 155
4.15 Generating Samples from a Given Distribution . . . . . . . . . . 159
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5 Simulating Random Numbers from Specific Distributions 165
5.1 Modifications of Standard Distributions . . . . . . . . . . . . . . 167
5.2 Some Specific Univariate Distributions . . . . . . . . . . . . . . . 170
5.2.1 Normal Distribution . . . . . . . . . . . . . . . . . . . . . 171
5.2.2 Exponential, Double Exponential, and Exponential
Power Distributions . . . . . . . . . . . . . . . . . . . . . 176
5.2.3 Gamma Distribution . . . . . . . . . . . . . . . . . . . . . 178
5.2.4 Beta Distribution . . . . . . . . . . . . . . . . . . . . . . . 183
5.2.5 Chi-Squared, Student’s t, and F Distributions . . . . . . . 184
5.2.6 Weibull Distribution . . . . . . . . . . . . . . . . . . . . . 186
5.2.7 Binomial Distribution . . . . . . . . . . . . . . . . . . . . 187
5.2.8 Poisson Distribution . . . . . . . . . . . . . . . . . . . . . 188
5.2.9 Negative Binomial and Geometric Distributions . . . . . . 188
5.2.10 Hypergeometric Distribution . . . . . . . . . . . . . . . . 189
5.2.11 Logarithmic Distribution . . . . . . . . . . . . . . . . . . 190
5.2.12 Other Specific Univariate Distributions . . . . . . . . . . 191
5.2.13 General Families of Univariate Distributions . . . . . . . . 193
5.3 Some Specific Multivariate Distributions . . . . . . . . . . . . . . 197
5.3.1 Multivariate Normal Distribution . . . . . . . . . . . . . . 197
5.3.2 Multinomial Distribution . . . . . . . . . . . . . . . . . . 198
5.3.3 Correlation Matrices and Variance-Covariance Matrices . 198
5.3.4 Points on a Sphere . . . . . . . . . . . . . . . . . . . . . . 201
5.3.5 Two-Way Tables . . . . . . . . . . . . . . . . . . . . . . . 202
5.3.6 Other Specific Multivariate Distributions . . . . . . . . . 203
5.3.7 Families of Multivariate Distributions . . . . . . . . . . . 208
5.4 Data-Based Random Number Generation . . . . . . . . . . . . . 210
5.5 Geometric Objects . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6 Generation of Random Samples, Permutations, and
Stochastic Processes 217
6.1 Random Samples . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.2 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.3 Limitations of Random Number Generators . . . . . . . . . . . . 220
xiv CONTENTS
6.4 Generation of Nonindependent Samples . . . . . . . . . . . . . . 221
6.4.1 Order Statistics . . . . . . . . . . . . . . . . . . . . . . . . 221
6.4.2 Censored Data . . . . . . . . . . . . . . . . . . . . . . . . 223
6.5 Generation of Nonindependent Sequences . . . . . . . . . . . . . 224
6.5.1 Markov Process . . . . . . . . . . . . . . . . . . . . . . . . 224
6.5.2 Nonhomogeneous Poisson Process . . . . . . . . . . . . . 225
6.5.3 Other Time Series Models . . . . . . . . . . . . . . . . . . 226
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7 Monte Carlo Methods 229
7.1 Evaluating an Integral . . . . . . . . . . . . . . . . . . . . . . . . 230
7.2 Sequential Monte Carlo Methods . . . . . . . . . . . . . . . . . . 233
7.3 Experimental Error in Monte Carlo Methods . . . . . . . . . . . 235
7.4 Variance of Monte Carlo Estimators . . . . . . . . . . . . . . . . 236
7.5 Variance Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.5.1 Analytic Reduction . . . . . . . . . . . . . . . . . . . . . . 240
7.5.2 Stratified Sampling and Importance Sampling . . . . . . . 241
7.5.3 Use of Covariates . . . . . . . . . . . . . . . . . . . . . . . 245
7.5.4 Constrained Sampling . . . . . . . . . . . . . . . . . . . . 248
7.5.5 Stratification in Higher Dimensions:
Latin Hypercube Sampling . . . . . . . . . . . . . . . . . 248
7.6 The Distribution of a Simulated Statistic . . . . . . . . . . . . . 249
7.7 Computational Statistics . . . . . . . . . . . . . . . . . . . . . . . 250
7.7.1 Monte Carlo Methods for Inference . . . . . . . . . . . . . 251
7.7.2 Bootstrap Methods . . . . . . . . . . . . . . . . . . . . . . 252
7.7.3 Evaluating a Posterior Distribution . . . . . . . . . . . . . 255
7.8 Computer Experiments . . . . . . . . . . . . . . . . . . . . . . . 256
7.9 Computational Physics . . . . . . . . . . . . . . . . . . . . . . . . 257
7.10 Computational Finance . . . . . . . . . . . . . . . . . . . . . . . 261
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
8 Software for Random Number Generation 283
8.1 The User Interface for Random Number Generators . . . . . . . 285
8.2 Controlling the Seeds in Monte Carlo Studies . . . . . . . . . . . 286
8.3 Random Number Generation in Programming Languages . . . . 286
8.4 Random Number Generation in IMSL Libraries . . . . . . . . . . 288
8.5 Random Number Generation in S-Plus and R . . . . . . . . . . . 291
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
9 Monte Carlo Studies in Statistics 297
9.1 Simulation as an Experiment . . . . . . . . . . . . . . . . . . . . 298
9.2 Reporting Simulation Experiments . . . . . . . . . . . . . . . . . 300
9.3 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
A Notation and Definitions 313
CONTENTS xv
B Solutions and Hints for Selected Exercises 323
Bibliography 331
Literature in Computational Statistics . . . . . . . . . . . . . . . . . . 332
World Wide Web, News Groups, List Servers, and Bulletin Boards . . 334
References for Software Packages . . . . . . . . . . . . . . . . . . . . . 336
References to the Literature . . . . . . . . . . . . . . . . . . . . . . . . 336
Author Index 371
Subject Index 377