Week 5 Preparation Guide

Reading

Required: Textbook Chapters 10 and 11. There’s no additional reading. Please go through all the examples in the textbook with a pencil and paper at hand, working out the steps as you read.

Practice Problems

• David Aldous’ former student Takis Konstantopoulos created a great resource. Resist the impulse to read the answers before you try the problems yourself. Also be warned that some of the problems can be solved by less work than in the answers. Try 7 (‘topological properties’ means whether it is irreducible and what its period is; for the irreducible aperiodic ones, find the long run proportion of time spent at each state), 16, 21, 25, 27 (you can do this one without calculation), 36.

• Let $X_0, X_1, \ldots $ be an irreducible, aperiodic Markov Chain on a finite state space $S$. Let $\mathbb{P}$ be the transition matrix of the chain. Let $\lambda$ be a vector containing the distribution of $X_0$, that is, for all $i \in S$, let $\lambda(i) = P(X_0 = i)$. This is called the initial distribution of the chain.

  • Find the distribution of $X_n$ in terms of $\lambda$, $\mathbb{P}$, and $n$.
  • What happens to the distribution of $X_n$ as $n \to \infty$? Prove your answer.

Discussion Section

Konstantopoulos 16, 36, 21, and the last problem above