This note covers Markov chains: systems that move between a fixed set of states with probabilities that depend only on the current state. You will build transition matrices, predict the state after several steps using matrix powers, and find the long-term (steady state) behaviour. Markov models are used for customer loyalty, weather patterns, population movement and queues.
Key ideas
A Markov chain has a list of states, and at each step the system moves from its current state to a state (possibly the same one) with fixed probabilities. The key property is that the next state depends only on the present state, not on how the system arrived there.
- Transition matrix \(T\). The entry in row \(i\) and column \(j\) is the probability of moving from state \(j\) to state \(i\). With this layout, each column adds up to 1, and every entry is between 0 and 1. A transition diagram with arrows and probabilities shows the same information.
- State vector. A column vector \(\mathbf{s}_n\) gives the distribution after \(n\) steps, either as probabilities (adding to 1) or as counts (adding to the total population).
- Prediction. \(\mathbf{s}_{n}=T^{n}\mathbf{s}_0\). Use the matrix power function on the GDC. Also \(\mathbf{s}_{n+1}=T\mathbf{s}_n\). The matrix \(T^n\) shows the \(n\)-step probabilities: its entry in row \(i\), column \(j\) is the probability of being in state \(i\) after \(n\) steps, given a start in state \(j\).
- Regular chain. A chain is regular if some power of \(T\) has every entry strictly positive. For a regular chain, \(T^n\mathbf{s}_0\) approaches a single long-term vector whatever the starting state.
- Steady state. The steady-state vector \(\mathbf{s}\) satisfies \(T\mathbf{s}=\mathbf{s}\), with entries adding to 1. It is an eigenvector of \(T\) for eigenvalue 1, scaled so the entries add to 1. It can be found by solving equations by hand, or by taking a very large power of \(T\) on the GDC.
The steady state does not mean that individuals stop moving. It means the proportions in each state stay constant, because the flows in and out of every state balance.
To find a steady state by hand, write the equations from \(T\mathbf{s}=\mathbf{s}\). They are not independent (one is redundant), so use the equation that the entries sum to 1 to finish.
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| Transition matrix \(T\) | Square matrix of probabilities; columns sum to 1 in the layout "from column, to row". |
| \(\mathbf{s}_{n}=T^{n}\mathbf{s}_0\) | State vector after \(n\) steps from the initial vector \(\mathbf{s}_0\). |
| \(\mathbf{s}_{n+1}=T\mathbf{s}_n\) | One step forward. |
| \(T\mathbf{s}=\mathbf{s}\) | Steady-state condition. |
| Sum of entries of \(\mathbf{s}\) equals 1 | Normalisation used to find the steady state of probabilities. |
| Regular chain | Some power of \(T\) has all entries greater than 0; guarantees a unique steady state. |
Worked examples
Example 1 Each month, commuters in a town use bus (B), train (T) or bicycle (C). Of bus users, 70% use the bus again next month, 20% switch to train and 10% to bicycle. Of train users, 80% stay, 10% switch to bus and 10% to bicycle. Of cyclists, 60% stay, 20% switch to bus and 20% to train. Initially 400 use the bus, 500 the train and 100 the bicycle. Find the numbers after one month and after three months.
Order the states B, T, C. Each column describes where one group goes:
\[T=\begin{pmatrix}0.7&0.1&0.2\\0.2&0.8&0.2\\0.1&0.1&0.6\end{pmatrix},\qquad \mathbf{s}_0=\begin{pmatrix}400\\500\\100\end{pmatrix}\]
The columns add to 1, as required.
After one month: \(\mathbf{s}_1=T\mathbf{s}_0\). Bus: \(0.7\times 400+0.1\times 500+0.2\times 100=280+50+20=350\). Train: \(0.2\times 400+0.8\times 500+0.2\times 100=80+400+20=500\). Bicycle: \(0.1\times 400+0.1\times 500+0.6\times 100=40+50+60=150\).
After three months: use the matrix power function to find \(T^3\), then multiply by \(\mathbf{s}_0\): \(\mathbf{s}_3=T^3\mathbf{s}_0=(312.5,\;500,\;187.5)^T\).
Answer: after one month 350, 500, 150. After three months 312.5, 500, 187.5 (the halves show these are expected numbers, not exact counts of people).
Example 2 A phone user is either on network A or network B. Each year, 90% of A customers stay and 10% move to B. Of B customers, 70% stay and 30% move to A. Find the long-term proportion on each network.
\[T=\begin{pmatrix}0.9&0.3\\0.1&0.7\end{pmatrix}\]
Let the steady state be \(\mathbf{s}=(a,\,b)^T\). From \(T\mathbf{s}=\mathbf{s}\): \(0.9a+0.3b=a\), which gives \(0.3b=0.1a\), so \(a=3b\).
The second equation, \(0.1a+0.7b=b\), gives the same relationship, so it is redundant.
Use \(a+b=1\): \(3b+b=1\), so \(b=0.25\) and \(a=0.75\).
Answer: 75% on network A and 25% on network B in the long run.
Example 3 Using the commuter matrix \(T\) from Example 1, find (a) the probability that a person who cycles this month uses the bus in two months' time, (b) the long-term numbers if the town has 1000 commuters, given that the steady state is \((0.3,\,0.5,\,0.2)^T\).
(a) Use the GDC to find \(T^2\):
\[T^2=\begin{pmatrix}0.53&0.17&0.28\\0.32&0.68&0.32\\0.15&0.15&0.40\end{pmatrix}\]
The start state is cycling, which is column 3. The bus is row 1. The entry is 0.28.
(b) First check that the steady state is correct: \(0.7(0.3)+0.1(0.5)+0.2(0.2)=0.21+0.05+0.04=0.30\), \(0.2(0.3)+0.8(0.5)+0.2(0.2)=0.06+0.40+0.04=0.50\), and \(0.1(0.3)+0.1(0.5)+0.6(0.2)=0.03+0.05+0.12=0.20\). So \(T\mathbf{s}=\mathbf{s}\).
Long-term numbers: \(1000\times(0.3,0.5,0.2)=(300,\,500,\,200)\).
Answer: (a) 0.28 (b) 300 bus, 500 train, 200 bicycle.
Common errors
- Writing the matrix with rows adding to 1 when the problem uses the "from column, to row" layout. Check which way your matrix is arranged before multiplying.
- Multiplying in the wrong order. With column vectors the calculation is \(T^n\mathbf{s}_0\), not \(\mathbf{s}_0T^n\).
- Using \(nT\) instead of \(T^n\) (repeated matrix multiplication, not multiplication by a number).
- Forgetting the condition that entries sum to 1 when solving for the steady state, which leaves infinitely many solutions.
- Reading the steady state as "everyone stops moving", or giving unrounded fractions of people without comment.
Exam tip: Label the rows and columns with the state names and state which way your matrix is arranged. Check that each column sums to 1 before doing any calculation.
Check yourself
- \(T=\begin{pmatrix}0.6&0.5\\0.4&0.5\end{pmatrix}\). A system starts in state 1. Find the probability it is in state 1 after two steps.
Answer
\(\mathbf{s}_2=T^2(1,0)^T\). \(T^2=\begin{pmatrix}0.56&0.55\\0.44&0.45\end{pmatrix}\), so the probability is 0.56. - Find the steady state of the same \(T\).
Answer
\(0.6a+0.5b=a\) gives \(0.5b=0.4a\), so \(b=0.8a\). With \(a+b=1\): \(1.8a=1\), \(a=\frac59\approx 0.556\) and \(b=\frac49\approx 0.444\). - \(T=\begin{pmatrix}0.8&a\\b&0.65\end{pmatrix}\) is a transition matrix with columns summing to 1. Find \(a\) and \(b\).
Answer
Column 1: \(0.8+b=1\), so \(b=0.2\). Column 2: \(a+0.65=1\), so \(a=0.35\). - Using the commuter matrix from Example 1, find \(T\mathbf{s}\) for \(\mathbf{s}=(0.2,\,0.5,\,0.3)^T\).
Answer
Row 1: \(0.14+0.05+0.06=0.25\). Row 2: \(0.04+0.40+0.06=0.50\). Row 3: \(0.02+0.05+0.18=0.25\). The result is \((0.25,\,0.5,\,0.25)^T\).