Contents
1 Aims of Simulation 1
1.1 The Tools, 2
1.2 Models, 2
1.3 Simulation as Experimentation, 4
1.4 Simulation in Inference, 4
1.5 Examples, 5
1.6 Literature, 12
1.7 Convention, 12
Exercises, 13
2 Pseudo-Random Numbers 14
2.1 History and Philosophy, 14
2.2 Congruential Generators, 20
2.3 Shift-Register Generators, 26
2.4 Lattice Structure, 33
2.5 Shuffling and Testing, 42
2.6 Conclusions, 45
2.7 Proofs, 46
Exercises, 50
3 Random Variables 53
3.1 Simple Examples, 54
3.2 General Principles, 59
3.3 Discrete Distributions, 71
3.4 Continuous Distributions, 81
3.5 Recommendations, 91
Exercises, 92
x
CONTENTS
4 Stochastic Models
4.1 Order Statistics, 96
4.2 Multivariate Distributions, 98
4.3 Poisson Processes and Lifetimes, 100
4.4 Markov Processes, 104
4.5 Gaussian Processes, 105
4.6 Point Processes, 110
4.7 Metropolis' Method and Random Fields, 113
Exercises, 116
96
5 Variance Reduction
5.1 Monte-Carlo Integration, 119
5.2 Importance Sampling, 122
5.3 Control and Antithetic Variates, 123
5.4 Conditioning, 134
5.5 Experimental Design, 137
Exercises, 139
118
6 Output Analysis
6.1 The Initial Transient, 146
6.2 Batching, 150
6.3 Time-Series Methods, 155
6.4 Regenerative Simulation, 157
6.5 A Case Study, 161
Exercises, 169
142
7 Uses of Simulation
7.1 Statistical Inference, 171
7.2 Stochastic Methods in Optimization, 178
7.3 Systems of Linear Equations, 186
7.4 Quasi-Monte-Carlo Integration, 189
7.5 Sharpening Buffon's Needle, 193
Exercises, 198
170
References
200
CONTENTS Xl
Appendix A. Computer Systems 215
Appendix B. Computer Programs 217
B.1 Form a x b mod c, 217
B.2 Check Primitive Roots, 219
B.3 Lattice Constants for Congruential Generators, 220
B.4 Test GFSR Generators, 227
B.5 Normal Variates, 228
B.6 Exponential Variates, 230
B.7 Gamma Variates, 230
B.8 Discrete Distributions, 231
Index
235