Run a Markov chain for a long time and, for most chains, the distribution of the state stops changing: the chain forgets where it started. That limiting distribution is the stationary distribution, found by solving a small linear system, as in elimination.
Key idea
A stationary distribution is a row vector $\pi$ with $$\pi P = \pi \quad \text{and} \quad \pi_1 + \cdots + \pi_n = 1.$$ For a chain that can reach every state from every state and does not cycle with a fixed period, $\pi_n \to \pi$ from any start, $\pi_i$ is the long-run fraction of time spent in state $i$, and the mean time to return to $i$ is $\frac{1}{\pi_i}$.
Why it works
If the chain's distribution is ever $\pi$, the next one is $\pi P = \pi$: it stays put, which is why it is called stationary. Entry by entry, $\pi P = \pi$ says that the probability flowing into each state equals the probability flowing out: a balance of flows. These equations only fix the ratios of the $\pi_i$ (any multiple of a solution is a solution, including 0), so the condition that the entries add to 1 is needed to pin down the answer. In the Linear Algebra lesson the same vector appears as an eigenvector for eigenvalue 1 of the column-stochastic matrix, the transpose of our $P$.
Worked examples
Worked example: Two states
Weather: $$P = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{4} & \frac{3}{4} \end{bmatrix}$$ on (Sunny, Rainy). Find the long-run fraction of rainy days.
- $\pi P = \pi$, first entry: $\pi_1 = \frac{1}{2}\pi_1 + \frac{1}{4}\pi_2$, so $\frac{1}{2}\pi_1 = \frac{1}{4}\pi_2$: flow out of Sunny equals flow in.
- So $\pi_2 = 2\pi_1$. With $\pi_1 + \pi_2 = 1$: $\pi = \left(\frac{1}{3}, \frac{2}{3}\right)$.
Answer: $\frac{2}{3}$ of days are rainy in the long run.
Worked example: Three states
For the chain in the picture, find $\pi$ and the mean return time to A.
- Column A: $\pi_A = \frac{1}{4}\pi_B + \frac{1}{3}\pi_C$. Column B: $\pi_B = \frac{1}{2}\pi_A + \frac{1}{2}\pi_B + \frac{1}{3}\pi_C$.
- Drop the third equation (it follows from the others) and add $\pi_A + \pi_B + \pi_C = 1$. Solving: $\pi = \left(\frac{2}{9}, \frac{4}{9}, \frac{1}{3}\right)$.
- Check column C: $$\frac{1}{2} \cdot \frac{2}{9} + \frac{1}{4} \cdot \frac{4}{9} + \frac{1}{3} \cdot \frac{1}{3} = \frac{1}{9} + \frac{1}{9} + \frac{1}{9} = \frac{1}{3}$$ Mean return time to A: $\frac{9}{2}$ steps.
Answer: $\pi = \left(\frac{2}{9}, \frac{4}{9}, \frac{1}{3}\right)$; $\frac{9}{2}$ steps.
Worked example: A small queue
A queue holds 0, 1 or 2 people. Each minute one person arrives with probability $\frac{1}{3}$ (unless full) or one leaves with probability $\frac{1}{2}$ (unless empty). Find $\pi$.
- Flow up across each gap equals flow down: $\frac{1}{3}\pi_0 = \frac{1}{2}\pi_1$ and $\frac{1}{3}\pi_1 = \frac{1}{2}\pi_2$.
- So $\pi \propto \left(1, \frac{2}{3}, \frac{4}{9}\right)$, with total $\frac{19}{9}$.
- $\pi = \left(\frac{9}{19}, \frac{6}{19}, \frac{4}{19}\right)$.
Answer: $\left(\frac{9}{19}, \frac{6}{19}, \frac{4}{19}\right)$
Common mistake
Solving $\pi P = \pi$ but dropping the condition that $\pi$ adds to 1. The balance equations alone allow every multiple of the answer, including $\pi = 0$, so you may report a multiple of the right vector or get stuck. Check: your $\pi$ must have nonnegative entries adding to 1, and $\pi P$ must give $\pi$ back.