Preface to the Second Edition
Preface to the First Edition
Acknowledgments
Contents
Notations
1 Introduction to Monte Carlo Methods
1.1 How Can Random Numbers Solve Problems?
1.1.1 History of the Monte Carlo Method
1.1.2 Histogramming Simulation Results
1.1.3 Sample Paths
1.2 Some Basic Probability
1.2.1 Events and Random Variables
1.2.2 Discrete and Continuous Random Variables
1.2.3 The Probability Density Function
1.2.4 Expected Values
1.2.5 Conditional Probabilities
1.2.6 Bayes' Formula
1.2.7 Joint Probability Distributions
1.3 Random Number Generation
1.3.1 Requirements for a Random Number Generator (RNG)
1.3.2 Middle-Square and Other Middle-Digit Techniques
1.3.3 Linear Congruential Random Number Generators
1.4 Some Applications
2 Some Probability Distributions and Their Uses
2.1 CDF Inversion–Discrete Case Example: Bernoulli Trials
2.1.1 Two-Outcome CDF Inversion
2.1.2 Multiple-Outcome Distributions
2.2 Walker's Alias Method Example: Roulette Wheel Selection
2.3 Probability Simulation Example: The Binomial Distribution
2.3.1 Sampling from the Binomial
2.4 Another Simulation Example: The Poisson Distribution
2.4.1 Sampling from the Poisson Distribution by Simulation
2.5 CDF Inversion, Continuous Case Example: The Exponential Distribution
2.5.1 Inverting the CDF–The Canonical Method for the Exponential
2.5.2 Discrete Event Simulation
2.5.3 Transforming Random Variables, the Cauchy Distribution
2.6 The Central Limit Theorem and the Normal Distribution
2.6.1 Sampling from the Normal Distribution
2.6.2 Approximate Sampling via the Central Limit Theorem
2.6.3 Error Estimates for Monte Carlo Simulations
2.7 Gibrat's Law and the Lognormal Distribution
2.8 Rejection Sampling Example: The Beta Distribution
2.8.1 The Beta Distribution
2.8.2 Sampling from an Unbounded Beta Distribution
2.9 Composite Distributions: Sampling the Gamma Distribution
2.9.1 The Gamma Distribution
2.9.2 Sampling from upper G left parenthesis alpha comma 1 right parenthesisG(α,1)
2.10 Sampling from a Joint Distribution
3 Markov Chain Monte Carlo
3.1 Discrete Markov Chains
3.1.1 Random Walk on a Graph
3.1.2 Matrix Representation of a Chain
3.2 Markov Chain Monte Carlo Sampling— The Metropolis Algorithm
3.2.1 Some Examples
3.2.2 Why Does the Metropolis Algorithm Work?
3.3 MCMC Sampling and the Ergodic Theorem
3.4 Statistical Mechanics
3.5 Ising Model and the Metropolis Algorithm
3.6 The Metropolis–Hastings Algorithm
3.7 Counting
3.8 Some Applications of MCMC
3.8.1 Shuffling with Constraints
3.8.2 Coupling from the Past
4 Random Walks
4.1 1d Random Walk
4.2 Diffusion
4.3 Brownian Motion
4.4 Random Walk Applications I
4.4.1 Options Pricing in Finance
4.4.2 Self-Avoiding Walks
4.5 Gambler's Ruin
4.5.1 Gambling Schemes
4.6 Random Walk Applications II—Kelly's Criterion in Finance
4.6.1 The Simple Kelly Game
4.6.2 The Simple Game with Catastrophic Loss
4.6.3 Option Trading Application I
4.6.4 Option Trading Application II
4.7 Random Walks and Electrical Networks
4.7.1 Markov Chain Solution for Voltages
4.7.2 The Fundamental Matrix and Expected Hitting Times
4.8 The Kinetic Monte Carlo Method
5 Optimization by Monte Carlo Methods
5.1 Simulated Annealing
5.2 Application of SA to the Traveling Salesman Problem
5.3 Genetic Algorithms
5.4 An Application of GA to Function Maximization
5.5 An Application of GA to the Permanent Problem
6 More on Markov Chain Monte Carlo
6.1 Bayesian Inference
6.1.1 Pymc3
6.2 Gibbs Sampling
6.3 Monte Carlo Integration: Quadrature
6.3.1 Variance Reduction
6.3.2 MCMC in Quadrature
6.4 Round-off Error
Appendix A Generating Uniform Random Numbers
A.1 Multiple Stored Value Random Number Generation
A.1.1 Fibonacci Generators
A.1.2 Finite Field RNG
A.2 Mersenne Twister
A.3 Testing for Non-randomness
A.3.1 Chi-Square Test
A.3.2 Kolmogorov–Smirnov Test
Appendix B Perron–Frobenius Theorem
B.1 Proof of Perron–Frobenius
Appendix C Kelly Allocation for Correlated Investments
C.1 Kelly Allocation for Correlated Investments
C.2 Genetic Algorithm Code for the Kelly Problem
Appendix D Donsker's Theorem
D.1 Donsker's Theorem
Appendix E Projects
Appendix References
Index
Code Index