Markov Chains - Statistical Laboratory

1 Markov ChainsThese notes contain material prepared by colleagues who have also presented this courseat Cambridge, especially James Norris. The material mainlycomes from books ofNorris, Grimmett & Stirzaker, Ross, Aldous & Fill, and Grinstead & Snell. Many ofthe examples are classic and ought to occur in any sensible course on Markov of ContentsiSchedulesiv1 Definitions, basic properties, the transition An example and some interesting questions .. Definitions .. Where do Markov Chains come from?

2 How can we simulate them? .. Then-step transition matrix .. (n)for a two-state Markov chain .. 42 Calculation ofn-step transition probabilities, class structure, absorp-tion, and Example: a three-state Markov chain .. Example: use of symmetry .. Markov property .. Class structure .. Closed classes .. Irreducibility .. 83 Hitting probabilities and mean hitting Absorption probabilities and mean hitting times .. Calculation of hitting probabilities and mean hitting times.

3 Absorption probabilities are minimal solutions to RHEs .. Gambler s ruin .. 124 Survival probability for birth and death Chains , stoppingtimesand strong Markov Survival probability for birth death Chains .. Mean hitting times are minimal solutions to RHEs .. Stopping times .. Strong Markov property .. 15i5 Recurrence and Recurrence and transience .. Equivalence of recurrence and certainty of return .. Equivalence of transience and summability ofn-step transition probabilities Recurrence as a class property.

4 Relation with closed classes .. 196 Random walks in dimensions one, two and Simple random walk onZ.. Simple symmetric random walk onZ2.. Simple symmetric random walk onZ3.. *A continuized analysis of random walk onZ3* .. *Feasibility of wind instruments* .. 247 Invariant 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.

5 288 Existence and uniqueness of invariant distribution, meanreturn time,positive and null Existence and uniqueness up to constant multiples .. Mean return time, positive and null recurrence .. Random surfer .. 329 Convergence to equilibrium for ergodic Equivalence of positive recurrence and the existence of an invariant dis-tribution .. Aperiodic Chains .. Convergence to equilibrium *and proof by coupling* ..3510 Long-run proportion of time spent in given Ergodic theorem .. *Kemeny s constant and the random target lemma*.

6 3911 Time reversal, detailed balance, reversibility, randomwalk on a graph Time reversal .. Detailed balance .. Reversibility .. Random walk on a graph .. 43ii12 Concluding problems and recommendations for further Reversibility and Ehrenfest s urn model .. Reversibility and theM/M/1 queue .. *The probabilistic abacus* .. *Random walks and electrical networks* .. Probability courses in Part II .. 50 Appendix51A Probability spaces51B Historical notes52C The probabilistic abacus for absorbing chains53 Index56 Topics marked * * are non-examinable.

7 Furthermore, only AppendixA is Weber, October 2011iiiSchedulesDefinition and basic properties, the transition matrix. Calculation ofn-step transitionprobabilities. Communicating classes, closed classes, absorption, irreducibility. Calcu-lation of hitting probabilities and mean hitting times; survival probability for birth anddeath Chains . Stopping times and statement of the strong Markovproperty. [5]Recurrence and transience; equivalence of transience and summability ofn-steptransition probabilities; equivalence of recurrence and certainty of return.

8 Recurrenceas a class property, relation with closed classes. Simple random walksin dimensionsone, two and three. [3]Invariant distributions, statement of existence and uniqueness up to constant mul-tiples. Mean return time, positive recurrence; equivalence of positive recurrence andthe existence of an invariant distribution. Convergence to equilibrium for irreducible,positive recurrent, aperiodic Chains *and proof by coupling*. Long-run proportion oftime spent in given state. [3]Time reversal, detailed balance, reversibility; random walk on a graph.

9 [1]Learning outcomesA Markov process is a random process for which the future (the next step) dependsonly on the present state; it has no memory of how the present state was reached. Atypical example is a random walk (in two dimensions, the drunkards walk). The courseis concerned with Markov Chains in discrete time, including periodicity and example, a random walk on a lattice of integers returns to the initial positionwith probability one in one or two dimensions, but in three or more dimensions theprobability of recurrence in zero.

10 Some Markov Chains settle down to an equilibriumstate and these are the next topic in the course. The material in this course will beessential if you plan to take any of the applicable courses in Part outcomesBy the end of this course, you should: understand the notion of a discrete-time Markov chain and be familiar with boththe finite state-space case and some simple infinite state-space cases, such asrandom walks and birth-and-death Chains ; know how to compute for simple examples then-step transition probabilities,hitting probabilities, expected hitting times and invariant distribution.