Stochastic Syllabus

1 Introduction and Review 1
1.1 Deterministic and Stochastic Models, 1
1.2 What is a Stochastic Process? 6
1.3 Monte Carlo Simulation, 9
1.4 Conditional Probability, 10
1.5 Conditional Expectation, 18

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

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

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

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 Shufling and Total Variation Distance*, 212

6 Poisson Process 223
6.1 Introduction, 223
6.2 Arrival, Interarrival Times, 227
6.3 Ininitesimal 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

7 Continuous-Time Markov Chains 265
7.1 Introduction, 265
7.2 Alarm Clocks and Transition Rates, 270
7.3 Ininitesimal Generator, 273
7.4 Long-Term Behavior, 283
7.5 Time Reversibility, 294
7.6 Queueing Theory, 301
7.7 Poisson Subordination, 306

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

9 A Gentle Introduction to Stochastic Calculus* 372
9.1 Introduction, 372
9.2 Ito Integral, 378
9.3 Stochastic Differential Equations, 385