Markov Chains

A system is in one of several states and moves between them at each step. Each transition is random, but the probabilities depend only on the current state. Where the system was before the current step does not influence where it goes next. The present state alone determines the distribution of the next state. This memoryless property is the defining feature of a Markov chain. The past has no influence beyond the current state. Because of this property, the entire evolution of the system is determined by a single matrix of transition probabilities.

A finite Markov chain has $n$ states and a transition matrix $P$ of size $n \times n$. The entry $P_{ij}$ is the probability that the system moves from state $i$ to state $j$ in one step. Since the system must move to some state, each row of $P$ sums to 1. A matrix with nonnegative entries whose rows all sum to 1 is called stochastic. The state at time $k$ is described by a row vector $\mathbf{p}^{(k)}$ whose $n$ entries give the probability of occupying each state. After one step, the distribution updates to

\[\mathbf{p}^{(k+1)} = \mathbf{p}^{(k)} P.\]

The new probability of being in state $j$ is the sum over all states $i$ of the current probability of being in $i$ times the probability of jumping from $i$ to $j$.

Repeating the update $k$ times gives $\mathbf{p}^{(k)} = \mathbf{p}^{(0)} P^k$. The matrix power $P^k$ holds all the $k$-step transition probabilities. Entry $(i, j)$ of $P^k$ is the probability of reaching state $j$ from state $i$ in exactly $k$ steps. If every state can be reached from every other state and the chain does not cycle through states with a fixed period, then $P^k$ converges as $k$ grows. Every row of the limiting matrix is the same vector $\boldsymbol{\pi}$, which satisfies $\boldsymbol{\pi} P = \boldsymbol{\pi}$ and has entries summing to 1. This is the stationary distribution. No matter where the system starts, its distribution converges to $\boldsymbol{\pi}$.

Take a concrete case. A system has two states, 1 and 2. From state 1, it stays with probability 0.6 and moves to 2 with probability 0.4. From state 2, it moves to 1 with probability 0.3 and stays with probability 0.7. The transition matrix is

\[P = \begin{bmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{bmatrix}.\]

Suppose the system starts in state 1, so $\mathbf{p}^{(0)} = (1,\, 0)$. After one step, $\mathbf{p}^{(1)} = (1,\, 0)\, P = (0.6,\, 0.4)$. After two steps, $\mathbf{p}^{(2)} = (0.6,\, 0.4)\, P = (0.48,\, 0.52)$. The probability shifts toward state 2. To find the stationary distribution, solve $\boldsymbol{\pi} P = \boldsymbol{\pi}$ with $\pi_1 + \pi_2 = 1$. Writing out the first component gives $0.6\,\pi_1 + 0.3\,\pi_2 = \pi_1$, which simplifies to $0.3\,\pi_2 = 0.4\,\pi_1$. Substituting $\pi_2 = 1 - \pi_1$ and solving yields $\pi_1 = 3/7$ and $\pi_2 = 4/7$. In the long run, the system spends three-sevenths of its time in state 1 and four-sevenths in state 2 regardless of where it began.

The equation $\boldsymbol{\pi} P = \boldsymbol{\pi}$ says the stationary distribution is a left eigenvector of $P$ for eigenvalue 1. Every stochastic matrix has 1 as an eigenvalue because its row sums force $P\mathbf{1} = \mathbf{1}$. The remaining eigenvalues, all at most 1 in absolute value, govern how fast the chain converges. In the example above, the eigenvalues of $P$ are 1 and 0.3. The contribution of the second eigenvalue to $\mathbf{p}^{(k)}$ decays like $0.3^k$, so after a few steps, the dependence on the initial state essentially vanishes. A chain whose second eigenvalue lies close to 1 mixes slowly and remains dependent on its initial distribution for many steps. A chain whose second eigenvalue lies close to 0 loses dependence on the initial state quickly and reaches equilibrium almost at once.