Preface xi
Acknowledgments xv
List of Symbols and Notation xvii
About the Companion Website xxi
1 Introduction and Review 1
1.1 Deterministic and Stochastic Models 1
1.2 What is a Stochastic Process? 5
1.3 Monte Carlo Simulation 9
1.4 Conditional Probability 10
1.5 Conditional Expectation 18
Exercises 34
2 Markov Chains: First Steps 40
2.1 Introduction 40
2.2 Markov Chain Cornucopia 42
2.3 Basic Computations 52
2.4 Long-Term Behavior-the Numerical Evidence 59
2.5 Simulation 65
2.6 Mathematical Induction* 68
Exercises 70
3 Markov Chains for the Long Term 76
3.1 Limiting Distribution 76
3.2 Stationary Distribution 80
3.3 Can you Find the Way to State a? 94
3.4 Irreducible Markov Chains 103
3.5 Periodicity 106
3.6 Ergodic Markov Chains 109
3.7 Time Reversibility 114
3.8 Absorbing Chains 119
3.9 Regeneration and the Strong Markov Property* 133
3.10 Proofs of Limit Theorems* 135
Exercises 144
4 Branching Processes 158
4.1 Introduction 158
4.2 Mean Generation Size 160
4.3 Probability Generating Functions 164
4.4 Extinction is Forever 168
Exercises 175
5 Markov Chain Monte Carlo 181
5.1 Introduction 181
5.2 Metropolis-Hastings Algorithm 187
5.3 Gibbs Sampler 197
5.4 Perfect Sampling* 205
5.5 Rate of Convergence: the Eigenvalue Connection* 210
5.6 Card Shuffling and Total Variation Distance* 212
Exercises 219
6 Poisson Process 223
6.1 Introduction 223
6.2 Arrival, Interarrival Times 227
6.3 Infinitesimal Probabilities 234
6.4 Thinning, Superposition 238
6.5 Uniform Distribution 243
6.6 Spatial Poisson Process 249
6.7 Nonhomogeneous Poisson Process 253
6.8 Parting Paradox 255
Exercises 258
7 Continuous-Time Markov Chains 265
7.1 Introduction 265
7.2 Alarm Clocks and Transition Rates 270
7.3 Infinitesimal Generator 273
7.4 Long-Term Behavior 283
7.5 Time Reversibility 294
7.6 Queueing Theory 301
7.7 Poisson Subordination 306
Exercises 313
8 Brownian Motion 320
8.1 Introduction 320
8.2 Brownian Motion and Random Walk 326
8.3 Gaussian Process 330
8.4 Transformations and Properties 334
8.5 Variations and Applications 345
8.6 Martingales 356
Exercises 366
9 A Gentle Introduction to Stochastic Calculus* 372
9.1 Introduction 372
9.2 Ito Integral 378
9.3 Stochastic Differential Equations 385
Exercises 397
A Getting Started with R 400
B Probability Review 421
B.1 Discrete Random Variables 422
B.2 Joint Distribution 424
B.3 Continuous Random Variables 426
B.4 Common Probability Distributions 428
B.5 Limit Theorems 439
B.6 Moment-Generating Functions 440
C Summary of Common Probability Distributions 443
D Matrix Algebra Review 445
D.1 Basic Operations 445
D.2 Linear System 447
D.3 Matrix Multiplication 448
D.4 Diagonal, Identity Matrix, Polynomials 448
D.5 Transpose 449
D.6 Invertibility 449
D.7 Block Matrices 449
D.8 Linear Independence and Span 450
D.9 Basis 451
D.10 Vector Length 451
D.11 Orthogonality 452
D.12 Eigenvalue, Eigenvector 452
D.13 Diagonalization 453
Answers to Selected Odd-Numbered Exercises 455
References 470
Index 475
