Transition Matrices & Markov Chains (AI HL)
A Markov chain models a system that moves between a fixed set of states over time, where the probability of the next move depends only on the current state. This topic covers writing down a valid transition matrix from a worded description, using it to find the probability distribution after any number of steps, and finding the long-term steady-state distribution the system settles into - by hand, by repeated matrix multiplication on the GDC, or via eigenvectors.
What the syllabus says
This topic maps onto one point in the official IB Applications & Interpretation syllabus, examinable only at HL.
| Code | Syllabus content |
|---|---|
| AHL4.19 | Transition matrices and powers of transition matrices. Use of transition diagrams to represent transitions in discrete dynamical systems. Regular Markov chains and initial state probability matrices. In general, the column state matrix \(s_n\) after \(n\) transitions is given by \(s_n = T^n s_0\), where \(T\) is the transition matrix (with \(T_{ij}\) the probability of moving from state \(j\) to state \(i\)) and \(s_0\) is the initial state matrix. Calculation of steady state and long-term probabilities by repeated multiplication of the transition matrix, or by solving a system of linear equations - with awareness that the solution is the eigenvector corresponding to the eigenvalue equal to \(1\). |
This is Additional Higher Level (AHL) content - examinable at AI HL only, not at AI SL.
Key terms
Five words worth knowing cold before you touch the formulas below - each with a worked example showing exactly what it means.
What is a transition matrix?
A transition matrix \(T\) records the probability of moving between states in one step. The entry \(T_{ij}\) is the probability of moving to state \(i\) given the system is currently in state \(j\). Every entry must be non-negative, and each column (a "current state") must sum to \(1\).
e.g. \(T=\begin{pmatrix}0.75&0.35\\0.25&0.65\end{pmatrix}\) is valid, since \(0.75+0.25=1\) and \(0.35+0.65=1\).
What is a state vector?
A state vector (or state matrix) \(s_n\) is a column vector listing the probability (or proportion) of being in each state after \(n\) steps. Its entries always sum to \(1\), since the system must be in exactly one state.
e.g. A machine that starts working, but has not yet had a chance to break down, has initial state vector \(s_0=\begin{pmatrix}1\\0\end{pmatrix}\).
What is a (regular) Markov chain?
A Markov chain is a sequence of states where the probability of the next state depends only on the current state, not on the earlier history. It's "regular" if, after enough steps, every state can be reached from every other state - which guarantees a unique steady-state distribution exists.
e.g. Weather modelled as sunny/cloudy, where tomorrow's weather depends only on today's, is a two-state Markov chain.
What is the steady-state distribution?
The steady-state distribution \(\pi\) is the state vector the system settles towards in the long run, satisfying \(T\pi = \pi\) with all its entries summing to \(1\). Once reached, further transitions leave the distribution unchanged.
e.g. For \(T=\begin{pmatrix}0.7&0.2\\0.3&0.8\end{pmatrix}\), solving \(T\pi=\pi\) with \(\pi_1+\pi_2=1\) gives \(\pi_1=\tfrac25,\ \pi_2=\tfrac35\).
What does T^n s0 give you?
\(T^n s_0\) gives the state vector after exactly \(n\) transitions, found by multiplying the transition matrix by itself \(n\) times and applying the result to the initial state. On a GDC this is a single matrix-power calculation.
e.g. With \(T=\begin{pmatrix}0.8&0.4\\0.2&0.6\end{pmatrix}\) and \(s_0=\begin{pmatrix}1\\0\end{pmatrix}\), \(T^2 s_0 = \begin{pmatrix}0.72\\0.28\end{pmatrix}\).
Key formulas
One core formula drives every calculation on this topic - the tables below show it, and how the steady-state case is really just a special case of it.
Formula reference
The state-after-n-transitions formula is on the official formula booklet; the steady-state equation is derived from it rather than listed separately.
| Formula | Used for | Booklet? |
|---|---|---|
| \(s_n = T^n s_0\) | State vector after \(n\) transitions | ✓ Yes |
| \(T\pi = \pi,\ \sum \pi_i = 1\) | Steady-state distribution | Not in the booklet - derived from \(s_n=T^ns_0\) |
| Each column of \(T\) sums to \(1\) | Checking \(T\) is a valid transition matrix | Not in the formula booklet - prior knowledge |
n-step distribution vs steady state
Both describe the same Markov chain, but answer different questions - one is a snapshot at a specific step, the other is the long-run limit.
| Feature | State after n steps | Steady state |
|---|---|---|
| Equation | \(s_n = T^n s_0\) | \(T\pi=\pi\) |
| Depends on \(s_0\)? | Yes | No (for a regular chain) |
| Method | Raise \(T\) to the power \(n\), multiply by \(s_0\) | Solve the linear system, or use a very large power of \(T\) |
| Example | \(T^2\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}0.72\\0.28\end{pmatrix}\) | \(\pi=\begin{pmatrix}2/5\\3/5\end{pmatrix}\) |
Valid transition matrices
Before using a transition matrix, it's worth being able to justify that it's actually valid.
Non-negative entries
Every \(T_{ij} \ge 0\)
Probabilities can never be negative, so no entry of a transition matrix can be either.
Columns sum to 1
\(\sum_i T_{ij} = 1\) for each \(j\)
Starting from any given state, the system must move somewhere (possibly staying put) with total probability 1.
Columns = "from" state
\(T_{ij}\): from \(j\) to \(i\)
Reading down a column shows where a system currently in that state can go next.
Working with T^n
Larger powers are always done on the GDC, never expanded by hand.
Repeated multiplication
\(s_1=Ts_0,\ s_2=Ts_1,\ \dots\)
Each step applies \(T\) once more to the previous state vector.
Matrix power shortcut
\(s_n = T^n s_0\)
Computing \(T^n\) directly and multiplying once is far faster than \(n\) separate multiplications.
n must be a whole number
Only integer transitions
\(T^n\) only makes sense for a whole number of steps - there's no "half a transition".
Finding the steady state
Two different routes reach the same answer - use whichever the question asks for.
Solve Tπ = π
Exact solution
Write out the equations, eliminate a variable, then use \(\sum \pi_i=1\) to solve exactly - often giving a fraction.
Eigenvector for λ = 1
Same equation, matrix language
\(\pi\) is the eigenvector of \(T\) corresponding to eigenvalue \(1\), normalised so its entries sum to \(1\).
High power shortcut
\(T^{50}s_0\) on the GDC
Raising \(T\) to a large power and reading the (near-identical) columns gives a fast numerical check.
Worked examples
Two full exam-style questions, marked exactly like the real thing. Try each one yourself before checking the worked solution.
\(T=\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}\) and \(s_0=\begin{pmatrix}1\\0\end{pmatrix}\):
(a) Find \(s_1=Ts_0\).
(b) Find \(s_2=Ts_1.\)
Worked solution
(a) \(s_1=\begin{pmatrix}0.7\\0.3\end{pmatrix}.\) M1
\(s_1=\begin{pmatrix}0.7\\0.3\end{pmatrix}.\) A1
(b) \(s_2=\begin{pmatrix}0.58\\0.42\end{pmatrix}.\) M1
\(s_2=\begin{pmatrix}0.58\\0.42\end{pmatrix}.\) A1
Each year, customers switch between providers A and B. 85% of A's customers stay with A; 70% of B's customers stay with B. The transition matrix is \(T=\begin{pmatrix}0.85&0.30\\0.15&0.70\end{pmatrix}\) acting on \(\begin{pmatrix}a\\b\end{pmatrix}.\)
(a) Initially \(a=0.6,\ b=0.4.\) Find the proportions after 2 years.
(b) Find the long-term (steady-state) proportions.
Worked solution
(a) \(T^2\begin{pmatrix}0.6\\0.4\end{pmatrix}\) M1
\(\approx\begin{pmatrix}0.647\\0.354\end{pmatrix}.\) About 64.7% with A. A1
About 35.4% with B. A1
(b) Steady state \(\mathbf{s}\) satisfies \(T\mathbf{s}=\mathbf{s},\ a+b=1:\) M1
\(0.15a=0.30b\Rightarrow a=2b.\) With \(a+b=1:\ a=\tfrac23.\) A1
\(b=\tfrac13.\) A1
Common mistakes
The four slip-ups that account for most of the marks lost on this topic - worth reading before you start practising, not just after you get one wrong.
- Mixing up rows and columns. \(T_{ij}\) is the probability of moving from state \(j\) (the column) to state \(i\) (the row) - reading a transition matrix the wrong way round reverses every probability.
- Forgetting the normalisation condition when solving Ts = s. The equation \(T\mathbf{s}=\mathbf{s}\) alone only fixes the ratio between the state probabilities - you also need \(\sum s_i = 1\) to pin down exact values.
- Multiplying in the wrong order. The transition matrix acts on the state vector as \(Ts_0\), not \(s_0T\) - matrix multiplication isn't commutative, so getting the order backwards gives nonsense (or an error) on the GDC.
- Using T·s0 when T^n·s0 is needed. "After 3 years" means \(T^3s_0\), not \(T \cdot s_0\) applied once - miscounting the number of transitions is one of the most common slips on this topic.
Using your GDC
Every step below is a real button sequence, not a vague "use your calculator" hint - covering the TI-84 Plus, TI-Nspire, and Casio fx-9860/fx-CG50. Pick your model to filter down to just the steps that apply to you.
Find the state after n steps, or the long-run steady state, by raising the transition matrix to a power.
- Enter the transition matrix and the initial state vector.
- Enter [A] in 2nd → MATRX → EDIT, then compute [A]^n × [B] on the home screen.TI-84
- Enter the matrix, then type matrix ^ n × the state vector.Nspire
- Run-Matrix → MAT to enter the matrix; compute Mat A ^ n × the state vector.Casio
- For the long-run state, raise the matrix to a large power (e.g. ^50) and read the stabilising column.
Tip: Columns of a high power of a regular transition matrix converge to the steady-state distribution.
Used in AI HL for long-run behaviour of systems (e.g. coupled populations, Markov chains). The GDC computes them directly - no characteristic polynomial by hand.
- Enter the square matrix (2×2 or 3×3) into the calculator.
- 2nd → MATRX → EDIT to enter [A]. On the home screen: eigVl([A]) gives eigenvalues; eigVc([A]) gives eigenvectors as columns.TI-84
- Enter the matrix, then menu → Matrix & Vector → Eigenvalues (or Eigenvectors). Or type eigVl(A) and eigVc(A) directly.Nspire
- Run-Matrix → MAT to enter the matrix; then OPTN → MAT → EIG → EigenVal / EigenVec.Casio
- Each eigenvalue λ has a corresponding eigenvector column. Check: A × eigenvector = λ × eigenvector.
- For a 2×2 transition matrix, the dominant eigenvalue is 1 and its eigenvector gives the long-run steady state (normalise so the components sum to 1).
Tip: Eigenvectors from the GDC may be scaled differently - only the direction matters, not the magnitude. Always normalise if you need probabilities or proportions.
See the full GDC guide for more calculator models and topics.
Ready to practise properly?
Transition matrices & Markov chains questions, marked instantly like the real exam.
Quick answers
The questions students on this topic ask most often.
What does an entry in a transition matrix actually mean?
The entry in row i, column j is the probability of moving to state i given that you're currently in state j. Each column represents the current state, so every column must sum to 1 - the system has to move somewhere (possibly staying put).
How do I find the state after n transitions on my GDC?
Enter the transition matrix T and the initial state vector s0, then compute T^n multiplied by s0 directly on the calculator's matrix screen - it handles the repeated multiplication instantly, even for large n.
How do I find the steady-state distribution?
Solve Ts = s together with the condition that the probabilities in s sum to 1. In practice this means writing out the equations from Ts = s, eliminating variables, and substituting into the sum-to-1 condition - or raising T to a very high power on the GDC and reading off the column it settles on.
Do I need eigenvalues for Markov chain questions?
Not usually for the calculation itself - most steady-state questions are solved directly from Ts = s. But you should be aware that the steady-state vector is the eigenvector of T corresponding to the eigenvalue 1, and your GDC's eigenvector function can be used to find it directly.
Sub-topics
Transition Matrices & Markov Chains broken down into its individual skills, each with its own focused page.
Related topics
More Statistics & Probability topics from the same AI HL syllabus unit, in case you want to keep going.