Transition matrices and Markov chains AI HL
A Markov chain moves between a fixed set of states with probabilities that depend only on the current state, and a transition matrix stores those probabilities with one column for each starting state. Multiplying the matrix by a column of probabilities gives the next state, so the state after any number of steps comes from a matrix power on the calculator, and the long-term behaviour comes from a steady-state vector that the chain no longer changes. The marks are for reading the matrix the right way round, setting up the product in the right order and reading the result. Work through the two sections in order, because the second uses the first.
Formulas at a glance
The booklet gives the state after transitions. The meaning of an entry of the matrix, the rule that each column sums to , the steady-state equation and the large-power method are not in it, so learn them.
State after transitions
In the bookletMeaning of an entry of the transition matrix
is the probability of moving from state to state
Not in the bookletA valid transition matrix
Each column of adds to
Not in the bookletSteady-state distribution
, with the entries of adding to
Not in the bookletSteady state by repeated multiplication
For a large power , every column of is close to
Not in the bookletWhich method to use
Decide first whether the question is about a particular number of steps or about the long run. A stated number of steps needs a matrix power; the long run needs the steady state.
| The question has | Use | Notes |
|---|---|---|
| Probabilities of moving between states, given in words or as a diagram | A transition matrix with the starting state as the column and the new state as the row | Each column adds to , so a missing entry is minus the others in its column |
| The state, or the share of each state, after a stated number of steps | in matrix mode | Raise the matrix to the power first, then multiply by the starting column on the right |
| The probability of one particular state after steps | The entry for that state in | When the chain starts in one state, has a single and the rest zero |
| The long-term probability of each state | The steady state , from with the entries adding to , or from a large power of | Give decimals unless the question asks for exact values |
| A check that a vector is the steady state | Multiply it by : it must come back unchanged, with its entries adding to | The steady state is the eigenvector of for the eigenvalue |
| A number of items, such as bikes or customers, rather than probabilities | Multiply the probability by the total number | Round to a whole number only at the end |
Section 1 of 2 AHL4.19
Markov chains
A Markov chain moves between states with fixed probabilities that depend only on the current state, and these probabilities are stored in a transition matrix whose columns each sum to . The state after steps is . Use it to predict how a system, such as the weather, changes step by step.
Key terms
What is an initial state vector?
The initial state is a column of the starting probabilities of each state, and its entries sum to . If the system definitely starts in one state, that entry is and the others are .
e.g. Starting in state 2 of three states gives .
How do you read an entry of a transition matrix?
Entry is the probability of moving from state to state . The column is where you start and the row is where you end.
e.g. In , the entry is the probability of moving from state 2 to state 1.
What is a transition diagram?
A transition diagram shows the states as points, with arrows labelled by the probabilities of each move. The probabilities on the arrows leaving each state sum to .
e.g. If state A has only two arrows leaving it, one to B labelled and a loop back to A, the loop is labelled .
How do you find a missing entry in a transition matrix?
Each column sums to , so subtract the other entries in that column from .
e.g. In the column , .
Worked example, step by step
The question Calculator needed (matrix mode) [5 marks]
A bike-share scheme has bikes and three docking stations: Harbour (H), Station (S) and University (U). Each evening every bike is at one of the three stations. From one evening to the next, the probabilities of a bike moving between stations are given by the transition matrix where the columns are the station a bike is at (in the order H, S, U) and the rows are the station it is at the next evening (in the same order). On Sunday evening, of the bikes are at H, at S and at U.
(a) Write down the probability that a bike at S on one evening is at U the next evening.
(b) Find the proportion of the bikes at each station on Tuesday evening.
(c) Find the number of bikes expected at U on Tuesday evening, to the nearest whole number.
Worked solution: worked example
Answer: (a) (b) at H, at S, at U (c) bikes
Step 1 - Read the entry.
The columns give the starting station and the rows the new station. S is the second column and U is the third row, so A1 -
Why? The entry is the probability of moving from state to state . Reading along the row instead of down the column would give the probability of arriving at S from U, which is .
Step 2 - Set up the calculation.
The starting state is , and Tuesday is two evenings after Sunday, so M1 - Use with the starting column on the right
Why? The shares add to , as they must. The matrix acts on the column from the left, and the power is taken before the multiplication.
Step 3 - Enter the matrices.
In matrix mode, store as a matrix and as a matrix, then enter . The calculator shows A1 -
Why? Check that the three entries add to : . If they do not, a column of has probably been typed in as a row.
Step 4 - Convert to a number of bikes.
The share at U is , so the expected number at U is M1 - Multiply the share at U by
Why? A proportion of the whole fleet is the proportion times the total. The answer is not a whole number yet, so the rounding comes in the next step.
Step 5 - Give a whole number.
Bikes are counted in whole numbers, so about bikes are expected at U. A1 - bikes
Why? The answer is rounded only at the end, after the multiplication.
A1
M1 Use with the starting column on the right
A1
M1 Multiply the share at U by
A1 bikes
Now you try: enter your answers to be marked
These are real practice questions. Type your answer in each box and press Mark it. The worked solution and mark scheme appear straight away, and your first attempt is the one that counts. Use the keyboard for powers, roots and trig, and the working box for your notes.
Worked solution: practice question 1
Find
Worked solution: practice question 2
Find each share after 2 periods.
Worked solution: practice question 3
Your score so far: 0 out of 9 marks
Calculator steps: Matrix powers (transition / Markov chains), Matrix operations and solving systems
Common mistakes
- Mixing up rows and columns. is the probability of moving from state (the column) to state (the row) - reading a transition matrix the wrong way round reverses every probability in the model.
- Building rows that sum to 1 instead of columns. With the IB's convention, it's each column of that must sum to 1, not each row - a matrix built the other way round will look plausible but give the wrong answer at every step.
- Multiplying in the wrong order. means acts on the state vector, so it's , not - matrix multiplication isn't commutative, so reversing the order gives nonsense (or an error) on the calculator.
Section 2 of 2 AHL4.19
Steady state and equilibrium
A steady state is a probability vector that is unchanged by a transition, so , and whose entries sum to . To find it, solve the equations from together with the sum condition, or raise to a high power. It gives the long-term probability of being in each state.
Key terms
What is a regular Markov chain?
A regular chain has some power of its transition matrix with every entry positive. A regular chain settles to a single steady state whatever the starting state.
e.g. is regular because every entry is already positive.
What does the long-term probability mean?
It is the probability of being in each state after many transitions. For a regular chain it does not depend on the initial state.
e.g. A steady state of means that in the long run the system is in the first state of the time.
Why is the eigenvalue 1 involved?
The equation says that is an eigenvector of with eigenvalue . Find that eigenvector, then scale it so its entries sum to .
e.g. An eigenvector has entries summing to , so the steady state is .
How can repeated multiplication show the steady state?
Raising to a large power makes every column of approach the steady state. Multiplying by any initial state with entries summing to then gives that same vector.
e.g. If every column of is close to , the steady state is approximately .
Worked example, step by step
The question Calculator needed (matrix mode) [5 marks]
At the start of each day a machine is found to be working (W), under maintenance (M) or broken (B). The transition matrix for one day to the next is where the columns are today's state and the rows are tomorrow's state, both in the order W, M, B.
(a) Find the steady-state distribution, giving each probability to 3 significant figures.
(b) The machine is checked on days in a year. Find the number of those days on which it is expected to be broken, to 3 significant figures.
Worked solution: worked example
Answer: (a) (b) days
Step 1 - Choose the method.
The steady state is the vector that leaves unchanged, , with entries adding to . Every entry of is positive, so the chain is regular and every column of settles to . Use a large power of , such as . M1 - Use a large power of , or solve with the entries adding to
Why? A regular chain reaches the same steady state from every starting state, so the columns of a high power are all the same. Solving with the sum condition gives the same vector.
Step 2 - Calculate the power.
In matrix mode, enter . Every column shows , and . So the probabilities of working and of maintenance are and . A1 - and
Why? The columns agree to more than three significant figures, so the power is large enough. A larger power would not change the answer.
Step 3 - Read the third entry and check.
The probability of being broken is . The three unrounded entries add to , and as a check on the calculator returns the same vector. A1 - , with the three entries adding to
Why? The entries of a probability vector add to ; the rounded values give , which is to the accuracy used. The vector is also an eigenvector of for the eigenvalue , which is why it is unchanged by .
Step 4 - Find the expected number of days.
The expected number of days broken is using the unrounded value of the probability from the calculator. M1 - Multiply the probability of being broken by
Why? In the long run the machine is broken on a fraction of days, so the expected number of days is that fraction of . Using the unrounded value keeps the third significant figure safe.
Step 5 - Round.
A1 - days
Why? The question asks for 3 significant figures. An expected number need not be a whole number.
M1 Use a large power of , or solve with the entries adding to
A1 and
A1 , with the three entries adding to
M1 Multiply the probability of being broken by
A1 days
Now you try: enter your answers to be marked
Worked solution: practice question 1
Worked solution: practice question 2
Find the steady-state distribution.
Worked solution: practice question 3
Your score so far: 0 out of 7 marks
Calculator steps: Matrix powers (transition / Markov chains), Eigenvalues and eigenvectors
Common mistakes
- Forgetting the normalisation condition. The equation alone only fixes the ratio between the state probabilities - you still need to pin down exact values, not just a proportional relationship.
- Rounding the steady state before scaling it. When a long-term probability is multiplied by a total, such as a number of days or customers, use the unrounded value from the calculator. Rounding first and multiplying by a large total can change the third significant figure.
- Reading the steady state from a power that has not settled. Raise to a power large enough that the columns agree to the accuracy you need, such as . Examination questions state when an exact answer is required: then solve with the entries adding to and keep fractions.
Using your GDC
The exact key presses for the TI-84 Plus CE, Casio fx-CG50, Casio fx-CG100 and TI-Nspire CX, with what the screen shows. Pick your calculator.
Matrix powers (transition / Markov chains)
Used in: Markov chains, Steady state and equilibrium
How to raise a matrix to a power on a TI-84 Plus CE
The state after n steps | |
Enter the transition matrix as [A], with the same layout as in the question (each column adds to 1), and the starting state as a one-column matrix [B]. For the example, [A] is 2 × 2 with rows 0.7 0.4 and 0.3 0.6, and [B] is 2 × 1 holding 200 and 100. The steps for the matrix editor are in matrix operations and solving systems. |
|
Press 2nd mode (QUIT) to return to the home screen. Press 2nd x⁻¹ (MATRIX) and choose 1:[A] from the NAMES list. The name must be pasted from this list, because it cannot be typed. Then press ^ 4 ×, press 2nd x⁻¹ (MATRIX) again and choose 2:[B]. |
[A]^4*[B] |
Press enter. The answer is a column holding the number in each state after 4 steps. After 4 weeks there are customers of P and of Q. |
[A]^4*[B] [[171.66] [128.34]] |
The long-term state | |
Use the same entry with a large power. Press 2nd enter (ENTRY) to bring the last line back, change the 4 to 50, and press enter. The numbers settle at and , which is and to 3 significant figures. |
[A]^50*[B] [[171.4285714] [128.5714286]] |
To see the long-term proportions, enter [A]^50 on its own: every column is the same, and each column is the steady state. The power can be any whole number from 0 to 255. | |
Check the answer by adding the two numbers: they should still total the starting number, here 300. If they do not, the columns of the matrix probably do not add to 1.
The full guide: Matrix powers (transition / Markov chains)
Matrix operations and solving systems
Used in: Markov chains
How to use matrices on a TI-84 Plus CE
Enter a matrix | |
Press 2nd x⁻¹ (MATRIX), press ▶ twice to reach EDIT, choose 1:[A] and press enter. Type the size, 2 enter 2 enter for 2 rows and 2 columns, then type the numbers row by row, pressing enter after each one. Use (−) for a negative number. |
MATRIX[A] 2 ×2 [[2 1] [1 3]] |
Enter the second matrix the same way in 2:[B] and the right-hand side as a 2 by 1 matrix in 3:[C]. Press 2nd mode (QUIT) when you have finished. |
MATRIX[C] 2 ×1 [[5] [10]] |
Add, multiply, determinant and inverse | |
On the home screen press 2nd x⁻¹ (MATRIX), choose 1:[A] from the NAMES list and press enter. Then press +, paste [B] in the same way, and press enter. A matrix name can only be pasted from this menu, not typed. Use × instead of + to multiply. and . |
[A]+[B] [[3 3] [4 7]] [A]*[B] [[5 8] [10 14]] |
For the determinant, press 2nd x⁻¹ (MATRIX), press ▶ to reach MATH, choose 1:det(, paste [A] from NAMES, type ) and press enter. . |
det([A]) 5 |
For the inverse, paste [A], press x⁻¹, then enter. The answer is in decimals. To see fractions, press math, choose 1:▶Frac and press enter. , which is in decimal form. |
[A]-1 [[0.6 −0.2] [−0.2 0.4]] Ans▶Frac [[3/5 −1/5] [−1/5 2/5]] |
Solve a system with the inverse | |
To solve , paste [A], press x⁻¹, then ×, paste [C] and press enter. The inverse must come first: is not the same as . and . |
[A]-1*[C] [[1] [3]] |
Paste matrix names from the MATRIX menu rather than typing them, and put the inverse on the left when you solve a system.
The full guide: Matrix operations and solving systems
Eigenvalues and eigenvectors
Used in: Steady state and equilibrium
How to find eigenvalues and eigenvectors on a TI-84 Plus CE
No eigenvalue command: characteristic equation and rref | |
Press 2nd x⁻¹ (MATRIX), press ▶ to the EDIT menu and choose 1:[A]. Enter the size, 2 enter 2 enter, then the entries row by row, pressing enter after each: 6, 2, 1, 5. Press 2nd mode (QUIT) to leave the editor. |
MATRIX[A] 2 ×2 [ 6 2 ] [ 1 5 ] |
The manual lists no eigenvalue or eigenvector command for this calculator, so the eigenvalues come from the characteristic equation. For a matrix it is . Here the trace is and the determinant is , so it is . Press apps and choose PlySmlt2, press any key, then choose 1:Polynomial Root Finder. Set ORDER to 2, press graph under NEXT, and enter the coefficients 1 enter, (−) 1 1 enter, 2 8 enter. Press graph under SOLVE. The eigenvalues are and . |
X1=4 X2=7 |
For an eigenvector, row-reduce . Quit the app, then on the home screen press 2nd x⁻¹ (MATRIX), ▶ to MATH, and choose B:rref(. Type [A] from 2nd x⁻¹ (MATRIX) 1:[A], then − 7 ×, and choose 5:identity( from the same MATH menu, followed by 2 ) ) and enter. This is rref([A]-7*identity(2)) for . Each row of the result is an equation in and . means , so and an eigenvector for is . Repeat with in place of : the result means , so an eigenvector is . |
rref([A]-7*identity(2)) [[1 -2] [0 0]] |
Any non-zero multiple of an eigenvector is also an eigenvector, so (2, 1) and (4, 2) are equally correct. The identity size must match the matrix: identity(2) for a 2 by 2.
The full guide: Eigenvalues and eigenvectors
See the full list of GDC guides for every calculator task.
Syllabus content covered
| 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 after transitions is given by , where is the transition matrix (with the probability of moving from state to state ) and 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 . |
Official IB source: Mathematics: applications and interpretation subject brief (PDF, ibo.org).
Quick questions
What is a transition matrix in a Markov chain?
A square matrix where entry is the probability of moving from state (the column) to state (the row) in one step - every column must sum to 1.
What is the steady-state distribution of a Markov chain?
The state vector that satisfies and sums to 1 - once the system reaches it, further transitions leave the distribution unchanged.
How do you find the state after n transitions?
, where is the initial state (probability) vector - raise to the power and multiply by , usually done in the calculator's matrix mode.
How do you find a steady-state distribution by hand?
Set , write the resulting equations, add the normalisation condition that the entries of sum to 1, then solve the system - or raise to a high power on the calculator and read off the converged columns.
What does the Markov property mean?
The probability of the next state depends only on the current state, not on any of the earlier states.
Does the steady state depend on the starting state?
For a regular chain it does not. Any initial state leads to the same long-term probabilities, although the number of steps needed to get close may differ.
How do I find the probability of being in a state after 2 steps?
Calculate and read the entry for that state. You can also find first and then .
How do I solve for the steady state of a 2 by 2 matrix by hand?
Write , form , and solve one of the equations for . Using the sum condition leaves only one unknown.
Can the rows of the transition matrix sum to 1 instead?
In the IB convention the columns sum to and the state is a column, so . Mixing this with a matrix whose rows sum to changes the order of multiplication, so keep to one convention.
How can I check my steady state is correct?
Multiply by your vector: the result must be the same vector, and its entries must sum to . Both checks together confirm the answer.
Ready to practise properly?
Practice questions on every section, marked instantly like the real exam.