Problem Sheet 10

You should attempt all these questions and write up your solutions in advance of your workshop in week 11 (Tuesday 4 or Thursday 6 May) where the answers will be discussed.

1. Consider the Markov jump process on \(\mathcal S = \{1,2,3,4\}\) with generator matrix \[ \mathsf Q = \begin{pmatrix} -1 & \frac12 & \frac12 & 0 \\ \frac14 & -\frac12 & 0 & \frac14 \\ \frac16 & 0 & -\frac13 & \frac16 \\ 0 & 0 & 0 & 0 \end{pmatrix} . \]

(a) Draw a transition rate diagram for this process.

Solution. PICTURE

(b) Write down the communicating classes for this process, and state whether they are recurrent or transient.

Solution. The class \(\{1,2,3\}\) is not closed, so is transient. The class \(\{4\}\) is closed, so positive recurrent.

(c) Calculate the hitting probability \(h_{13}\).

Solution. Conditioning on the first step, we have \[\begin{align*} h_{13} &= \tfrac12 h_{23} + \tfrac12 h_{33} = \tfrac12 h_{23} + \tfrac12 \\ h_{23} &= \tfrac12 h_{13} + \tfrac12 h_{43} = \tfrac12 h_{13} , \end{align*}\] since \(h_{33} = 1\) and \(h_{43} = 0\). Substituting the second equation into the first gives \(h_{13} = \tfrac14 h_{13} + \tfrac12\), and so \(h_{13} = \frac23\).

(d) Calculate the expected hitting time \(\eta_{14}\).

Solution. Conditioning on the first step, we have \[\begin{align*} \eta_{14} &= 1 + \tfrac12 \eta_{24} + \tfrac12 \eta_{34} \\ \eta_{24} &= 2 + \tfrac12 \eta_{14} + \tfrac12 \eta_{44} = 1 + \tfrac12 \eta_{14} \\ \eta_{34} &= 3 + \tfrac12 \eta_{14} + \tfrac12 \eta_{44} = 1 + \tfrac12 \eta_{14} . \end{align*}\] Substituting the second and third equations into the first give \(\eta_{14} = \frac72 + \frac12 \eta_{14}\), so \(\eta_{14} = 7\).

2. Consider a Markov jump process \((X(t))\) on a triangle, with the vertices labelled 1, 2, 3 going clockwise. In a short time period \(\tau\), we move one step clockwise with probability \(\alpha\tau + o(\tau)\), one step anticlockwise with probability \(\beta\tau + o(\tau)\), or stay where we are.

(a) Write down a generator matrix for this Markov jump process, and draw a transition rate diagram.

Solution. \[ \mathsf Q = \begin{pmatrix} -(\alpha + \beta) & \alpha & \beta \\\beta & -(\alpha + \beta) & \alpha \\ \alpha & \beta & -(\alpha + \beta) \end{pmatrix} . \]

(b) What is the probability, starting from state 1, that we hit state 3 before state 2?

Solution. Starting from 1, we next move to 3 with probability \(\beta/(\alpha+\beta)\), and otherwise we next move to 2, so the answer is \(\beta/(\alpha+\beta)\).

(c) What is the expected time \(\eta_{13}\) to hit state 3 starting from state 1.

Solution. Conditioning on the first step, we have \[\begin{align*} \eta_{13} &= \frac{1}{\alpha + \beta} + \frac{\alpha}{\alpha + \beta} \eta_{23} + \frac{\beta}{\alpha + \beta} \eta_{33} = \frac{1}{\alpha + \beta} + \frac{\alpha}{\alpha + \beta} \eta_{23} \\ \eta_{23} &= \frac{1}{\alpha + \beta} + \frac{\alpha}{\alpha + \beta} \eta_{33} + \frac{\beta}{\alpha + \beta} \eta_{13} = \frac{1}{\alpha + \beta} + \frac{\beta}{\alpha + \beta} \eta_{13} , \end{align*}\] since \(\eta_{33} = 0\). Substituting the second equation into the first and solving, we get \[ \eta_{13} = \frac{2\alpha+\beta}{\alpha^2 + \alpha\beta + \beta^2} . \]

(d) Write down the transition matrix \(\mathsf R\) for the jump chain \((Y_n)\).

Solution. \[ \mathsf R = \frac{1}{\alpha+\beta} \begin{pmatrix} 0 & \alpha & \beta \\\beta & 0 & \alpha \\ \alpha & \beta & 0 \end{pmatrix} . \]

(e) What is the probability in the jump chain \((Y_n)\) that, starting from state 1, that we hit state 3 before state 2?

Solution. Hitting probabilities are always the same for a Markov jump process and its jump chain, so this is \(\beta/(\alpha+\beta)\), as in part (b).

(f) What is the expected number of steps in the jump chain \((Y_n)\) to hit state 3 starting from state 1.

Solution. We have similar equations to before, with \[\begin{align*} \eta_{13} &= 1 + \frac{\alpha}{\alpha + \beta} \eta_{23} \\ \eta_{23} &= 1 + \frac{\beta}{\alpha + \beta} \eta_{13} . \end{align*}\] We substitute the second into the first and solve to get \[ \eta_{13} = \frac{2\alpha^2 + 3\alpha\beta + \beta^2}{\alpha^2 + \alpha\beta + \beta^2} = (\alpha + \beta) \frac{(2\alpha+\beta)}{\alpha^2 + \alpha\beta + \beta^2} . \] This is \((\alpha + \beta)\) times the original answer, reflecting the extra average time we spend in each state in the continuous time process.

3.

(a) Calculate the stationary distribution for a Markov jump process with generator matrix \[ \mathsf Q = \begin{pmatrix} -2 & 1 & 1 \\ 1 & -3 & 2 \\ 0 & 2 & -2 \end{pmatrix}. \]

Solution. First, we write out the equations for \(\boldsymbol\pi \mathsf Q = \mathbf 0\): \[\begin{align*} -2 \pi_1 + \phantom{3}\pi_2 \phantom{{}+2\pi_3} &= 0 \\ \pi_1 - 3\pi_2 + 2\pi_3 &= 0 \\ \pi_1 + 2\pi_2 - 2\pi_3 &= 0 . \end{align*}\] Second, we discard the second equation and choose \(\pi_1\) as the working variable, to get \[\begin{align*} \pi_2 \phantom{{}+2\pi_3 }&= 2\pi_1 \\ -2\pi_2 + 2\pi_3 &= \pi_1 , \end{align*}\] Substituting the second first into the second gives \(\pi_3 = \frac{5}{2}\pi_1\). Third, the normalising condition gives \[ \pi_1 + 2\pi_1 + \tfrac52 \pi_1 = 1 , \] meaning \(\pi_1 = \frac{2}{11}\). We get the solution \(\boldsymbol\pi = (\frac{2}{11}, \frac{4}{11}, \frac{5}{11})\).

(b) Fill in the missing entries of the following generator matrix, and find two stationary distributions for the associated Markov jump process: \[ \mathsf Q = \begin{pmatrix} ? & 2 & 0 \\ ? & -3 & 0 \\ ? & ? & 0 \end{pmatrix}. \]

Solution. Since rows add up to \(0\), and since off-diagonal elements cannot be negative, we have \[ \mathsf Q = \begin{pmatrix} -2 & 2 & 0 \\ 3 & -3 & 0 \\ 0 & 0 & 0 \end{pmatrix}. \]

Since state \(3\) is absorbing, we have that \((0,0,1)\) is a stationary distribution. For another, we seek a stationary distribution on states \(1\) and \(2\). The equations for \(\boldsymbol\pi \mathsf Q = \mathbf 0\) are \[ -2\pi_1 + 3 \pi_2 = 0 \qquad 2\pi_2 - 3 \pi_2 = 0 , \] with solution \((\frac35, \frac25, 0)\).

4. Consider a Markov jump process \((X(t))\) with state space \(\mathcal S = \{1,2,3,4\}\) and generator matrix \[ \mathsf Q = \begin{pmatrix} -2 & 2 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 1 & 2 & -4 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}. \]

(a) Draw a transition rate diagram for \((X(t))\).

Solution. PICTURE

(b) Write down the communicating classes for \((X(t))\), and state if each one is positive recurrent, null recurrent, or transient. Are there any absorbing states?

Solution. \(\{1,2\}\) is positive recurrent, \(\{3\}\) is transient, \(\{4\}\) is positive recurrent and is an absorbing state.

(c) Calculate the hitting probability \(h_{31}\).

Solution. Conditioning on the first step, we have \[ h_{31} = \tfrac14 h_{11} + \tfrac24 h_{21} + \tfrac14 h_{41} . \] Further, it’s clear that \(h_{11} = h_{21} = 1\) and \(h_{41} = 0\), and thus we get \(h_{31} = \frac34\).

(d) Does \((X(t))\) have an equilibrium distribution?

Solution. No, because the limiting distribution depends on the initial distribution. For example, starting in \(4\), we have \(\mathbb P(X_n = 4 \mid X_0 = 4) = 1\); but starting in \(1\) we have \(\mathbb P(X_n = 4 \mid X_0 = 1) = 0\).

(d) Conditional on Markov jump process starting from \(X(0) = 3\), calculate the limiting probabilities \(\lim_{n \to \infty} \mathbb P(X(t) = j \mid X(0) = 3)\) for all \(j \in \mathcal S\).

Solution. Starting from 3 we must leave 3 and not return. With probability \(\frac14\) we enter the absorbing state 4, while with probability \(\frac34\) we enter the closed class \(\{1,2,\}\). To know what happens in the latter case, we seek a stationary distribution on \(\{1,2\}\). The equations for \(\boldsymbol\pi \mathsf Q = \mathbf 0\) are \[ -2\pi_1 + \pi_2 = 0 \qquad 2\pi_2 - \pi_1 = 0 , \] with solution \(\boldsymbol\pi = (\frac13, \frac23, 0,0)\). Hence, the limiting probability starting from \(X(0) = 3\) is \[ \left( \tfrac34 \pi_1, \tfrac34 \pi_2, 0, \tfrac14 \right) = \left( \tfrac14, \tfrac12 , 0, \tfrac14 \right) . \]

5. Suppose \((X(t))\) is a continuous time Markov jump process with a stationary distribution \(\boldsymbol\phi = (\phi_i)\). Show that \(\boldsymbol\pi = (\pi_i)\), where \[ \pi_i = \frac{q_i \phi_i}{\sum_j q_j \phi_j} ,\] is a stationary distribution for the discrete time jump chain associated to \(\big(X(t)\big)\).

Solution. The denominator \(\sum_j q_j\phi_j\) is just a normalising constant. We must show that the vector \((q_i\phi_i)\) satisfies \(\boldsymbol\pi\mathsf R = \boldsymbol\pi\). Written in coordinate form, this is \[\begin{align*} \sum_i (q_i\phi_i)r_{ij} &= \sum_{i \neq j}q_i\phi_i \frac{q_{ij}}{q_i} \tag{writing $r_{ij}$ in terms of $q_{ij}$} \\ &= \sum_{i \neq j} \phi_i q_{ij} \\ &= \sum_i \phi_iq_{ij} + q_j\phi_j \tag{since $q_j = -q_{jj}$} \\ &= 0 + q_j\phi_j \tag{since $\boldsymbol\phi\mathsf Q = \mathbf 0$} \\ &= q_j \phi_j , \end{align*}\] as required.