4.19 · AHL · HL onlyPaper 1Paper 2Paper 3

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 TT holds the step probabilities, and sn=Tns0\boldsymbol{s}_n = T^{n}\boldsymbol{s}_0 predicts the state after nn steps. The , an of TT for the 11, 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 sn=Tns0\boldsymbol{s}_n = T^{n}\boldsymbol{s}_0 to find probabilities after nn 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
Check yourself
Find (0.50.20.50.8)(1020)\begin{pmatrix}0.5 & 0.2\\0.5 & 0.8\end{pmatrix}\begin{pmatrix}10\\20\end{pmatrix}.
Check yourself
M=(0.60.20.40.8)M = \begin{pmatrix}0.6 & 0.2\\0.4 & 0.8\end{pmatrix} and v=(12)\boldsymbol{v} = \begin{pmatrix}1\\2\end{pmatrix}. Mv=λvM\boldsymbol{v} = \lambda\boldsymbol{v}. Find λ\lambda.
Check yourself
Solve 0.3x=0.5y0.3x = 0.5y and x+y=1x + y = 1 for xx.

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 11. Use this to find a missing label.

Use the same state order for rows and columns. Column jj lists the arrows leaving state jj. You met this layout for random walks in 3.15.

Transition diagram with two states, H for cooking at home and E for eating out. A loop on H is labelled 0.75 and a loop on E is labelled 0.6. An arrow from H to E is labelled 0.25 and an arrow from E to H is labelled 0.4. H E 0.25 0.4 0.75 0.6
Priya's evenings: H is home, E is eating out.
Worked exampleThe diagram shows how Priya's evening choice changes from one day to the next. Write down the transition matrix TT, with the states in the order H, E.

Try it first, then reveal one step at a time.

  1. Column H holds the arrows leaving H: stay at H 0.750.75, move to E 0.250.25.
Transition diagram with three states: S on the shelf, L on loan and R in repair. Loops: S 0.6, L 0.45, R 0.3. Arrows: S to L 0.38, L to S 0.5, S to R 0.02, R to S 0.7, L to R 0.05. There is no arrow from R to L. S L R 0.38 0.5 0.02 0.7 0.05 0.6 0.45 0.3
A library book's state from one day to the next.
Worked exampleA library tracks one copy of a popular book each day. It is on the shelf (S), on loan (L) or in repair (R). The diagram shows the daily transitions. Write down the transition matrix TT, in the order S, L, R.

Try it first, then reveal one step at a time.

  1. Column S: S to S 0.60.6, S to L 0.380.38, S to R 0.020.02. These add up to 11.
Check yourself
In the library book's matrix, what does the entry 0.050.05 in row R, column L mean?
Check yourself
A town's weather is sunny, cloudy or rainy each day. In its transition diagram, the arrows leaving cloudy are: to sunny 0.250.25, a loop on cloudy 0.450.45, and to rainy qq. Find qq.

Powers of T and the state after n steps

Where will Priya be in three days' time? Multiply by TT once for each day.

Write the probabilities of being in each state as a column, in the same order as TT. The s0\boldsymbol{s}_0 is this column at the start. It could be certain, like (10)\begin{pmatrix}1\\0\end{pmatrix}, or proportions of a population, like (0.50.30.2)\begin{pmatrix}0.5\\0.3\\0.2\end{pmatrix}.

One step gives s1=Ts0\boldsymbol{s}_1 = T\boldsymbol{s}_0. Then s2=Ts1=T2s0\boldsymbol{s}_2 = T\boldsymbol{s}_1 = T^{2}\boldsymbol{s}_0, and so on. Using the same TT at every step assumes the transition probabilities don't change over time.

In the formula booklet
Tns0=sn,where s0 is the initial stateT^{n}\boldsymbol{s}_0 = \boldsymbol{s}_n, \quad \text{where } \boldsymbol{s}_0 \text{ is the initial state}

This is in the formula booklet. The entries of each sn\boldsymbol{s}_n add up to 11, just like those of s0\boldsymbol{s}_0.

TnT^{n} is a transition matrix too: (Tn)ij(T^{n})_{ij} is the probability of being in state ii after nn steps, starting from state jj. Find TnT^{n} by , by hand for a small nn or with the GDC.

Worked examplePriya cooks at home on Monday evening. Use T=(0.750.40.250.6)T = \begin{pmatrix}0.75 & 0.4\\0.25 & 0.6\end{pmatrix} (order H, E) to find the probability that she eats out on Thursday evening.

Try it first, then reveal one step at a time.

  1. Monday to Thursday is 33 steps, and s0=(10)\boldsymbol{s}_0 = \begin{pmatrix}1\\0\end{pmatrix}, so you need T3s0T^{3}\boldsymbol{s}_0.
Worked exampleHouseholds in a city use one of three broadband providers, P, Q and R. Each year, the switching between them is modelled by T=(0.820.060.150.10.870.050.080.070.8)T = \begin{pmatrix}0.82 & 0.06 & 0.15\\0.1 & 0.87 & 0.05\\0.08 & 0.07 & 0.8\end{pmatrix} (order P, Q, R). This year the market shares are 50%50\%, 30%30\% and 20%20\%. Use your GDC to find provider P's share after 44 years, to 3 s.f.

Try it first, then reveal one step at a time.

  1. Read the model: each year 82%82\% of P's customers stay with P, 10%10\% move to Q and 8%8\% to R. Each column adds up to 11.

Store s0\boldsymbol{s}_0 as a 3×13 \times 1 matrix B. In the multiply steps below, type A4A^{4} where they say A, so you calculate A4BA^{4}B, not ABAB.

Check yourself
Priya eats out tonight. Using the same TT, find the probability that she eats out on each of the next 33 evenings.
Check yourself
Commuters drive (D) or take the train (R). Each month T=(0.930.140.070.86)T = \begin{pmatrix}0.93 & 0.14\\0.07 & 0.86\end{pmatrix} (order D, R). This month 42%42\% drive. Assuming the model held last month too, find the proportion who drove last month, to 3 s.f.

Regular Markov chains

A zero in TT 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 TT is already positive, the chain is regular (k=1k = 1). If TT has zeros, work out T2,T3,…T^{2}, T^{3}, \ldots and look for a power with no zeros.

Worked exampleA robot vacuum cleans three rooms, A, B and C, and moves to a different room every 1515 minutes. Its moves follow T=(00.50.40.700.60.30.50)T = \begin{pmatrix}0 & 0.5 & 0.4\\0.7 & 0 & 0.6\\0.3 & 0.5 & 0\end{pmatrix} (order A, B, C). Find T2T^{2} and hence show that the chain is regular. Write down the probability that the robot is back in room A two moves after leaving it.

Try it first, then reveal one step at a time.

  1. TT has zeros on its diagonal: the robot never stays in a room for two periods in a row.
Worked exampleA study tracks users of a fitness app each week. An active user deletes the app with probability 0.20.2, and a user who deletes it never comes back. With states D (deleted) and A (active), T=(10.200.8)T = \begin{pmatrix}1 & 0.2\\0 & 0.8\end{pmatrix}. Explain why this Markov chain is not regular.

Try it first, then reveal one step at a time.

  1. Column D is (10)\begin{pmatrix}1\\0\end{pmatrix}: from D the user stays in D.
Check yourself
Which of these transition matrices are regular? X=(0.510.50)X = \begin{pmatrix}0.5 & 1\\0.5 & 0\end{pmatrix} and Y=(10.300.7)Y = \begin{pmatrix}1 & 0.3\\0 & 0.7\end{pmatrix}.
Check yourself
For the library book, with T=(0.60.50.70.380.4500.020.050.3)T = \begin{pmatrix}0.6 & 0.5 & 0.7\\0.38 & 0.45 & 0\\0.02 & 0.05 & 0.3\end{pmatrix} (order S, L, R), find the probability that a book in repair today is on loan two days later.

Steady state and long-term probabilities

A column s\boldsymbol{s} with Ts=sT\boldsymbol{s} = \boldsymbol{s} 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.

Learn this
Ts=s,s1+s2+⋯+sk=1T\boldsymbol{s} = \boldsymbol{s}, \quad s_1 + s_2 + \cdots + s_k = 1

There are two methods. 1. Repeated multiplication: raise TT to a high power, such as T50T^{50}, on the GDC. For a regular chain every column of TnT^{n} is close to s\boldsymbol{s}. Check that T51T^{51} gives the same values to the accuracy you need.

2. A : write out Ts=sT\boldsymbol{s} = \boldsymbol{s}. One of these equations always follows from the others, so drop one and use s1+⋯+sk=1s_1 + \cdots + s_k = 1 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.

Worked exampleFor Priya's evenings, T=(0.750.40.250.6)T = \begin{pmatrix}0.75 & 0.4\\0.25 & 0.6\end{pmatrix} (order H, E). Find the exact long-term probability that she cooks at home.

Try it first, then reveal one step at a time.

  1. Let s=(he)\boldsymbol{s} = \begin{pmatrix}h\\e\end{pmatrix}. The top row of Ts=sT\boldsymbol{s} = \boldsymbol{s} is 0.75h+0.4e=h0.75h + 0.4e = h, so 0.4e=0.25h0.4e = 0.25h.
Worked exampleFor the broadband providers, T=(0.820.060.150.10.870.050.080.070.8)T = \begin{pmatrix}0.82 & 0.06 & 0.15\\0.1 & 0.87 & 0.05\\0.08 & 0.07 & 0.8\end{pmatrix} (order P, Q, R). Find the long-term market share of provider P, to 3 s.f. Comment on the model.

Try it first, then reveal one step at a time.

  1. Let s=(pqr)\boldsymbol{s} = \begin{pmatrix}p\\q\\r\end{pmatrix}. Rows P and Q of Ts=sT\boldsymbol{s} = \boldsymbol{s}: 0.82p+0.06q+0.15r=p0.82p + 0.06q + 0.15r = p and 0.1p+0.87q+0.05r=q0.1p + 0.87q + 0.05r = q.
Check yourself
A streaming service's customers are subscribed (S) or cancelled (C) each month, with T=(0.90.350.10.65)T = \begin{pmatrix}0.9 & 0.35\\0.1 & 0.65\end{pmatrix} (order S, C). Find the long-term proportion of customers who are subscribed, to 3 s.f.
Check yourself
A café regular orders tea or coffee each visit, with T=(0.80.50.20.5)T = \begin{pmatrix}0.8 & 0.5\\0.2 & 0.5\end{pmatrix} (order tea, coffee). Which is the steady state?

The steady state as an eigenvector

Look again at Ts=sT\boldsymbol{s} = \boldsymbol{s}. It says Ts=1sT\boldsymbol{s} = 1\boldsymbol{s}, so s\boldsymbol{s} is an of TT with 11. You found eigenvectors in 1.15.

To scale an eigenvector (ab)\begin{pmatrix}a\\b\end{pmatrix}, divide each entry by a+ba + b. A GDC may give a unit eigenvector, or one with negative entries: dividing by the sum fixes both.

Every transition matrix has 11 as an eigenvalue. In a regular chain the other eigenvalues have modulus less than 11, so their parts die away as nn grows. That is why Tns0T^{n}\boldsymbol{s}_0 settles at the steady state.

Worked exampleA commuter cycles (C) or takes the bus (B) each day, with T=(0.70.180.30.82)T = \begin{pmatrix}0.7 & 0.18\\0.3 & 0.82\end{pmatrix} (order C, B). Find an eigenvector of TT for the eigenvalue 11. Hence find the steady state, and interpret it.

Try it first, then reveal one step at a time.

  1. Solve (T−I)v=0(T - I)\boldsymbol{v} = \boldsymbol{0}: T−I=(−0.30.180.3−0.18)T - I = \begin{pmatrix}-0.3 & 0.18\\0.3 & -0.18\end{pmatrix}, so −0.3x+0.18y=0-0.3x + 0.18y = 0. The second row says the same.
Worked exampleFor the robot vacuum, T=(00.50.40.700.60.30.50)T = \begin{pmatrix}0 & 0.5 & 0.4\\0.7 & 0 & 0.6\\0.3 & 0.5 & 0\end{pmatrix} (order A, B, C). A TI-Nspire gives this eigenvector for the eigenvalue 11: (0.538956…0.677545…0.500459…)\begin{pmatrix}0.538956\ldots\\0.677545\ldots\\0.500459\ldots\end{pmatrix}. Find the long-term proportion of time the robot spends in room B, to 3 s.f.

Try it first, then reveal one step at a time.

  1. This is a unit eigenvector: its length is 11, but its entries do not add up to 11.
Check yourself
Readers of a news site use its app (X) or its website (Y). An eigenvector of the transition matrix for the eigenvalue 11 is (49)\begin{pmatrix}4\\9\end{pmatrix} (order X, Y). Find the long-term proportion of readers using the app, to 3 s.f.
Check yourself
A GDC gives (−0.6−0.8)\begin{pmatrix}-0.6\\-0.8\end{pmatrix} as an eigenvector of a 2×22 \times 2 transition matrix for the eigenvalue 11. What is the steady state?

Common mistakes

  • Building TT with each row as “from”. In IB notation TijT_{ij} is the step from state jj to state ii, so each column adds up to 11; check the column sums before you use TT.
  • Giving a whole matrix such as T50T^{50} when the question asks for the steady state. Give one column, with entries adding up to 11.
  • Leaving an eigenvector unscaled. (35)\begin{pmatrix}3\\5\end{pmatrix} is not a steady state; divide by 3+53 + 5 to get (3858)\begin{pmatrix}\frac{3}{8}\\\frac{5}{8}\end{pmatrix}.
  • Counting steps wrongly. From Monday to Thursday is 33 transitions, so use T3T^{3}, not T4T^{4}.
  • Rounding entries of TnT^{n} or sn\boldsymbol{s}_n 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 TT: 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 11.
  • Find a probability after nn steps: write sn=Tns0\boldsymbol{s}_n = T^{n}\boldsymbol{s}_0 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 Ts=sT\boldsymbol{s} = \boldsymbol{s} with the entries adding up to 11, and reach the given values. Checking Ts=sT\boldsymbol{s} = \boldsymbol{s} 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 35%35\% of households use provider P in the long run”.

Key takeaways

In bookletTns0=sn,where s0 is the initial stateT^{n}\boldsymbol{s}_0 = \boldsymbol{s}_n, \quad \text{where } \boldsymbol{s}_0 \text{ is the initial state}
Learn thisTransition matrix: TijT_{ij} is the chance of going to state ii at the next step, given the chain is in state jj now, so each column adds up to 11. Columns are “from”, rows are “to”.
Learn thisIn a transition diagram the probabilities on the arrows leaving any one state, including its loop, add up to 11.
Learn this(Tn)ij(T^{n})_{ij} is the probability of being in state ii after nn steps, starting in state jj. A probability along one fixed path is a product of single-step probabilities instead.
Learn thisA Markov chain is regular when some power of TT has all its entries positive. Then the columns of TnT^{n} all approach the steady state, whatever the start.
Learn thisSteady state s\boldsymbol{s}: Ts=sT\boldsymbol{s} = \boldsymbol{s} with entries adding up to 11. For a regular chain it is unique: find it from a column of a high power of TT, or exactly by solving Ts=sT\boldsymbol{s} = \boldsymbol{s} with one equation replaced by the sum =1= 1.
Learn thisA steady state is an eigenvector of TT for the eigenvalue 11, divided by the sum of its entries. For a regular chain there is only one.

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.

Practise Transition matrices and Markov chains →