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.
Author(s): James E. Gentle
Edition: 2nd
Year: 2003
Language: English
Pages: 264
Cover Page......Page 1
Title Page......Page 4
ISBN 0387001786......Page 5
Preface......Page 8
Acknowledgments......Page 10
1 Simulating Random Numbers from a Uniform Distribution......Page 12
4 Transformations of Uniform Deviates: General Methods......Page 13
6 Generation of Random Samples, Permutations, and Stochastic Processes......Page 14
Appendixes, Bibliography, Indexes......Page 15
1 Simulating Random Numbers from a Uniform Distribution......Page 18
1.1 Uniform Integers and an Approximate Uniform Density......Page 22
1.2 Simple Linear Congruential Generators......Page 28
1.2.1 Structure in the Generated Numbers......Page 31
1.2.2 Tests of Simple Linear Congruential Generators......Page 37
1.2.3 Shuffling the Output Stream......Page 38
1.2.4 Generation of Substreams in Simple Linear Congruential Generators......Page 40
1.3 Computer Implementation of Simple Linear Congruential Generators......Page 44
1.3.1 Ensuring Exact Computations......Page 45
1.3.2 Restriction that the Output Be in the Open Interval (0,1)......Page 46
1.3.4 Vector Processors......Page 47
1.4 Other Linear Congruential Generators......Page 48
1.4.1 Multiple Recursive Generators......Page 49
1.4.2 Matrix Congruential Generators......Page 51
1.4.3 Add-with-Carry, Subtract-with-Borrow, and Multiply-with-Carry Generators......Page 52
1.5.1 Inversive Congruential Generators......Page 53
1.5.2 Other Nonlinear Congruential Generators......Page 54
1.6 Feedback Shift Register Generators......Page 55
1.6.1 Generalized Feedback Shift Registers and Variations......Page 57
1.7 Other Sources of Uniform Random Numbers......Page 60
1.7.1 Generators Based on Cellular Automata......Page 61
1.7.3 Other Recursive Generators......Page 62
1.8 Combining Generators......Page 63
1.9 Properties of Combined Generators......Page 65
1.10 Independent Streams and Parallel Random Number Generation......Page 68
1.10.2 Different Generators for Different Streams......Page 69
1.10.3 Quality of Parallel Random Number Streams......Page 70
1.11 Portability of Random Number Generators......Page 71
1.12 Summary......Page 72
Exercises......Page 73
2 Quality of Random Number Generators......Page 78
2.1 Properties of Random Numbers......Page 79
2.2.1 Measures Based on the Lattice Structure......Page 81
2.2.2 Differences in Frequencies and Probabilities......Page 84
2.2.3 Independence......Page 87
2.3.1 Statistical Goodness-of-Fit Tests......Page 88
2.3.3 Anecdotal Evidence......Page 103
2.5 Summary......Page 104
Exercises......Page 105
3.1 Low Discrepancy......Page 110
3.2.1 Halton Sequences......Page 111
3.2.2 Sobol’ Sequences......Page 113
3.2.4 Variations......Page 114
3.3 Further Comments......Page 115
Exercises......Page 117
4 Transformations of Uniform Deviates: General Methods......Page 118
4.1 Inverse CDF Method......Page 119
4.2 Decompositions of Distributions......Page 126
4.3 Transformations that Use More than One Uniform Deviate......Page 128
4.4 Multivariate Uniform Distributions with Nonuniform Marginals......Page 129
4.5 Acceptance/Rejection Methods......Page 130
4.6 Mixtures and Acceptance Methods......Page 142
4.7 Ratio-of-Uniforms Method......Page 146
4.8 Alias Method......Page 150
4.9 Use of the Characteristic Function......Page 153
4.10 Use of Stationary Distributions of Markov Chains......Page 154
4.12 Weighted Resampling......Page 166
4.13 Methods for Distributions with Certain Special Properties......Page 167
4.14 General Methods for Multivariate Distributions......Page 172
Exercises......Page 176
5 Simulating Random Numbers from Specific Distributions......Page 182
5.1 Modifications of Standard Distributions......Page 184
5.2 Some Specific Univariate Distributions......Page 187
5.2.1 Normal Distribution......Page 188
5.2.2 Exponential, Double Exponential, and Exponential Power Distributions......Page 193
5.2.3 Gamma Distribution......Page 195
5.2.4 Beta Distribution......Page 200
5.2.5 Chi-Squared, Student’s t, and F Distributions......Page 201
5.2.6 Weibull Distribution......Page 203
5.2.7 Binomial Distribution......Page 204
5.2.9 Negative Binomial and Geometric Distributions......Page 205
5.2.10 Hypergeometric Distribution......Page 206
5.2.11 Logarithmic Distribution......Page 207
5.2.12 Other Specific Univariate Distributions......Page 208
5.2.13 General Families of Univariate Distributions......Page 210
5.3.1 Multivariate Normal Distribution......Page 214
5.3.3 Correlation Matrices and Variance-Covariance Matrices......Page 215
5.3.4 Points on a Sphere......Page 218
5.3.5 Two-Way Tables......Page 219
5.3.6 Other Specific Multivariate Distributions......Page 220
5.3.7 Families of Multivariate Distributions......Page 225
5.4 Data-Based Random Number Generation......Page 227
5.5 Geometric Objects......Page 229
Exercises......Page 230
6.1 Random Samples......Page 234
6.3 Limitations of Random Number Generators......Page 237
6.4.1 Order Statistics......Page 238
6.4.2 Censored Data......Page 240
6.5.1 Markov Process......Page 241
6.5.2 Nonhomogeneous Poisson Process......Page 242
6.5.3 Other Time Series Models......Page 243
Exercises......Page 244
7 Monte Carlo Methods......Page 246
7.1 Evaluating an Integral......Page 247
7.2 Sequential Monte Carlo Methods......Page 250
7.3 Experimental Error in Monte Carlo Methods......Page 252
7.4 Variance of Monte Carlo Estimators......Page 253
7.5 Variance Reduction......Page 256
7.5.1 Analytic Reduction......Page 257
7.5.2 Stratified Sampling and Importance Sampling......Page 258
7.5.3 Use of Covariates......Page 262
7.5.5 Stratification in Higher Dimensions: Latin Hypercube Sampling......Page 265
7.6 The Distribution of a Simulated Statistic......Page 266
7.7 Computational Statistics......Page 267
7.7.1 Monte Carlo Methods for Inference......Page 268
7.7.2 Bootstrap Methods......Page 269
7.7.3 Evaluating a Posterior Distribution......Page 272
7.8 Computer Experiments......Page 273
7.9 Computational Physics......Page 274
7.10 Computational Finance......Page 278
Exercises......Page 288
8 Software for Random Number Generation......Page 300
8.1 The User Interface for Random Number Generators......Page 302
8.3 Random Number Generation in Programming Languages......Page 303
8.4 Random Number Generation in IMSL Libraries......Page 305
8.5 Random Number Generation in S-Plus and R......Page 308
Exercises......Page 312
9 Monte Carlo Studies in Statistics......Page 314
9.1 Simulation as an Experiment......Page 315
9.2 Reporting Simulation Experiments......Page 317
9.3 An Example......Page 318
Exercises......Page 327
A: Notation and Definitions......Page 330
B: Solutions and Hints for Selected Exercises......Page 340
Bibliography......Page 348
Literature in Computational Statistics......Page 349
World Wide Web, News Groups, List Servers, and Bulletin Boards......Page 351
References to the Literature......Page 353
C......Page 388
G......Page 389
L......Page 390
P......Page 391
T......Page 392
Z......Page 393
C......Page 394
I......Page 395
N......Page 396
S......Page 397
Z......Page 398
