Weather that tends to persist, a customer switching brands, a board-game token: in each, the next state is random, but its chances depend on the current state. A Markov chain models this. Its one-step behavior is a table of conditional probabilities, and many steps are computed by matrix multiplication.
Key idea
A Markov chain has the property that, given the present state, the past does not matter: $$P(X_{n + 1} = j \mid X_n = i, \text{earlier states}) = P_{ij}$$ The transition matrix $P$ has row $i$ listing the chances of moving from state $i$, so every row adds to 1. A distribution is a row vector $\pi_n$, and $$\pi_{n + 1} = \pi_n P, \qquad \pi_n = \pi_0 P^{n};$$ entry $(i, j)$ of $P^{n}$ is the chance of going from $i$ to $j$ in $n$ steps.
Why it works
Condition on where the chain is now, using the law of total probability: $$P(X_{n + 1} = j) = \sum_i P(X_n = i)\,P_{ij}.$$ The right side is the row vector $\pi_n$ times column $j$ of $P$, so $\pi_{n + 1} = \pi_n P$. Repeating, $\pi_n = \pi_0 P^{n}$. Starting surely in state $i$ makes $\pi_0$ a row of zeros with a single 1, and then $\pi_0 P^{n}$ is row $i$ of $P^{n}$.
Mind the convention. Here, as in most probability books, rows of $P$ add to 1 and the distribution is a row vector multiplied on the left. The Linear Algebra lesson on Markov chains uses the transpose: columns add to 1 and $\mathbf{x}_{k + 1} = P\mathbf{x}_k$ with column vectors. The two describe the same chain.
Worked examples
Worked example: Two steps ahead
Weather: from Sunny, tomorrow is Sunny or Rainy with probability $\frac{1}{2}$ each; from Rainy, Sunny with $\frac{1}{4}$ and Rainy with $\frac{3}{4}$. Today is Sunny. Find the chance the day after tomorrow is Rainy.
- Write S for Sunny and R for Rainy, and condition on tomorrow: $P(X_2 = R) = P_{SS}P_{SR} + P_{SR}P_{RR}$.
- $= \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{3}{4} = \frac{1}{4} + \frac{3}{8} = \frac{5}{8}$.
- This is entry (Sunny, Rainy) of $P^{2}$, as the next example confirms.
Answer: $\frac{5}{8}$
Worked example: The whole matrix
For the same chain, find $P^{2}$.
- Row 1: $\left(\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{4},\ \frac{5}{8}\right) = \left(\frac{3}{8}, \frac{5}{8}\right)$.
- Row 2: $$\left(\frac{1}{4} \cdot \frac{1}{2} + \frac{3}{4} \cdot \frac{1}{4},\ \frac{1}{4} \cdot \frac{1}{2} + \frac{3}{4} \cdot \frac{3}{4}\right) = \left(\frac{5}{16}, \frac{11}{16}\right)$$
- Each row of $P^{2}$ adds to 1 again.
Answer: $$P^{2} = \begin{bmatrix} \frac{3}{8} & \frac{5}{8} \\ \frac{5}{16} & \frac{11}{16} \end{bmatrix}$$
Worked example: A distribution
If today is Sunny with probability $\frac{1}{2}$, find tomorrow's distribution.
- $\pi_1 = \left(\frac{1}{2}, \frac{1}{2}\right)P$.
- First entry: $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{4} = \frac{3}{8}$; second: $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{3}{4} = \frac{5}{8}$.
Answer: $\left(\frac{3}{8}, \frac{5}{8}\right)$
Common mistake
Multiplying on the wrong side, $P\pi_0$, with a matrix whose rows add to 1; that mixes the wrong entries and need not even give a distribution. Another slip is writing rows that do not add to 1, for example by listing the chances of arriving in a state along a row. Check: every row of $P$, and every $\pi_n$, adds to 1.