Transition matrices and diagrams Problem set A Worked solutions

A Markov chain has two states, A and B. Write down the transition matrix in each case.

1. (a) \(P(A \to A) = 0.64\); \(P(B \to A) = 0.27\).

   • Column A: \(1 − 0.64 = 0.36\), so \(P(A \to B) = 0.36\)
   • Column B: \(1 − 0.27 = 0.73\), so \(P(B \to B) = 0.73\)
   • \(\mathbf{T} = \begin{pmatrix} 0.64 & 0.27 \\ 0.36 & 0.73 \end{pmatrix}\)

2. (b) \(P(A \to B) = 0.88\); \(P(B \to B) = 0.41\).

   • Column A: \(1 − 0.88 = 0.12\), so \(P(A \to A) = 0.12\)
   • Column B: \(1 − 0.41 = 0.59\), so \(P(B \to A) = 0.59\)
   • \(\mathbf{T} = \begin{pmatrix} 0.12 & 0.59 \\ 0.88 & 0.41 \end{pmatrix}\)

A Markov chain has three states, A, B and C. The known probabilities are: \(P(A \to A) = 0.52\); \(P(A \to B) = 0.31\); \(P(B \to B) = 0.46\); \(P(B \to C) = 0.31\); \(P(C \to A) = 0.14\); \(P(C \to C) = 0.67\). Write down the transition matrix.

• Column A: \(1 − 0.52 − 0.31 = 0.17\), so \(P(A \to C) = 0.17\)
• Column B: \(1 − 0.46 − 0.31 = 0.23\), so \(P(B \to A) = 0.23\)
• Column C: \(1 − 0.14 − 0.67 = 0.19\), so \(P(C \to B) = 0.19\)
• \(\mathbf{T} = \begin{pmatrix} 0.52 & 0.23 & 0.14 \\ 0.31 & 0.46 & 0.19 \\ 0.17 & 0.31 & 0.67 \end{pmatrix}\)

A Markov chain has four states, A, B, C and D. The probabilities of changing state are: \(P(A \to B) = 0.27\); \(P(A \to C) = 0.18\); \(P(A \to D) = 0.24\); \(P(B \to A) = 0.12\); \(P(B \to C) = 0.33\); \(P(B \to D) = 0.19\); \(P(C \to A) = 0.28\); \(P(C \to B) = 0.07\); \(P(C \to D) = 0.19\); \(P(D \to A) = 0.22\); \(P(D \to B) = 0.29\); \(P(D \to C) = 0.38\). Find the transition matrix.

• Column A: \(1 − 0.27 − 0.18 − 0.24 = 0.31\), so \(P(A \to A) = 0.31\)
• Column B: \(1 − 0.12 − 0.33 − 0.19 = 0.36\), so \(P(B \to B) = 0.36\)
• Column C: \(1 − 0.28 − 0.07 − 0.19 = 0.46\), so \(P(C \to C) = 0.46\)
• Column D: \(1 − 0.22 − 0.29 − 0.38 = 0.11\), so \(P(D \to D) = 0.11\)
• \(\mathbf{T} = \begin{pmatrix} 0.31 & 0.12 & 0.28 & 0.22 \\ 0.27 & 0.36 & 0.07 & 0.29 \\ 0.18 & 0.33 & 0.46 & 0.38 \\ 0.24 & 0.19 & 0.19 & 0.11 \end{pmatrix}\)

Draw the transition diagram for each matrix. The rows and columns are in the order of the states shown.

1. (a) States A, B: \(\mathbf{T} = \begin{pmatrix} 0.38 & 0.57 \\ 0.62 & 0.43 \end{pmatrix}\)

   • Column A: a loop 0.38, an arrow to B labelled 0.62.
   • Column B: an arrow to A labelled 0.57, a loop 0.43.
   • Check: the labels leaving each vertex, loop included, add to 1.

2. (b) States A, B, C: \(\mathbf{T} = \begin{pmatrix} 0.66 & 0 & 0.41 \\ 0.12 & 0.52 & 0.36 \\ 0.22 & 0.48 & 0.23 \end{pmatrix}\)

   • Column A: a loop 0.66, an arrow to B labelled 0.12, an arrow to C labelled 0.22.
   • Column B: a loop 0.52, an arrow to C labelled 0.48.
   • Column C: an arrow to A labelled 0.41, an arrow to B labelled 0.36, a loop 0.23.
   • Check: the labels leaving each vertex, loop included, add to 1.

Write down the transition matrix for the transition diagram, with the states in the order A, B.

• Column A (arrows leaving A): 0.62 (loop), 0.38 (A to B)
• Column B (arrows leaving B): 0.27 (B to A), 0.73 (loop)
• \(\mathbf{T} = \begin{pmatrix} 0.62 & 0.27 \\ 0.38 & 0.73 \end{pmatrix}\)
• Each column adds to 1.

Write down the transition matrix for the transition diagram, with the states in the order A, B, C. Say which state is absorbing.

• Column A (arrows leaving A): 0.55 (loop), 0.3 (A to B), 0.15 (A to C)
• Column B (arrows leaving B): 0.4 (B to A), 0.4 (loop), 0.2 (B to C)
• Column C (arrows leaving C): 1 (loop)
• \(\mathbf{T} = \begin{pmatrix} 0.55 & 0.4 & 0 \\ 0.3 & 0.4 & 0 \\ 0.15 & 0.2 & 1 \end{pmatrix}\)
• The loop at C is 1 and nothing leaves C, so C is absorbing.

Write down the transition matrix for the transition diagram, with the states in the order A, B, C, D.

• Column A (arrows leaving A): 0.3 (loop), 0.5 (A to B), 0.2 (A to D)
• Column B (arrows leaving B): 0.25 (B to A), 0.75 (B to C)
• Column C (arrows leaving C): 0.1 (C to A), 0.2 (C to B), 0.4 (loop), 0.3 (C to D)
• Column D (arrows leaving D): 0.6 (D to C), 0.4 (loop)
• \(\mathbf{T} = \begin{pmatrix} 0.3 & 0.25 & 0.1 & 0 \\ 0.5 & 0 & 0.2 & 0 \\ 0 & 0.75 & 0.4 & 0.6 \\ 0.2 & 0 & 0.3 & 0.4 \end{pmatrix}\)
• Each column adds to 1.

Three cafes, A, B and C, share the same street. Each week, 80% of the customers of cafe A return to A and 12% go to B. Of the customers of B, 70% return to B and 20% go to C. Of the customers of C, 15% go to A and 25% go to B. Write down the transition matrix for the weekly movement of customers, with the cafes in the order A, B, C.

• Column A: stay 0.8, to B 0.12, so to C \(1 − 0.8 − 0.12 = 0.08\)
• Column B: stay 0.7, to C 0.2, so to A \(1 − 0.7 − 0.2 = 0.1\)
• Column C: to A 0.15, to B 0.25, so stay \(1 − 0.15 − 0.25 = 0.6\)
• \(\mathbf{T} = \begin{pmatrix} 0.8 & 0.1 & 0.15 \\ 0.12 & 0.7 & 0.25 \\ 0.08 & 0.2 & 0.6 \end{pmatrix}\)

Answer each part.

1. (a) Explain why \(\begin{pmatrix} 0.52 & 0.28 \\ 0.39 & 0.72 \end{pmatrix}\) cannot be a transition matrix.

   • Add each column. Column 1: \(0.52 + 0.39 = 0.91\).
   • The columns of a transition matrix must each add to 1, so this is not one.

2. (b) \(\mathbf{T} = \begin{pmatrix} 0.42 & a & 0.09 \\ b & 0.31 & 0.46 \\ 0.25 & 0.51 & c \end{pmatrix}\) is a transition matrix. Find \(a\), \(b\) and \(c\).

   • Column 1: \(0.42 + 0.25 + b = 1\), so \(b = 0.33\)
   • Column 2: \(0.31 + 0.51 + a = 1\), so \(a = 0.18\)
   • Column 3: \(0.09 + 0.46 + c = 1\), so \(c = 0.45\)

A phone battery is checked each morning. It is charged (C), low (L) or dead (D). If it is charged, it is still charged the next morning with probability 0.72, and low with probability 0.28. If it is low, it is charged the next morning with probability 0.08 and dead with probability 0.37. A dead battery is replaced only at the end of the term, so it stays dead.

1. (a) Write down the transition matrix, with the states in the order C, L, D.

   • C: stay 0.72, to L 0.28, to D 0.
   • L: to C 0.08, stay 0.55, to D 0.37.
   • D: stays, so \(P(D \to D) = 1\).
   • \(\mathbf{T} = \begin{pmatrix} 0.72 & 0.08 & 0 \\ 0.28 & 0.55 & 0 \\ 0 & 0.37 & 1 \end{pmatrix}\)

2. (b) List the loops and arrows of the transition diagram.

   • Each diagonal entry is a loop, each other non-zero entry in column X, row Y is an arrow from X to Y.
   • Loops: C 0.72, L 0.55, D 1.
   • Arrows: C to L 0.28, L to C 0.08, L to D 0.37.

3. (c) State the absorbing state and say how you can see it in the matrix.

   • D has a loop of 1 and no arrow leaves it.
   • In the matrix, column D is \(\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\): a 1 on the diagonal and 0 elsewhere.