Preface to the Second Edition .................................. IX
Preface to the First Edition ................................... XI
1. What is Monte Carlo? ......................................... 1
1.1. Introduction ........................................... 1
1.2. Topics to be Covered ................................... 3
1.3. A Short History of Monte Carlo ......................... 4
References 5
2. A Bit of Probability ......................................... 7
2.1. Random Events .......................................... 7
2.2. Random Variables ....................................... 9
2.2.1 The Binomial Distribution ....................... 12
2.2.2 The Geometric Distribution ...................... 13
2.2.3 The Poisson Distribution ........................ 14
2.3. Continuous Random Variables ........................... 14
2.4. Expectations of Continuous Random Variables ........... 16
2.5. Bivariate Continuous Random Distributions ............. 19
2.6. Sums of Random Variables: Monte Carlo Quadrature ...... 21
2.7. Distribution of the Mean of a Random Variable:
A Fundamental Theorem ................................. 22
2.8. Distribution of Sums of Independent Random Variables .. 25
2.9. Monte Carlo Integration ............................... 28
2.10. Monte Carlo Estimators ................................ 31
References .................................................. 34
Further Reading ............................................. 34
Elementary .................................................. 34
More Advanced ............................................... 34
3. Sampling Random Variables ................................... 35
3.1. Transformation of Random Variables .................... 36
3.2. Numerical Transformation .............................. 42
3.3. Sampling Discrete Distributions ....................... 43
3.4. Composition of Random Variables ....................... 47
3.4.1. Sampling the Sum of Two Uniform Random
Variables ...................................... 47
3.4.2. Sampling a Random Variable Raised to a Power ... 48
3.4.3. Sampling the Distribution f(z) = z(l — z) ...... 50
3.4.4. Sampling the Sum of Several Arbitrary
Distributions .................................. 50
3.5. Rejection Techniques .................................. 53
3.5.1. Sampling a Singular pdf Using Rejection ........ 57
3.5.2. Sampling the Sine and Cosine of an Angle ....... 57
3.5.3. Kahn's Rejection Technique for a Gaussian ...... 59
3.5.4. Marsaglia et al. Method for Sampling a
Gaussian ....................................... 60
3.6. Multivariate Distributions ............................ 61
3.6.1 Sampling a Brownian Bridge ...................... 62
3.7. The M(RT)2 Algorithm .................................. 64
3.8. Application of M(RT)2 ................................. 72
3.9. Testing Sampling Methods .............................. 74
References .................................................. 75
Further Reading ............................................. 76
4. Monte Carlo Evaluation of Finite-Dimensional Integrals ...... 77
4.1. Importance Sampling ................................... 79
4.2. The Use of Expected Values to Reduce Variance ......... 88
4.3. Correlation Methods for Variance Reduction ............ 91
4.3.1. Antithetic Variates ............................ 93
4.3.2. Stratification Methods ......................... 95
4.4. Adaptive Monte Carlo Methods .......................... 98
4.5. Quasi-Monte Carlo .................................... 100
4.5.1. Low-Discrepancy Sequences ..................... 101
4.5.2. Error Estimation for Quasi-Monte Carlo
Quadrature .................................... 103
4.5.3. Applications of Quasi-Monte Carlo ............. 104
4.6. Comparison of Monte Carlo Integration, Quasi-Monte
Carlo and Numerical Quadrature ....................... 104
References ................................................. 105
Further Reading ............................................ 106
5. Random Walks, Integral Equations, and Variance Reduction ... 107
5.1. Properties of Discrete Markov Chains ................. 107
5.1.1. Estimators and Markov Processes ............... 109
5.2. Applications Using Markov Chains ..................... 110
5.2.1. Simulated Annealing ........................... 111
5.2.2. Genetic Algorithms ............................ 112
5.2.3. Poisson Processes and Continuous Time Markov
Chains ........................................ 114
5.2.4. Brownian Motion ............................... 122
5.3. Integral Equations ................................... 124
5.3.1. Radiation Transport and Random Walks .......... 124
5.3.2. The Boltzmann Equation ........................ 126
5.4. Variance Reduction ................................... 127
5.4.1. Importance Sampling of Integral Equations ..... 127
References ................................................. 129
Further Reading ............................................ 130
6. Simulations of Stochastic Systems: Radiation Transport ..... 131
6.1. Radiation Transport as a Stochastic Process .......... 131
6.2. Characterization of the Source ....................... 135
6.3. Tracing a Path ....................................... 136
6.4. Modeling Collision Events ............................ 140
6.5. The Boltzmann Equation and Zero Variance
Calculations ......................................... 142
6.5.1. Radiation Impinging on a Slab ................. 144
References ................................................. 147
Further Reading ............................................ 147
7. Statistical Physics ........................................ 149
7.1. Classical Systems .................................... 149
7.1.1. The Hard Sphere Liquid ........................ 151
7.1.2. Molecular Dynamics ............................ 153
7.1.3. Kinetic Monte Carlo ........................... 154
7.1.4. The Ising Model ............................... 155
References ................................................. 156
Further Reading ............................................ 157
8. Quantum Monte Carlo ........................................ 159
8.1. Variational Monte Carlo .............................. 160
8.2. Green's Function Monte Carlo ......................... 161
8.2.1. Monte Carlo Solution of Homogeneous
Integral Equations ............................ 162
8.2.2. The Schrodinger Equation in Integral Form ..... 163
8.2.3. Green's Functions from Random Walks ........... 165
8.2.4. The Importance Sampling Transformation ........ 167
8.3. Diffusion Monte Carlo ................................ 170
8.4. Path Integral Monte Carlo ............................ 172
8.5. Quantum Chromodynamics ............................... 175
References ................................................. 176
Further Reading ............................................ 178
9. Pseudorandom Numbers ....................................... 179
9.1. Major Classes of prn Generators ...................... 180
9.1.1. Linear Recurrence Methods ..................... 180
9.1.2. Tausworthe or Feedback Shift Register
Generators .................................... 182
9.1.3. Nonlinear Recursive Generators ................ 183
9.1.4. Combination Generators ........................ 184
9.2. Statistical Testing of prng's ........................ 185
9.2.1. Theoretical Tests ............................. 185
9.2.2. Empirical Tests ............................... 286
9.3. Comparing Two Pseudorandom Number Generators ......... 187
9.3.1. A Multiplicative Congruential Generator
Proposed for 32-bit Computers ................. 187
9.3.2. A Bad Random Number Generator ................. 189
9.4. Pseudorandom Number Generation on Parallel
Computers ............................................ 192
9.4.1. Splitting and Leapfrogging .................... 193
9.4.2. Parallel Sequences from Combination
Generators .................................... 193
9.4.3. Reproducibility and Lehmer Trees .............. 194
9.4.4. SPRNG: A Library of Pseudorandom Number
Generators .................................... 195
9.5. Summary .............................................. 195
References .................................................... 196
Index ......................................................... 199
|
