Markov chain problems, absorbing states and eigenvalues Problem set A One question at a time

Members of a town library choose one of three branches each week: Main (M), Central (C) or South (S). The transition diagram shows the probabilities of changing branch from one week to the next. Write down the transition matrix.

• Read the arrows leaving each state to fill each column. A missing arrow is 0.
• column M: M to M 0.6, M to C 0.4, M to S 0; column C: C to M 0.2, C to C 0.6, C to S 0.2; column S: S to M 0.1, S to C 0, S to S 0.9.
• Check each column sums to 1.

A frog sits on one of three lily pads, A, B or C. Each minute it moves according to the transition matrix \(T=\begin{pmatrix}0.46 & 0.28 & 0 \\ 0.54 & 0.22 & 0.64 \\ 0 & 0.5 & 0.36\end{pmatrix}\) (columns and rows in the order A, B, C). Draw the transition diagram, with the probability on each arrow.

• One vertex for each state.
• Diagonal entries are loops: loop at A 0.46; loop at B 0.22; loop at C 0.36.
• Other non-zero entries are arrows from the column state to the row state: A to B 0.54; B to A 0.28; B to C 0.5; C to B 0.64.
• No arrow for the zero entries (A to C, C to A). Labels leaving each vertex sum to 1.

A train is On time (O) or Late (L) each day. If it is on time today, the probability that it is on time tomorrow is 0.85. If it is late today, the probability that it is on time tomorrow is 0.35. Write down the transition matrix, with states in the order O, L.

• Column O (on time today): on time 0.85, so late \(1-0.85=0.15\).
• Column L (late today): on time 0.35, so late \(1-0.35=0.65\).
• Each column sums to 1.

A hiker spends each night at one of three huts, A, B or C. Where she spends tomorrow night depends only on where she spends tonight, with transition matrix \(T=\begin{pmatrix}0.42 & 0.28 & 0.12 \\ 0.38 & 0.52 & 0.36 \\ 0.2 & 0.2 & 0.52\end{pmatrix}\) (columns and rows in the order A, B, C).

1. (a) She is at hut A on Monday night. Find the probability that she is at hut C on Wednesday night.

   • From the calculator: \(T^2=\begin{pmatrix}0.307 & 0.287 & 0.214 \\ 0.429 & 0.449 & 0.42 \\ 0.264 & 0.264 & 0.366\end{pmatrix}\)
   • Start A is column A, end C is row C.
   • \(P=0.264\)

2. (b) She is at hut B on Monday night. Find the probability that she is at hut B on Wednesday night.

   • From the calculator: \(T^2=\begin{pmatrix}0.307 & 0.287 & 0.214 \\ 0.429 & 0.449 & 0.42 \\ 0.264 & 0.264 & 0.366\end{pmatrix}\)
   • Start B is column B, end B is row B.
   • \(P=0.449\)

Each day a commuter travels by Train or by Bus. The transition matrix is \(T=\begin{pmatrix}0.85 & 0.3 \\ 0.15 & 0.7\end{pmatrix}\) (columns and rows in the order Train, Bus). In the long term the proportions of days by train and by bus are \(x\) and \(y\).

1. (a) Write down a system of equations for the long-term proportions.

   • Ts = s gives one equation for each row.
   • 0.85x + 0.3y = x; 0.15x + 0.7y = y
   • Add that the proportions sum to 1: x+y=1.

2. (b) Solve the equations to find the exact long-term proportions.

   • Use one tidied equation: 0.3y = 0.15x.
   • Substitute into x+y=1 and solve.
   • \(x=\frac{2}{3},\ y=\frac{1}{3}\)
   • As decimals: 0.667 and 0.333.

A phone company has 1000 customers, each on the Basic (B), Standard (S) or Premium (P) plan. Each month, of the customers on Basic, 70% stay and 20% move to Standard (the rest move to Premium). Of the customers on Standard, 10% move to Basic and 60% stay. Of the customers on Premium, none move to Basic and 80% stay. Initially 500 customers are on Basic, 300 on Standard and 200 on Premium.

1. (a) Write down the transition matrix T, with the states in the order B, S, P.

   • Column B: 0.7 stay, 0.2 to S, so 0.1 to P. Column S: 0.1 to B, 0.6 stay, so 0.3 to P. Column P: 0 to B, 0.8 stay, so 0.2 to S.
   • Check each column sums to 1.

2. (b) Find the number of customers on each plan after 6 months. Give each answer to the nearest whole number.

   • From the calculator: \(\mathbf{s}_{6}=T^{6}\mathbf{s}_0=\begin{pmatrix}156 \\ 333 \\ 511\end{pmatrix}\)
   • To the nearest whole number: 156, 333, 511.

3. (c) Find the number of customers on each plan in the long term, to the nearest whole number.

   • Use \(T\mathbf{s}=\mathbf{s}\) with the sum equal to 1 (or a high power of T).
   • \(\mathbf{s}=\begin{pmatrix}0.111 \\ 0.333 \\ 0.556\end{pmatrix}\)
   • Multiply by 1000: 111, 333, 556.

A rental firm has three depots: Airport (A), City (C) and Harbour (H). A car is returned each day to one depot, and the depot depends only on where it was returned the day before, with transition matrix \(T=\begin{pmatrix}0.52 & 0.18 & 0.32 \\ 0.28 & 0.62 & 0.18 \\ 0.2 & 0.2 & 0.5\end{pmatrix}\) (columns and rows in the order A, C, H). A car is returned to the Airport today. Find the probability that it is returned to the City depot four days later.

• Start A is column A. End C is row C. 4 steps.
• From the calculator: \(T^{4}=\begin{pmatrix}0.337 & 0.324 & 0.342 \\ 0.38 & 0.393 & 0.366 \\ 0.283 & 0.283 & 0.292\end{pmatrix}\)
• \(P=0.38\)

Each week a user of a fitness app is Daily (D), Weekly (W) or Inactive (I). The transition matrix is \(T=\begin{pmatrix}0.68 & 0.28 & 0.12 \\ 0.22 & 0.52 & 0.18 \\ 0.1 & 0.2 & 0.7\end{pmatrix}\) (columns and rows in the order D, W, I). Use technology to find the long-term probability that a user is a Daily user.

• From the calculator: \(T^{60}=\begin{pmatrix}0.38 & 0.38 & 0.38 \\ 0.296 & 0.296 & 0.296 \\ 0.324 & 0.324 & 0.324\end{pmatrix}\)
• Every column is \(\begin{pmatrix}0.38 \\ 0.296 \\ 0.324\end{pmatrix}\).
• The long-term probability for D is 0.38. Check with \(T^{100}\).

A gambler starts a game with \(\pounds 2\). He bets \(\pounds 1\) each round. He wins \(\pounds 1\) with probability 0.45 and loses \(\pounds 1\) with probability 0.55. He stops when he has \(\pounds 0\) or \(\pounds 5\).

1. (a) Write down the transition matrix for the amount of money he has, with states \(\pounds 0\) to \(\pounds 5\).

   • States 0, 1, 2, 3, 4, 5. States 0 and 5 are absorbing: a 1 on the diagonal.
   • From each other state: up one with 0.45, down one with 0.55.

2. (b) Find the probability that he finishes with \(\pounds 5\).

   • From the calculator: \(T^{100}\) has the same 3 significant figures as \(T^{200}\).
   • Start is column £2, end is row £5.
   • Probability 0.286.

Customers of a delivery app are Active or Lapsed. Each month 0.3 of active customers lapse and 0.12 of lapsed customers become active. The transition matrix is \(T=\begin{pmatrix}0.7 & 0.12 \\ 0.3 & 0.88\end{pmatrix}\) (columns and rows in the order Active, Lapsed).

1. (a) Find the eigenvalues of T and a corresponding eigenvector for each.

   • \(\det(T-\lambda I)=\lambda^2-1.58\lambda+0.58=0\)
   • \(\lambda=1\text{ or }\lambda=0.58\)
   • For \(\lambda=1\): solve \((T-I)\mathbf{v}=\mathbf{0}\) to get \(\begin{pmatrix}2 \\ 5\end{pmatrix}\).
   • For \(\lambda=0.58\): solve to get \(\begin{pmatrix}1 \\ -1\end{pmatrix}\).

2. (b) Write down matrices P and D such that \(T=PDP^{-1}\).

   • The columns of P are the eigenvectors; D has the matching eigenvalues on its diagonal.
   • \(P=\begin{pmatrix}2 & 1 \\ 5 & -1\end{pmatrix},\quad D=\begin{pmatrix}1 & 0 \\ 0 & 0.58\end{pmatrix}\)
   • Order of the columns of P matches the order in D.

A lake is Clear or Cloudy each week. The transition matrix is \(T=\begin{pmatrix}0.82 & 0.42 \\ 0.18 & 0.58\end{pmatrix}\) (columns and rows in the order Clear, Cloudy), and \(T=PDP^{-1}\) where \(P=\begin{pmatrix}7 & 1 \\ 3 & -1\end{pmatrix},\ D=\begin{pmatrix}1 & 0 \\ 0 & 0.4\end{pmatrix}\). At the start, the probability that the lake is clear is 0.9. Let \(f_n\) be the probability that the lake is clear after \(n\) weeks.

1. (a) Find an expression for \(f_n\).

   • Use \(\mathbf{s}_n=PD^nP^{-1}\mathbf{s}_0\).
   • \(P^{-1}\mathbf{s}_0=\begin{pmatrix}0.1 \\ 0.2\end{pmatrix}\)
   • \(\mathbf{s}_n=0.1\begin{pmatrix}7 \\ 3\end{pmatrix}+0.2(0.4)^{n}\begin{pmatrix}1 \\ -1\end{pmatrix}\)
   • First component: \(f_n=0.7+0.2(0.4)^{n}\). Check n = 0: 0.9.

2. (b) Hence find the long-term probability that the lake is clear.

   • \((0.4)^{n}\to0\text{ as }n\to\infty\)
   • \(f_n\to0.7\)
   • This is the first entry of the steady-state vector.

A family chooses a holiday each year: Beach (B), Mountains (M) or City (C). The transition matrix is \(T = \begin{pmatrix} 0.5 & 0.25 & 0.05 \\ 0.25 & 0.5 & 0.2 \\ 0.25 & 0.25 & 0.75 \end{pmatrix}\), in that order.

1. (a) Use your calculator to find the three eigenvalues of \(T\).

   • From the calculator, the eigenvalues are 1, 0.5, 0.25.
   • One of them is 1, as it must be for a transition matrix.

2. (b) Write down an eigenvector for the eigenvalue 1.

   • From the calculator, the eigenvector for \(\lambda = 1\) is a multiple of \(\begin{pmatrix} 2 \\ 3 \\ 5 \end{pmatrix}\).
   • Any non-zero multiple is correct.

3. (c) Hence find the steady-state vector, as exact fractions.

   • The entries add to 10.
   • Divide each by 10: \(\mathbf{s} = \begin{pmatrix} \frac{1}{5} \\ \frac{3}{10} \\ \frac{1}{2} \end{pmatrix}\)
   • The entries add to 1.