Transition matrices and Markov chains
In a minute
A moves between states, such as shops a customer uses, where the next step depends only on the current state. A holds the step probabilities, and predicts the state after steps. The , an of for the , gives the long-term proportions.
You'll be able to
- Build a transition matrix from a description or a , and interpret its entries in context.
- Find powers of a transition matrix and use to find probabilities after steps.
- Decide whether a Markov chain is regular, and say what that means for the long term.
- Find the steady state by repeated multiplication or by solving linear equations, exactly when asked.
- Find the steady state as an eigenvector for the eigenvalue 1, scaled so its entries add up to 1.
Before you start3 quick questions on what this builds on
Revise first: 1.8 Solving equations with technology, 1.14 Matrices, determinants and inverses, 1.15 Eigenvalues and eigenvectors, 3.14 Graph theory basics and 3.15 Adjacency matrices and walks
Markov chains, transition diagrams and transition matrices
Each evening Priya cooks at home or eats out. Tomorrow depends only on today, not on earlier days. That makes it a Markov chain.
A transition diagram has one circle per state and a labelled arrow for each possible move. A loop is the probability of staying put.
The arrows leaving any state cover every possibility, so their probabilities add up to . Use this to find a missing label.
Use the same state order for rows and columns. Column lists the arrows leaving state . You met this layout for random walks in 3.15.
Try it first, then reveal one step at a time.
- Column H holds the arrows leaving H: stay at H , move to E .
- Column E holds the arrows leaving E: move to H , stay at E .
- Check: each column adds up to ( and ).
- Interpret: the entry in row H, column E is . If Priya eats out tonight, the probability she cooks at home tomorrow is .
Try it first, then reveal one step at a time.
- Column S: S to S , S to L , S to R . These add up to .
- Column L: L to S , L to L , L to R .
- Column R: R to S , R to R . There is no arrow from R to L, so that entry is .
- Check each column adds up to . Interpret: row L, column R is because a book is always shelved after a repair before it can be borrowed again.
Powers of T and the state after n steps
Where will Priya be in three days' time? Multiply by once for each day.
Write the probabilities of being in each state as a column, in the same order as . The is this column at the start. It could be certain, like , or proportions of a population, like .
One step gives . Then , and so on. Using the same at every step assumes the transition probabilities don't change over time.
This is in the formula booklet. The entries of each add up to , just like those of .
is a transition matrix too: is the probability of being in state after steps, starting from state . Find by , by hand for a small or with the GDC.
Try it first, then reveal one step at a time.
- Monday to Thursday is steps, and , so you need .
- .
- . Check: each column still adds up to .
- is the first column of . The probability she eats out on Thursday is its E entry, .
- Interpret: starting from a home-cooked Monday, she eats out on about of Thursdays.
Try it first, then reveal one step at a time.
- Read the model: each year of P's customers stay with P, move to Q and to R. Each column adds up to .
- Initial state: , so you need . Write this down: it earns the method mark.
- Store as matrix A and as matrix B. Calculate .
- The GDC gives . The entries add up to , as they should.
- Interpret: after years provider P has about of households, down from . Q and R have gained customers.
Store as a matrix B. In the multiply steps below, type where they say A, so you calculate , not .
Regular Markov chains
A zero in means one move is impossible in one step. It might still be possible in two or three steps. If there is one number of steps after which every state can be reached from every state, the chain is a .
If every entry of is already positive, the chain is regular (). If has zeros, work out and look for a power with no zeros.
Try it first, then reveal one step at a time.
- has zeros on its diagonal: the robot never stays in a room for two periods in a row.
- Row A of times column A of : . Work out the other entries the same way, or use the GDC.
- . Every column still adds up to .
- Every entry of is positive, so the chain is regular.
- Interpret: . Starting in room A, the robot is back in A after two moves with probability .
Try it first, then reveal one step at a time.
- Column D is : from D the user stays in D.
- So from D you can never reach A, in any number of steps. Check with : the zero is still there.
- In general , with a in row A, column D for every .
- Interpret: in the long term every user deletes the app. The chain still settles, but not because it is regular.
- Every power has a in row A, column D, because a user who has deleted the app can never become active again. So no power of has all its entries positive, and the chain is not regular.
Steady state and long-term probabilities
A column with never changes again. It is the steady state.
For a regular chain the steady state is unique, and it gives the long-term probabilities: the proportion of steps spent in each state in the long run, whatever the start.
There are two methods. 1. Repeated multiplication: raise to a high power, such as , on the GDC. For a regular chain every column of is close to . Check that gives the same values to the accuracy you need.
2. A : write out . One of these equations always follows from the others, so drop one and use instead. Solve by hand or with the GDC.
Use the equations when a question asks for an exact answer. The exam says when it wants one.
Try it first, then reveal one step at a time.
- Let . The top row of is , so .
- The bottom row, , gives the same equation. Use instead.
- Substitute : , so and .
- Check: , and .
- Interpret: in the long run Priya cooks at home on about of evenings. on the GDC agrees: both columns round to and .
Try it first, then reveal one step at a time.
- Let . Rows P and Q of : and .
- Rearranged: and . Add . Write this system down before using the GDC.
- The GDC gives , , .
- Check by repeated multiplication: every column of shows , and to 3 s.f., and agrees.
- Interpret: in the long run P keeps about of households, whatever the shares are now. Comment: this assumes the switching rates never change and no households join or leave, so treat it as a trend, not a forecast.
The steady state as an eigenvector
Look again at . It says , so is an of with . You found eigenvectors in 1.15.
To scale an eigenvector , divide each entry by . A GDC may give a unit eigenvector, or one with negative entries: dividing by the sum fixes both.
Every transition matrix has as an eigenvalue. In a regular chain the other eigenvalues have modulus less than , so their parts die away as grows. That is why settles at the steady state.
Try it first, then reveal one step at a time.
- Solve : , so . The second row says the same.
- , so . Take , : .
- Scale so the entries add up to : divide by .
- Check: .
- Interpret: in the long run the commuter cycles on of days, , and takes the bus on .
Try it first, then reveal one step at a time.
- This is a unit eigenvector: its length is , but its entries do not add up to .
- Sum of entries: . Keep the full values.
- Divide each entry by the sum: .
- On a TI-84 or Casio, which have no eigenvector command, find the same column from or by solving the linear equations.
- Interpret: in the long run the robot is in room B about of the time, the most of the three rooms.
Common mistakes
- Building with each row as “from”. In IB notation is the step from state to state , so each column adds up to ; check the column sums before you use .
- Giving a whole matrix such as when the question asks for the steady state. Give one column, with entries adding up to .
- Leaving an eigenvector unscaled. is not a steady state; divide by to get .
- Counting steps wrongly. From Monday to Thursday is transitions, so use , not .
- Rounding entries of or before using them again. Keep the GDC's full values and round only the final answer, in the form asked (for example, as a percentage).
- Stopping at a number when the question asks what it means. Say what the probability or proportion is about, in the context of the question.
Exam tips
- Write down : label the states in the same order for rows and columns, put each “from” state in a column, and check each column adds up to .
- Find a probability after steps: write with your matrices, then pick out the entry you need. The set-up earns the M mark even if a GDC slip loses the answer.
- Show that a given column is the only steady state: solve with the entries adding up to , and reach the given values. Checking alone does not show it is the only one.
- Interpret a steady state: give it as the long-term proportion or probability of each state, in context, for example “about of households use provider P in the long run”.
Key takeaways
Practise this
18 past-paper questions on Transition matrices and Markov chains in the AI HL bank, each with a mark scheme and a worked explanation.