Markov Chains

Table of Contents Schedules Definitions, basic properties, the transition matrix An example and some interesting questions Definitions Where do Markov chains come from? How can we simulate them? The n-step transition matrix P(n) for a two-state Markov chain Calculation of n-step transition probabilities, class structure, absorption, and irreducibility Example: a three-state Markov chain Example: use of symmetry Markov property Class structure Closed classes Irreducibility Hitting probabilities and mean hitting times Absorption probabilities and mean hitting times Calculation of hitting probabilities and mean hitting times Absorption probabilities are minimal solutions to RHEs Gambler's ruin Survival probability for birth and death chains, stopping times and strong Markov property Survival probability for birth death chains Mean hitting times are minimal solutions to RHEs Stopping times Strong Markov property Recurrence and transience Recurrence and transience Equivalence of recurrence and certainty of return Equivalence of transience and summability of n-step transition probabilities Recurrence as a class property Relation with closed classes Random walks in dimensions one, two and three Simple random walk on Z Simple symmetric random walk on Z2 Simple symmetric random walk on Z3 *A continuized analysis of random walk on Z3* *Feasibility of wind instruments* Invariant distributions Examples of invariant distributions Notation What does an invariant measure or distribution tell us? Invariant distribution is the solution to LHEs Stationary distributions Equilibrium distributions Existence and uniqueness of invariant distribution, mean return time, positive and null recurrence Existence and uniqueness up to constant multiples Mean return time, positive and null recurrence Random surfer Convergence to equilibrium for ergodic chains Equivalence of positive recurrence and the existence of an invariant distribution Aperiodic chains Convergence to equilibrium *and proof by coupling* Long-run proportion of time spent in given state Ergodic theorem *Kemeny's constant and the random target lemma* Time reversal, detailed balance, reversibility, random walk on a graph Time reversal Detailed balance Reversibility Random walk on a graph Concluding problems and recommendations for further study Reversibility and Ehrenfest's urn model Reversibility and the M/M/1 queue *The probabilistic abacus* *Random walks and electrical networks* Probability courses in Part II Appendix Probability spaces Historical notes The probabilistic abacus for absorbing chains Index