MIT 6.1220 — Lecture 20

Random Walks (Part I)

Definition (Markov Chain). A Markov chain is a sequence of random variables $\{X_t \mid t \in \mathbb{N}\}$ such that $X_{t + 1}$ is independent of history $X_0, \dots, X_{t - 1}$ given $X_t$ .

Remark. Even if a process depends on more history than just the previous state, it is sometimes possible to interpret it as a Markov chain by extending the state space.

Definition (Time-Homogeneous). A Markov chain is time-homogeneous if there is a finite transition probability matrix $W$ such that, for all pairs of states $(u, v)$ , we have $\mathrm{Pr}[X_{t + 1} = v \mid X_t = u] = W(u, v)$ for all $t$ .

Definition (Stationary). A distribution $\pi_*$ is stationary with respect to $W$ if $\pi_* = \pi_*W$ .

Definition (DG Terms). Draw the directed graph (DG) of $W$ : one vertex per state, with an edge $u \to v$ whenever $W(u, v) > 0$ . Two vertices $u, v$ are said to communicate with each other (denoted $u \leftrightsquigarrow v$ ) if there is a directed path from $u$ to $v$ and vice versa. Equivalence classes under $\leftrightsquigarrow$ are called strongly connected components. A component is transient if it has an outgoing edge, and recurrent otherwise.

Definition (Period). The period of a vertex $v$ is the GCD of the lengths of all directed walks from $v$ back to itself. A vertex is periodic if its period is greater than $1$ , and aperiodic otherwise.

Remark. Only the recurrent components matter; you can WLOG our distribution began strictly inside of a recurrent component, for any choice of recurrent component.

Claim. (Fundamental Theorem of Markov Chains.)

Every time-homogeneous Markov chain $W$ has a stationary distribution. Furthermore,

The stationary distribution $\pi_*$ is unique if and only if the DG has a unique recurrent component.
If all vertices in the recurrent components are aperiodic, then for every choice of initial distribution $\pi_0$ , the distribution $\pi_t = \pi_0W^t$ of $X_t$ converges as $t \to \infty$ .