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

A bike-share scheme has three docking stations: X, Y and Z. Each bike is taken from one station and returned to one station the next day. The transition diagram shows the probabilities of where a bike is returned. Write down the transition matrix.

• Read the arrows leaving each state to fill each column. A missing arrow is 0.
• column X: X to X 0.7, X to Y 0, X to Z 0.3; column Y: Y to X 0.2, Y to Y 0.5, Y to Z 0.3; column Z: Z to X 0, Z to Y 0.4, Z to Z 0.6.
• Check each column sums to 1.

A robot vacuum cleaner is in one of three rooms, the kitchen (K), the lounge (L) or the hall (H), at the start of each hour. It moves according to the transition matrix \(T=\begin{pmatrix}0.24 & 0.32 & 0 \\ 0.76 & 0.28 & 0.52 \\ 0 & 0.4 & 0.48\end{pmatrix}\) (columns and rows in the order K, L, H). Draw the transition diagram, with the probability on each arrow.

• One vertex for each state.
• Diagonal entries are loops: loop at K 0.24; loop at L 0.28; loop at H 0.48.
• Other non-zero entries are arrows from the column state to the row state: K to L 0.76; L to K 0.32; L to H 0.4; H to L 0.52.
• No arrow for the zero entries (K to H, H to K). Labels leaving each vertex sum to 1.

A web server is Up (U) or Down (D) each hour. If it is up this hour, the probability that it is up next hour is 0.92. If it is down this hour, the probability that it is down next hour is 0.4. Write down the transition matrix, with states in the order U, D.

• Column U (up this hour): up 0.92, so down \(1-0.92=0.08\).
• Column D (down this hour): down 0.4, so up \(1-0.4=0.6\).
• Each column sums to 1.

A delivery drone is based each night at one of three depots, P, Q or R. Where it is based tomorrow night depends only on where it is tonight, with transition matrix \(T=\begin{pmatrix}0.62 & 0.22 & 0.32 \\ 0.14 & 0.46 & 0.28 \\ 0.24 & 0.32 & 0.4\end{pmatrix}\) (columns and rows in the order P, Q, R).

1. (a) It is at depot Q on Monday night. Find the probability that it is at depot P on Wednesday night.

   • From the calculator: \(T^2=\begin{pmatrix}0.492 & 0.34 & 0.388 \\ 0.218 & 0.332 & 0.286 \\ 0.29 & 0.328 & 0.326\end{pmatrix}\)
   • Start Q is column Q, end P is row P.
   • \(P=0.34\)

2. (b) It is at depot R on Monday night. Find the probability that it is at depot R on Wednesday night.

   • From the calculator: \(T^2=\begin{pmatrix}0.492 & 0.34 & 0.388 \\ 0.218 & 0.332 & 0.286 \\ 0.29 & 0.328 & 0.326\end{pmatrix}\)
   • Start R is column R, end R is row R.
   • \(P=0.326\)

Each election a voter supports the Red party or the Blue party. The transition matrix is \(T=\begin{pmatrix}0.8 & 0.45 \\ 0.2 & 0.55\end{pmatrix}\) (columns and rows in the order Red, Blue). In the long term the proportions of voters for Red and for Blue 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.8x + 0.45y = x; 0.2x + 0.55y = 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.45y = 0.2x.
   • Substitute into x+y=1 and solve.
   • \(x=\frac{9}{13},\ y=\frac{4}{13}\)
   • As decimals: 0.692 and 0.308.

A gym has 1200 members, each with one main class: Yoga (Y), Spin (S) or Weights (W). Each month, of the members in Yoga, 60% stay and 30% move to Spin (the rest move to Weights). Of the members in Spin, 20% move to Yoga and 50% stay. Of the members in Weights, 10% move to Yoga and 70% stay. Initially 480 members are in Yoga, 300 in Spin and 420 in Weights.

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

   • Column Y: 0.6 stay, 0.3 to S, so 0.1 to W. Column S: 0.2 to Y, 0.5 stay, so 0.3 to W. Column W: 0.1 to Y, 0.7 stay, so 0.2 to S.
   • Check each column sums to 1.

2. (b) Find the number of members in each class after 5 months. Give each answer to the nearest whole number.

   • From the calculator: \(\mathbf{s}_{5}=T^{5}\mathbf{s}_0=\begin{pmatrix}323 \\ 390 \\ 487\end{pmatrix}\)
   • To the nearest whole number: 323, 390, 487.

3. (c) Find the number of members in each class 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.265 \\ 0.324 \\ 0.412\end{pmatrix}\)
   • Multiply by 1200: 318, 388, 494.

A factory machine is Working (W), Idle (I) or Faulty (F) each day, and tomorrow's state depends only on today's, with transition matrix \(T=\begin{pmatrix}0.78 & 0.42 & 0.32 \\ 0.12 & 0.48 & 0.22 \\ 0.1 & 0.1 & 0.46\end{pmatrix}\) (columns and rows in the order W, I, F). The machine is working today. Find the probability that it is faulty five days later.

• Start W is column W. End F is row F. 5 steps.
• From the calculator: \(T^{5}=\begin{pmatrix}0.635 & 0.629 & 0.621 \\ 0.209 & 0.215 & 0.218 \\ 0.155 & 0.155 & 0.161\end{pmatrix}\)
• \(P=0.155\)

Each year the water quality of a river is Good (G), Fair (F) or Poor (P). The transition matrix is \(T=\begin{pmatrix}0.62 & 0.24 & 0.08 \\ 0.28 & 0.52 & 0.28 \\ 0.1 & 0.24 & 0.64\end{pmatrix}\) (columns and rows in the order G, F, P). Use technology to find the long-term probability that the water quality is Fair.

• From the calculator: \(T^{60}=\begin{pmatrix}0.302 & 0.302 & 0.302 \\ 0.368 & 0.368 & 0.368 \\ 0.33 & 0.33 & 0.33\end{pmatrix}\)
• Every column is \(\begin{pmatrix}0.302 \\ 0.368 \\ 0.33\end{pmatrix}\).
• The long-term probability for F is 0.368. Check with \(T^{100}\).

A beetle is on a ladder with five rungs, numbered 1 (bottom) to 5 (top). Each minute it climbs up one rung with probability 0.55 or slips down one rung with probability 0.45. Rung 1 is a pool and rung 5 is its nest: once it reaches either one it stays there. The beetle starts on rung 2.

1. (a) Write down the transition matrix for the rung the beetle is on, with states 1 to 5.

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

2. (b) Find the probability that the beetle ends in its nest.

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

Learners on a language app are Daily or Occasional. Each week 0.2 of daily learners become occasional and 0.05 of occasional learners become daily. The transition matrix is \(T=\begin{pmatrix}0.8 & 0.05 \\ 0.2 & 0.95\end{pmatrix}\) (columns and rows in the order Daily, Occasional).

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

   • \(\det(T-\lambda I)=\lambda^2-1.75\lambda+0.75=0\)
   • \(\lambda=1\text{ or }\lambda=0.75\)
   • For \(\lambda=1\): solve \((T-I)\mathbf{v}=\mathbf{0}\) to get \(\begin{pmatrix}1 \\ 4\end{pmatrix}\).
   • For \(\lambda=0.75\): 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}1 & 1 \\ 4 & -1\end{pmatrix},\quad D=\begin{pmatrix}1 & 0 \\ 0 & 0.75\end{pmatrix}\)
   • Order of the columns of P matches the order in D.

A shop is Busy or Quiet each hour. The transition matrix is \(T=\begin{pmatrix}0.75 & 0.15 \\ 0.25 & 0.85\end{pmatrix}\) (columns and rows in the order Busy, Quiet), and \(T=PDP^{-1}\) where \(P=\begin{pmatrix}3 & 1 \\ 5 & -1\end{pmatrix},\ D=\begin{pmatrix}1 & 0 \\ 0 & 0.6\end{pmatrix}\). At the start, the probability that the shop is busy is 0.9. Let \(f_n\) be the probability that the shop is busy after \(n\) hours.

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.125 \\ 0.525\end{pmatrix}\)
   • \(\mathbf{s}_n=0.125\begin{pmatrix}3 \\ 5\end{pmatrix}+0.525(0.6)^{n}\begin{pmatrix}1 \\ -1\end{pmatrix}\)
   • First component: \(f_n=0.375+0.525(0.6)^{n}\). Check n = 0: 0.9.

2. (b) Hence find the long-term probability that the shop is busy.

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

A pupil travels to school each day by Walking (W), Bus (B) or Cycling (C). The transition matrix is \(T = \begin{pmatrix} 0.55 & 0.2 & 0.2 \\ 0.1 & 0.65 & 0.15 \\ 0.35 & 0.15 & 0.65 \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.35.
   • 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} 8 \\ 7 \\ 11 \end{pmatrix}\).
   • Any non-zero multiple is correct.

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

   • The entries add to 26.
   • Divide each by 26: \(\mathbf{s} = \begin{pmatrix} \frac{4}{13} \\ \frac{7}{26} \\ \frac{11}{26} \end{pmatrix}\)
   • The entries add to 1.