Dynamics of Markov Chains for Undergraduates
                   Ursula Porod
                  February 19, 2021
                Contents
                Preface                                                                                           6
                1 Markov chains                                                                                   8
                    1.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      8
                    1.2   Construction of a Markov chain . . . . . . . . . . . . . . . . . . . . . . . .          9
                          1.2.1   Finite-length trajectories . . . . . . . . . . . . . . . . . . . . . . . .      9
                          1.2.2   From finite to infinite-length trajectories . . . . . . . . . . . . . . .        11
                    1.3   Basic computations for Markov chains         . . . . . . . . . . . . . . . . . . . .   16
                    1.4   Strong Markov Property . . . . . . . . . . . . . . . . . . . . . . . . . . . .         21
                    1.5   Examples of Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . .          23
                    1.6   Functions of Markov chains       . . . . . . . . . . . . . . . . . . . . . . . . . .   35
                    1.7   Irreducibility and class structure of the state space       . . . . . . . . . . . . .  42
                    1.8   Transience and Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . .        44
                    1.9   Absorbing chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       53
                          1.9.1   First step analysis    . . . . . . . . . . . . . . . . . . . . . . . . . . .   53
                          1.9.2   Finite number of transient states       . . . . . . . . . . . . . . . . . . .  55
                          1.9.3   Infinite number of transient states . . . . . . . . . . . . . . . . . . .       61
                    1.10 Stationary distributions      . . . . . . . . . . . . . . . . . . . . . . . . . . . .   66
                          1.10.1 Existence and uniqueness of an invariant measure . . . . . . . . . .            68
                          1.10.2 Positive recurrence versus null recurrence . . . . . . . . . . . . . . .        73
                          1.10.3 Stationary distributions for reducible chains . . . . . . . . . . . . .         74
                          1.10.4 Steady state distributions      . . . . . . . . . . . . . . . . . . . . . . .   76
                    1.11 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     77
                    1.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     85
                2 Limit Theorems for Markov Chains                                                               87
                    2.1   The Ergodic Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          87
                    2.2   Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      93
                    2.3   Long-run behavior of reducible chains . . . . . . . . . . . . . . . . . . . . .        98
                                                                 1
               CONTENTS                                                                                  2
                  2.4   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
               3 Random Walks on Z                                                                    101
                  3.1   Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
                  3.2   Wald’s Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
                  3.3   Gambler’s Ruin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
                  3.4   P´olya’s Random Walk Theorem . . . . . . . . . . . . . . . . . . . . . . . . 111
                  3.5   Reflection Principle and Duality . . . . . . . . . . . . . . . . . . . . . . . . 115
                        3.5.1  The ballot problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
                        3.5.2  Dual walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
                        3.5.3  Maximum and minimum . . . . . . . . . . . . . . . . . . . . . . . . 124
                  3.6   Arcsine Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
                        3.6.1  Last returns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
                        3.6.2  How often in the lead? . . . . . . . . . . . . . . . . . . . . . . . . . 128
                  3.7   The Range of a Random Walk . . . . . . . . . . . . . . . . . . . . . . . . . 130
                  3.8   Law of the Iterated Logarithm . . . . . . . . . . . . . . . . . . . . . . . . . 134
                  3.9   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
               4 Branching Processes                                                                  137
                  4.1   Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
                  4.2   Extinction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
                  4.3   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
               5 Martingales                                                                          149
                  5.1   Definition of a Martingale . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
                  5.2   Optional Stopping Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 154
                  5.3   Martingale transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
                  5.4   Martingale Convergence Theorem . . . . . . . . . . . . . . . . . . . . . . . 161
                  5.5   Transience/recurrence via martingales . . . . . . . . . . . . . . . . . . . . . 162
                  5.6   Applications    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
                        5.6.1  Waiting times for sequence patterns . . . . . . . . . . . . . . . . . . 166
                        5.6.2  Gambler’s ruin, revisited    . . . . . . . . . . . . . . . . . . . . . . . 170
                        5.6.3  Branching process, revisited . . . . . . . . . . . . . . . . . . . . . . 172
                        5.6.4  P´olya’s Urn, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 174
                  5.7   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
               6 Reversibility                                                                        176
                  6.1   Time reversal of a Markov chain . . . . . . . . . . . . . . . . . . . . . . . . 176
               CONTENTS                                                                                     3
                   6.2  Reversible Markov chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
                        6.2.1   Linear-algebraic interpretation of reversibility  . . . . . . . . . . . . 181
                   6.3  Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
               7 Markov Chains and Electric Networks                                                     185
                   7.1  Reversible chains and graph networks . . . . . . . . . . . . . . . . . . . . . 185
                   7.2  Harmonic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
                   7.3  Voltage and Current . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
                   7.4  Effective resistance and Escape probabilities . . . . . . . . . . . . . . . . . 194
                   7.5  Commute times and Cover times . . . . . . . . . . . . . . . . . . . . . . . 201
                   7.6  Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
               8 Markov Chain Monte Carlo                                                                211
                   8.1  MCMCAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
                        8.1.1   Metropolis-Hastings Algorithm      . . . . . . . . . . . . . . . . . . . . 211
                        8.1.2   Gibbs Sampler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
                   8.2  Stochastic Optimization and Simulated Annealing . . . . . . . . . . . . . . 219
                   8.3  Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
               9 Random Walks on Groups                                                                  226
                   9.1  Generators, Convolution powers . . . . . . . . . . . . . . . . . . . . . . . . 226
                        9.1.1   Time reversal of a random walk . . . . . . . . . . . . . . . . . . . . 230
                   9.2  Card shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
                   9.3  Abelian groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
                        9.3.1   Characters and eigenvalues     . . . . . . . . . . . . . . . . . . . . . . 236
                   9.4  Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
               10 Rates of Convergence                                                                   241
                   10.1 Basic set-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
                   10.2 Spectral bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
                        10.2.1 Spectral decomposition of the transition matrix . . . . . . . . . . . 246
                        10.2.2 Spectral bounds on total variation distance . . . . . . . . . . . . . . 249
                        10.2.3 Random walk on the discrete circle . . . . . . . . . . . . . . . . . . 251
                        10.2.4 The Ehrenfest chain      . . . . . . . . . . . . . . . . . . . . . . . . . . 253
                   10.3 Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
                        10.3.1 Definition of Coupling . . . . . . . . . . . . . . . . . . . . . . . . . 255
                        10.3.2 Coupling of Markov chains . . . . . . . . . . . . . . . . . . . . . . . 258
                   10.4 Strong Stationary Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265