Markov Chains

Carl Graham CNRS (France's National Center for Scientific Research) and Ecole Polytechnique, Palaiseau, France.

• Preface ix List of Figures xiNomenclature xiiiIntroduction xv1 First steps 11.1 Preliminaries 11.2 First properties of Markov chains 21.2.1 Markov chains, finite-dimensional marginals, and laws 21.2.2 Transition matrix action and matrix notation 51.2.3 Random recursion and simulation 91.2.4 Recursion for the instantaneous laws, invariant laws 101.3 Natural duality: algebraic approach 111.3.1 Complex eigenvalues and spectrum 111.3.2 Doeblin condition and strong irreducibility 151.3.3 Finite state space Markov chains 171.4 Detailed examples 211.4.1 Random walk on a network 211.4.2 Gambler’s ruin 221.4.3 Branching process: evolution of a population 251.4.4 Ehrenfest’s Urn 271.4.5 Renewal process 331.4.6 Word search in a character chain 361.4.7 Product chain 38Exercises 402 Past, present, and future 472.1 Markov property and its extensions 472.1.1 Past -field, filtration, and translation operators 472.1.2 Markov property 482.1.3 Stopping times and strong Markov property 502.2 Hitting times and distribution 512.2.1 Hitting times, induced chain, and hitting distribution 512.2.2 “One step forward” method, Dirichlet problem 532.3 Detailed examples 602.3.1 Gambler’s ruin 602.3.2 Unilateral hitting time for a random walk 642.3.3 Exit time from a box 672.3.4 Branching process 672.3.5 Word search 71Exercises 733 Transience and recurrence 793.1 Sample paths and state space 793.1.1 Communication and closed irreducible classes 793.1.2 Transience and recurrence, recurrent class decomposition 803.1.3 Detailed examples 833.2 Invariant measures and recurrence 873.2.1 Invariant laws and measures 873.2.2 Canonical invariant measure 893.2.3 Positive recurrence, invariant law criterion 913.2.4 Detailed examples 933.3 Complements 973.3.1 Hitting times and superharmonic functions 973.3.2 Lyapunov functions 993.3.3 Time reversal, reversibility, and adjoint chain 1053.3.4 Birth-and-death chains 108Exercises 1114 Long-time behavior 1194.1 Path regeneration and convergence 1194.1.1 Pointwise ergodic theorem, extensions 1204.1.2 Central limit theorem for Markov chains 1244.1.3 Detailed examples 1264.2 Long-time behavior of the instantaneous laws 1284.2.1 Period and aperiodic classes 1284.2.2 Coupling of Markov chains and convergence in law 1324.2.3 Detailed examples 1394.3 Elements on the rate of convergence for laws 1404.3.1 The Hilbert space framework 1404.3.2 Dirichlet form, spectral gap, and exponential bounds 1434.3.3 Spectral theory for reversible matrices 1464.3.4 Continuous-time Markov chains 149Exercises 1505 Monte Carlo methods 1555.1 Approximate solution of the Dirichlet problem 1555.1.1 General principles 1555.1.2 Heat equation in equilibrium 1565.1.3 Heat equation out of equilibrium 1585.1.4 Parabolic partial differential equations 1595.2 Invariant law simulation 1625.2.1 Monte Carlo methods and ergodic theorems 1625.2.2 Metropolis algorithm, Gibbs law, and simulated annealing 1635.2.3 Exact simulation and backward recursion 166Appendix A Complements 171A.1 Basic probabilistic notions 171A.1.1 Discrete random variable, expectation, and generating function 171A.1.2 Conditional probabilities and independence 175A.2 Discrete measure convergence 177A.2.1 Total variation norm and maximal coupling 177A.2.2 Duality between measures and functions 180A.2.3 Weak convergence of laws and convergence in law 182A.3 Measure-theoretic framework 183A.3.1 Probability spaces 183A.3.2 Measurable spaces and functions: signed and nonnegative 185A.3.3 Random variables, their laws, and expectations 186A.3.4 Random sequences and Kolmogorov extension theorem 192References 195Solutions for the exercises 197Index 229