Contents

Preface page vii

1 Discrete-time Markov chains 1

1.1 The Markov property and its immediate consequences 1

1.2 Class division 17

1.3 Hitting times and probabilities 26

1.4 Strong Markov property 35

1.5 Recurrence and transience: definitions and basic facts 39

1.6 Recurrence and transience: random walks on lattices 45

1.7 Equilibrium distributions: definitions and basic facts 52

1.8 Positive and null recurrence 58

1.9 Convergence to equilibrium. Long-run proportions 70

1.10 Detailed balance and reversibility 80

1.11 Controlled and partially observed Markov chains 89

1.12 Geometric algebra of Markov chains, I 99

1.13 Geometric algebra of Markov chains, II 116

1.14 Geometric algebra of Markov chains, III 130

1.15 Large deviations for discrete-time Markov chains 138

1.16 Examination questions on discrete-time Markov chains 155

2 Continuous-time Markov chains 185

2.1 Q-matrices and transition matrices 185

2.2 Continuous-time Markov chains: definitions and basic constructions 196

2.3 The Poisson process 210

2.4 Inhomogeneous Poisson process 231

2.5 Birth-and-death process. Explosion 240

2.6 Continuous-time Markov chains with countably many states 250

2.8 Convergence to an equilibrium distribution. Reversibility 283

2.9 Applications to queueing theory. Markovian queues 291

2.10 Examination questions on continuous-time Markov chains 308

3 Statistics of discrete-time Markov chains 349

3.1 Introduction 349

3.2 Likelihood functions, 1. Maximum likelihood estimators 357

3.3 Consistency of estimators. Various forms of convergence 366

3.4 Likelihood functions, 2. Whittle’s formula 390

3.5 Bayesian analysis of Markov chains: prior and posterior distributions 401

3.6 Elements of control and information theory 415

3.7 Hidden Markov models, 1. State estimation for Markov chains 434

3.8 Hidden Markov models, 2. The Baum–Welch learning algorithm 451

3.9 Generalisations of the Baum–Welch algorithm 461

Epilogue: Andrei Markov and his Time 479

Bibliography 483