Matrix Powers and Markov Chains

Many processes repeat the same linear step: populations from year to year, money in accounts, customers switching brands. After $k$ steps the state is $A^{k}\mathbf{x}_0$. Diagonalization makes $A^{k}$ easy to compute and, better, easy to understand.

Key idea

If $A = PDP^{-1}$, then $A^{k} = PD^{k}P^{-1}$, and $D^{k}$ just raises each diagonal entry to the power $k$. In the long run, the largest eigenvalues dominate.

Why it works

$A^{2}$ $= (PDP^{-1})(PDP^{-1})$ $= PD(P^{-1}P)DP^{-1}$ $= PD^{2}P^{-1}$, because $P^{-1}P = I$ in the middle. The same cancellation happens in every power. In eigenvector coordinates, each step just multiplies coordinate $i$ by $\lambda_i$; after $k$ steps, by $\lambda_i^{k}$. Coordinates with $|\lambda_i| > 1$ grow, those with $|\lambda_i| < 1$ fade away.

Worked example: A third power

Compute $A^{3}$ for $A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}$ using $P = \begin{bmatrix} 1 & 1 \\ 1 & -2 \end{bmatrix}$ and $D = \begin{bmatrix} 5 & 0 \\ 0 & 2 \end{bmatrix}$.

$P^{-1}$ $= \frac{1}{-3}\begin{bmatrix} -2 & -1 \\ -1 & 1 \end{bmatrix}$ $= \begin{bmatrix} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & -\frac{1}{3} \end{bmatrix}$.
$D^{3} = \begin{bmatrix} 125 & 0 \\ 0 & 8 \end{bmatrix}$.
$PD^{3} = \begin{bmatrix} 125 & 8 \\ 125 & -16 \end{bmatrix}$, and $PD^{3}P^{-1} = \begin{bmatrix} 86 & 39 \\ 78 & 47 \end{bmatrix}$.
Check one entry the slow way: $A^{2} = \begin{bmatrix} 18 & 7 \\ 14 & 11 \end{bmatrix}$, and row 1 of $A^{2}$ times column 1 of $A$ is $(18)(4) + (7)(2) = 86$. ✓

Answer: $A^{3} = \begin{bmatrix} 86 & 39 \\ 78 & 47 \end{bmatrix}$

Markov chains

A Markov matrix (stochastic matrix) has nonnegative entries and columns that add up to $1$. Entry $(i, j)$ is the probability of moving from state $j$ to state $i$ in one step. A probability vector $\mathbf{x}_k$ lists the chances (or shares) of each state, and $\mathbf{x}_{k+1} = P\mathbf{x}_k$. A steady state is a probability vector $\mathbf{q}$ with $P\mathbf{q} = \mathbf{q}$: an eigenvector for $\lambda = 1$.

Worked example: A two-state chain

Each year 10% of a city's downtown residents move to the suburbs and 20% of suburban residents move downtown. Find the long-run split.

Order the states (downtown, suburbs). Column 1 is where downtown people go: $0.9$ stay, $0.1$ leave. So $P = \begin{bmatrix} 0.9 & 0.2 \\ 0.1 & 0.8 \end{bmatrix}$.
Steady state: $(P - I)\mathbf{q} = \mathbf{0}$ with $P - I = \begin{bmatrix} -0.1 & 0.2 \\ 0.1 & -0.2 \end{bmatrix}$. Both rows say $q_1 = 2q_2$.
So $\mathbf{q}$ is a multiple of $(2, 1)$; make the entries add to $1$: $\mathbf{q} = \left(\frac{2}{3}, \frac{1}{3}\right)$.
Check: $P\mathbf{q}$ $= (0.9 \cdot \frac{2}{3} + 0.2 \cdot \frac{1}{3},\ 0.1 \cdot \frac{2}{3} + 0.8 \cdot \frac{1}{3})$ $= \left(\frac{2}{3}, \frac{1}{3}\right)$. ✓

Answer: Two thirds downtown, one third in the suburbs.

Why it works

Why does every Markov matrix have the eigenvalue $1$, and why does the chain settle down? The columns of $P$ add to $1$, so $(1, 1, \dots, 1)P = (1, 1, \dots, 1)$: the all-ones vector is an eigenvector of $P^{T}$ for $1$, and $P$ and $P^{T}$ have the same eigenvalues. For this $P$ the other eigenvalue is $\operatorname{tr} P - 1 = 0.7$. Writing $\mathbf{x}_0 = \mathbf{q} + c\mathbf{w}$ in eigenvectors, $\mathbf{x}_k = \mathbf{q} + c(0.7)^{k}\mathbf{w} \to \mathbf{q}$, whatever the starting split.

The Markov matrix keeps the steady-state direction $(2, 1)$ fixed ($\lambda = 1$) and shrinks the direction $(1, -1)$ by $0.7$ each step.

The steady state does not depend on the start. For larger chains with all entries of some power $P^{k}$ positive (a regular chain), the same is true: $P^{k}\mathbf{x}_0 \to \mathbf{q}$ for every probability vector $\mathbf{x}_0$.

Matrix Powers and Markov Chains

Markov chains

Practice

Builds on

Leads to

Sources and further reading