Random Number Generation and Monte Carlo Methods (Statistics and Computing)
by James E. Gentle (Author)
Monte Carlo simulation has become one of the most important tools in all fields of science. Simulation methodology relies on a good source of numbers that appear to be random. These "pseudorandom" numbers must pass statistical tests just as random samples would. Methods for producing pseudorandom numbers and transforming those numbers to simulate samples from various distributions are among the most important topics in statistical computing. This book surveys techniques of random number generation and the use of random numbers in Monte Carlo simulation. The book covers basic principles, as well as newer methods such as parallel random number generation, nonlinear congruential generators, quasi Monte Carlo methods, and Markov chain Monte Carlo. The best methods for generating random variates from the standard distributions are presented, but also general techniques useful in more complicated models and in novel settings are described. The emphasis throughout the book is on practical methods that work well in current computing environments. The book includes exercises and can be used as a test or supplementary text for various courses in modern statistics. It could serve as the primary test for a specialized course in statistical computing, or as a supplementary text for a course in computational statistics and other areas of modern statistics that rely on simulation. The book, which covers recent developments in the field, could also serve as a useful reference for practitioners. Although some familiarity with probability and statistics is assumed, the book is accessible to a broad audience. The second edition is approximately 50% longer than the first edition. It includes advances in methods for parallel random number generation, universal methods for generation of nonuniform variates, perfect sampling, and software for random number generation. The material on testing of random number generators has been expanded to include a discussion of newer software for testing, as well as more discussion about the tests themselves. The second edition has more discussion of applications of Monte Carlo methods in various fields, including physics and computational finance. James Gentle is University Professor of Computational Statistics at George Mason University. During a thirteen-year hiatus from academic work before joining George Mason, he was director of research and design at the world's largest independent producer of Fortran and C general-purpose scientific software libraries. These libraries implement several random number generators, and are widely used in Monte Carlo studies. He is a Fellow of the American Statistical Association and a member of the International Statistical Institute. He has held several national offices in the American Statistical Association and has served as an associate editor for journals of the ASA as well as for other journals in statistics and computing. Recent activities include serving as program director of statistics at the National Science Foundation and as research fellow at the Bureau of Labor Statistics.
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