|
Contents
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(1 − 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 Schr¨odinger 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 186
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
|