Jochen Voss, School of Mathematics, University of Leeds, UK.

List of algorithms ix

Preface xi

Nomenclature xiii

1 Random number generation 1

1.1 Pseudo random number generators 2

1.1.1 The linear congruential generator 2

1.1.2 Quality of pseudo random number generators 4

1.1.3 Pseudo random number generators in practice 8

1.2 Discrete distributions 8

1.3 The inverse transform method 11

1.4 Rejection sampling 15

1.4.1 Basic rejection sampling 15

1.4.2 Envelope rejection sampling 18

1.4.3 Conditional distributions 22

1.4.4 Geometric interpretation 26

1.5 Transformation of random variables 30

1.6 Special-purpose methods 36

1.7 Summary and further reading 36

Exercises 37

2 Simulating statistical models 41

2.1 Multivariate normal distributions 41

2.2 Hierarchical models 45

2.3 Markov chains 50

2.3.1 Discrete state space 51

2.3.2 Continuous state space 56

2.4 Poisson processes 58

2.5 Summary and further reading 67

Exercises 67

3 Monte Carlo methods 69

3.1 Studying models via simulation 69

3.2 Monte Carlo estimates 74

3.2.1 Computing Monte Carlo estimates 75

3.2.2 Monte Carlo error 76

3.2.3 Choice of sample size 80

3.2.4 Refined error bounds 82

3.3 Variance reduction methods 84

3.3.1 Importance sampling 84

3.3.2 Antithetic variables 88

3.3.3 Control variates 93

3.4 Applications to statistical inference 96

3.4.1 Point estimators 97

3.4.2 Confidence intervals 100

3.4.3 Hypothesis tests 103

3.5 Summary and further reading 106

Exercises 106

4 Markov Chain Monte Carlo methods 109

4.1 The Metropolis-Hastings method 110

4.1.1 Continuous state space 110

4.1.2 Discrete state space 113

4.1.3 Random walk Metropolis sampling 116

4.1.4 The independence sampler 119

4.1.5 Metropolis-Hastings with different move types 120

4.2 Convergence of Markov Chain Monte Carlo methods 125

4.2.1 Theoretical results 125

4.2.2 Practical considerations 129

4.3 Applications to Bayesian inference 137

4.4 The Gibbs sampler 141

4.4.1 Description of the method 141

4.4.2 Application to parameter estimation 146

4.4.3 Applications to image processing 151

4.5 Reversible Jump Markov Chain Monte Carlo 158

4.5.1 Description of the method 160

4.5.2 Bayesian inference for mixture distributions 171

4.6 Summary and further reading 178

4.6 Exercises 178

5 Beyond Monte Carlo 181

5.1 Approximate Bayesian Computation 181

5.1.1 Basic Approximate Bayesian Computation 182

5.1.2 Approximate Bayesian Computation with regression 188

5.2 Resampling methods 192

5.2.1 Bootstrap estimates 192

5.2.2 Applications to statistical inference 197

5.3 Summary and further reading 209

Exercises 209

6 Continuous-time models 213

6.1 Time discretisation 213

6.2 Brownian motion 214

6.2.1 Properties 216

6.2.2 Direct simulation 217

6.2.3 Interpolation and Brownian bridges 218

6.3 Geometric Brownian motion 221

6.4 Stochastic differential equations 224

6.4.1 Introduction 224

6.4.2 Stochastic analysis 226

6.4.3 Discretisation schemes 231

6.4.4 Discretisation error 236

6.5 Monte Carlo estimates 243

6.5.1 Basic Monte Carlo 243

6.5.2 Variance reduction methods 247

6.5.3 Multilevel Monte Carlo estimates 250

6.6 Application to option pricing 255

6.7 Summary and further reading 259

Exercises 260

Appendix A Probability reminders 263

A.1 Events and probability 263

A.2 Conditional probability 266

A.3 Expectation 268

A.4 Limit theorems 269

A.5 Further reading 270

Appendix B Programming in R 271

B.1 General advice 271

B.2 R as a Calculator 272

B.2.1 Mathematical operations 273

B.2.2 Variables 273

B.2.3 Data types 275

B.3 Programming principles 282

B.3.1 Don't repeat yourself! 283

B.3.2 Divide and conquer! 286

B.3.3 Test your code! 290

B.4 Random number generation 292

B.5 Summary and further reading 294

Exercises 294

Appendix C Answers to the exercises 299

C.1 Answers for Chapter 1 299

C.2 Answers for Chapter 2 315

C.3 Answers for Chapter 3 319

C.4 Answers for Chapter 4 328

C.5 Answers for Chapter 5 342

C.6 Answers for Chapter 6 350

C.7 Answers for Appendix B 366

References 375

Index 379