Markov Chains & Transition Matrices: exam review Exam review: second paper Worked solutions

A runner plans each day to Run (R), Swim (S) or take a rest day (T). After a run, she swims the next day with probability 0.35 and rests with probability 0.25. After a swim, she runs the next day with probability 0.3 and swims again with probability 0.5. After a rest day, she never swims the next day, and she runs with probability 0.55. [6]

1. (a) (a) Write down the transition matrix, with the states in the order R, S, T. [4]

   • M1 for placing the given probabilities with each start state as a column
   • A1 for column R: \(1-0.35-0.25=0.4\), so \((0.4, 0.35, 0.25)\)
   • A1 for columns S and T: \((0.3, 0.5, 0.2)\) and \((0.55, 0, 0.45)\)
   • A1 for the matrix with every column adding to 1

2. (b) (b) Draw the transition diagram. [2]

   • A1 for all 8 non-zero entries drawn as arrows, loops included, and no arrow for a 0
   • A1 for every arrow in the right direction with its probability

A phone contract is Active (A), Paused (P) or Cancelled (X) at the start of each month. The transition diagram is shown. [7]

1. (a) (a) Write down the transition matrix, with the states in the order A, P, X. [3]

   • M1 for each start state as a column
   • A1 for the first two columns
   • A1 for the third column \((0,0,1)\)

2. (b) (b) Write down the absorbing state and say how the matrix shows it. [1]

   • A1 for X, with a 1 on the diagonal of its column (it never leaves)

3. (c) (c) A contract is active this month. Find the probability that the contract is cancelled after 4 months. [3]

   • M1 for using \(\mathbf{T}^{4}\)
   • M1 for the entry in column A, row X
   • A1 for 0.0825

Each day in a coastal town is either Wet (W) or Dry (D). The states in the order W, D have transition matrix \(\mathbf{T}=\begin{pmatrix}0.75 & 0.4 \\ 0.25 & 0.6\end{pmatrix}\) [6]

1. (a) (a) Today is dry. Find the probability that it is wet five days from now. [3]

   • M1 for using \(\mathbf{T}^{5}\)
   • M1 for the entry in column D, row W
   • A1 for 0.612

2. (b) (b) On a certain day there is a probability of 0.3 that the day is wet. Find the probability of each state four days later. [3]

   • M1 for \(\mathbf{s}_{4}=\mathbf{T}^{4}\mathbf{s}_0\) with \(\mathbf{s}_0=\begin{pmatrix}0.3 \\ 0.7\end{pmatrix}\)
   • A1 for \(\mathbf{T}^{4}=\begin{pmatrix}0.621 & 0.606 \\ 0.379 & 0.394\end{pmatrix}\)
   • A1 for 0.611 and 0.389

A chain of cafes has three branches, P, Q and R. Each month its regular customers choose a branch to visit. The transition matrix, with the branches in the order P, Q, R, is \(\mathbf{T}=\begin{pmatrix}0.6 & 0.15 & 0.2 \\ 0.25 & 0.7 & 0.1 \\ 0.15 & 0.15 & 0.7\end{pmatrix}\) [7]

1. (a) (a) Write down a system of three linear equations that the steady-state vector must satisfy. Use \(\mathbf{T}\mathbf{s}=\mathbf{s}\) and the fact that the shares add to 1. [2]

   • M1 for \(\mathbf{T}\mathbf{s}=\mathbf{s}\) written as equations in \(s_1, s_2, s_3\)
   • A1 for two correct row equations and \(s_1+s_2+s_3=1\)

2. (b) (b) Solve your system to find the exact steady-state vector. [3]

   • M1 for solving the system on the calculator
   • A1 for two correct fractions
   • A1 for \(\mathbf{s}=\begin{pmatrix}\frac{10}{33} \\ \frac{4}{11} \\ \frac{1}{3}\end{pmatrix}\)

3. (c) (c) The chain has 2400 regular customers. In the long term, how many visit branch P each month? Give your answer to the nearest whole number. [2]

   • M1 for \(2400\times \frac{10}{33}\)
   • A1 for 727 (nearest whole number; \(727.27\) before rounding)

A shop's customers pay each week by Card (C) or by Cash (H). The way a customer pays in one week depends only on the way they paid in the previous week. The transition diagram is shown. [6]

1. (a) (a) Write down the transition matrix, with the states in the order C, H. [2]

   • M1 for each start state as a column
   • A1 for the matrix with every column adding to 1

2. (b) (b) A customer pays by card in week 1. Find the probability that the customer pays cash in weeks 2 and 3 and by card in week 4. [2]

   • M1 for multiplying the three entries: C to H, H to H, H to C
   • A1 for 0.06

3. (c) (c) A customer pays by card in week 1. Find the probability that the customer pays cash in week 3. [2]

   • M1 for using \(\mathbf{T}^{2}\)
   • A1 for the entry in column C, row H: 0.338

The users of an app are either Active (A) or Inactive (I) each month. 70% of the users who are active in one month are active the next month. 40% of the users who are inactive in one month are active the next month. There are 500 users. This month 300 of them are active. [8]

1. (a) (a) Write down the transition matrix, with the states in the order A, I. [2]

   • M1 for each start state as a column
   • A1 for the second column found from \(1-0.4\) and \(1-0.7\) (columns add to 1)

2. (b) (b) Find the number of users expected to be active in 3 months' time. [2]

   • M1 for \(\mathbf{T}^{3}\) multiplied by the initial vector \(\begin{pmatrix}300\\200\end{pmatrix}\)
   • A1 for 286 in the first state

3. (c) (c) Use a high power of \(\mathbf{T}\) to find the number of users expected to be active in the long term. [2]

   • M1 for a high power of \(\mathbf{T}\) (such as \(\mathbf{T}^{200}\)) times the initial vector, until the values stop changing
   • A1 for 286

4. (d) (d) Show, by solving \(\mathbf{T}\mathbf{s}=\mathbf{s}\), that the long-term proportion in the first state is exactly \(\frac{4}{7}\). [2]

   • M1 for \(\mathbf{T}\mathbf{s}=\mathbf{s}\) with \(\mathbf{s}=\begin{pmatrix}x\\1-x\end{pmatrix}\), giving \(0.7x+0.4(1-x)=x\)
   • A1 for \(x=\frac{4}{7}\)

The water level in a reservoir is recorded each week as High (H), Medium (M) or Low (L). The level next week depends only on the level this week. After a High week, the next week is High with probability 0.6 and Medium with probability 0.3. After a Medium week, it is High with probability 0.25 and Low with probability 0.35. After a Low week, it is High with probability 0.15 and Medium with probability 0.35. [14]

1. (a) (a) Write down the transition matrix, with the states in the order H, M, L. [4]

   • M1 for each start state as a column
   • A1 for the first column
   • A1 for the second column
   • A1 for the third column (using column sums for the missing entry)

2. (b) (b) The level is medium this week. Find the probability that it is low three weeks from now. [2]

   • M1 for using \(\mathbf{T}^{3}\) and the entry in column M, row L
   • A1 for 0.325

3. (c) (c) At the start of the study the probabilities of a high, a medium and a low level are 0.2, 0.5 and 0.3. Find the probabilities of each level four weeks later. [3]

   • M1 for \(\mathbf{s}_{4}=\mathbf{T}^{4}\mathbf{s}_0\) with \(\mathbf{s}_0=\begin{pmatrix}0.2 \\ 0.5 \\ 0.3\end{pmatrix}\)
   • A1 for \(\mathbf{T}^{4}=\begin{pmatrix}0.358 & 0.33 & 0.32 \\ 0.348 & 0.352 & 0.353 \\ 0.294 & 0.318 & 0.327\end{pmatrix}\)
   • A1 for \(\begin{pmatrix}0.333 \\ 0.351 \\ 0.316\end{pmatrix}\)

4. (d) (d) Find the long-term matrix, giving its entries to 3 significant figures. [2]

   • M1 for a high power of \(\mathbf{T}\) such as \(\mathbf{T}^{100}\)
   • A1 for the matrix, with three identical columns

5. (e) (e) Write down the long-term percentage of weeks in which the level is low. [1]

   • A1 for 31.3% (first row of the long-term matrix, times 100)

6. (f) (f) Explain why every column of the long-term matrix is the same. [2]

   • R1 for the long-term probabilities do not depend on where the chain starts
   • R1 for every column being the steady-state vector

A robot moves along a track of five stations, numbered 0 to 4. Each hour it moves one station up with probability 0.4 and one station down with probability 0.6. Stations 0 and 4 are docks: once the robot is in one it stays there. The robot starts at station 3. [14]

1. (a) (a) Write down the two absorbing states and say what absorbing means. [2]

   • A1 for the two squares
   • A1 for it stays there once it is in (a 1 on the diagonal of its column)

2. (b) (b) Write down the transition matrix, with the stations in the order 0 to 4. [3]

   • M1 for each start square as a column
   • A1 for the two absorbing columns
   • A1 for the other three columns

3. (c) (c) Find the probability that the robot is at station 2 after 3 hours. [2]

   • M1 for \(\mathbf{T}^{3}\) and the entry in column 3, row 2
   • A1 for 0.288

4. (d) (d) Find the probability that the robot finishes at the dock at station 4. [3]

   • M1 for a high power of \(\mathbf{T}\), such as \(\mathbf{T}^{200}\), until the 3 significant figures stop changing
   • M1 for the entry in column 3, row 4
   • A1 for 0.585

5. (e) (e) Explain why this chain has no single steady state. [2]

   • R1 for the columns of a high power of \(\mathbf{T}\) are not all the same
   • R1 for the long-term probability depends on the starting square

6. (f) (f) 400 robots start at station 3. How many do you expect to finish at the dock at station 4? [2]

   • M1 for \(400\times 0.585\)
   • A1 for 234 (nearest whole number)

Each time a customer upgrades their phone they buy either an Android phone (A) or an iPhone (I). After owning an Android phone, 20% of customers switch to an iPhone at the next upgrade. After owning an iPhone, 30% of customers switch to an Android phone. There are no other makes. [15]

1. (a) (a) Write down the transition matrix \(\mathbf{T}\), with the states in the order A, I. [2]

   • M1 for each start state as a column
   • A1 for \(\mathbf{T}=\begin{pmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{pmatrix}\)

2. (b) (b) Find the eigenvalues of \(\mathbf{T}\). [3]

   • M1 for \(\det(\mathbf{T}-\lambda\mathbf{I})=0\): \((1-0.2-\lambda)(1-0.3-\lambda)-0.2\times0.3=0\)
   • A1 for \(\lambda=1\)
   • A1 for \(\lambda=0.5\)

3. (c) (c) Find an eigenvector for each eigenvalue. [3]

   • M1 for solving \((\mathbf{T}-\lambda\mathbf{I})\mathbf{v}=\mathbf{0}\)
   • A1 for an eigenvector for \(\lambda=1\): \(\begin{pmatrix}3 \\ 2\end{pmatrix}\)
   • A1 for an eigenvector for \(\lambda=0.5\): \(\begin{pmatrix}1 \\ -1\end{pmatrix}\)

4. (d) (d) Write down matrices \(\mathbf{P}\) and \(\mathbf{D}\) such that \(\mathbf{T}=\mathbf{PDP}^{-1}\), where \(\mathbf{D}\) is diagonal. [2]

   • A1 for \(\mathbf{P}=\begin{pmatrix}3 & 1 \\ 2 & -1\end{pmatrix}\) (eigenvectors as columns)
   • A1 for \(\mathbf{D}=\begin{pmatrix}1 & 0 \\ 0 & 0.5\end{pmatrix}\) in the same order

5. (e) (e) At the start, 45% of the customers own an Android phone. Use \(\mathbf{T}^n=\mathbf{P}\mathbf{D}^n\mathbf{P}^{-1}\) to find an expression for the proportion of Android owners after \(n\) upgrades. [3]

   • M1 for \(\mathbf{s}_n=\mathbf{P}\mathbf{D}^n\mathbf{P}^{-1}\mathbf{s}_0\) with \(\mathbf{s}_0=\begin{pmatrix}0.45 \\ 0.55\end{pmatrix}\)
   • A1 for \(\mathbf{D}^n=\begin{pmatrix}1 & 0 \\ 0 & (0.5)^n\end{pmatrix}\)
   • A1 for \(0.6-0.15(0.5)^n\)

6. (f) (f) Hence write down the long-term proportion of Android owners. [2]

   • M1 for \((0.5)^n\to 0\) as \(n\to\infty\)
   • A1 for 0.6

A warehouse has four zones, P, Q, R and S. Every hour each parcel stays in its zone or is moved to another zone. The probabilities of moving are known for a parcel in each zone. From P: to Q 0.25, to R 0.05, to S 0.2. From Q: to P 0.1, to R 0.3, to S 0.15. From R: to P 0.2, to Q 0.1, to S 0.3. From S: to P 0.25, to R 0.15, and never to Q. [12]

1. (a) (a) Write down the transition matrix, with the zones in the order P, Q, R, S. [3]

   • M1 for each start state as a column and a missing entry from a column sum
   • A1 for two columns correct
   • A1 for the matrix

2. (b) (b) A parcel is in zone P. Find the probability that it is in zone S four hours later. [2]

   • M1 for \(\mathbf{T}^{4}\)
   • A1 for the entry in column P, row S: 0.333

3. (c) (c) At 08:00 there are 500 parcels in zone P, 300 in Q, 100 in R and 200 in S. Find the number of parcels in each zone at 12:00, assuming the same 1100 parcels stay in the warehouse. [3]

   • M1 for \(\mathbf{s}_{4}=\mathbf{T}^{4}\mathbf{s}_0\) with \(\mathbf{s}_0=\begin{pmatrix}500 \\ 300 \\ 100 \\ 200\end{pmatrix}\)
   • A1 for correct values before rounding: \(\begin{pmatrix}310.6 \\ 190.3 \\ 220 \\ 379.1\end{pmatrix}\)
   • A1 for \(\begin{pmatrix}311 \\ 190 \\ 220 \\ 379\end{pmatrix}\)

4. (d) (d) Find the exact steady-state vector. [4]

   • M1 for \(\mathbf{T}\mathbf{s}=\mathbf{s}\) as equations in \(s_1, s_2, s_3, s_4\)
   • M1 for using \(s_1+s_2+s_3+s_4=1\) in place of one equation
   • M1 for solving on the calculator
   • A1 for \(\mathbf{s}=\begin{pmatrix}\frac{744}{2591} \\ \frac{430}{2591} \\ \frac{505}{2591} \\ \frac{912}{2591}\end{pmatrix}\)

A pupil travels to school each term by Walking (W), Cycling (C) or Scooter (S). The choice in one term depends only on the choice in the previous term. After walking, the pupil never walks again: she cycles with probability 0.7 and scoots otherwise. After cycling, she walks with probability 0.4 and cycles with probability 0.35. After scooting, she walks with probability 0.25 and cycles with probability 0.5. [9]

1. (a) (a) Write down the transition matrix, with the states in the order W, C, S. [3]

   • M1 for each given probability placed with the start state as a column
   • A1 for the column that is found by subtraction from 1
   • A1 for the matrix with every column adding to 1

2. (b) (b) Show that the chain is regular, and state the smallest power of \(\mathbf{T}\) with every entry positive. [2]

   • M1 for \(\mathbf{T}^{2}\) with every entry positive
   • A1 for 2 (\(\mathbf{T}\) itself has a zero entry, so 1 is not enough)

3. (c) (c) Find the eigenvalue 1 of \(\mathbf{T}\) and a corresponding eigenvector. Hence write down the steady state vector, giving its entries to 3 decimal places. [4]

   • M1 for using technology to find the eigenvalue 1 and its eigenvector
   • A1 for an eigenvector in proportion to (0.980, 1.824, 1.000)
   • M1 for dividing by the sum of its entries so the entries add to 1
   • A1 for (0.258, 0.480, 0.263)

A depot moves a delivery van between four sites, P, Q, R and S, every hour. The transition diagram is shown. [7]

1. (a) (a) Write down the transition matrix, with the states in the order P, Q, R, S. [3]

   • M1 for each start state as a column
   • A1 for three correct columns
   • A1 for the matrix with every column adding to 1

2. (b) (b) Find the probability that a van in S is in Q after 2 hours. [2]

   • M1 for using \(\mathbf{T}^{2}\) and the entry in column S, row Q
   • A1 for 0.15

3. (c) (c) Use technology to find the long-term probability that a van is in R. [2]

   • M1 for a high power of \(\mathbf{T}\) (such as \(\mathbf{T}^{200}\)) until the entries stop changing
   • A1 for 0.301