Expected number of steps between states in a Markov Chain

Question

Suppose I am given a state space $S=\{0,1,2,3\}$ with transition probability matrix

$\mathbf{P}= \begin{bmatrix} \frac{2}{3} & \frac{1}{3} & 0 & 0 \\[0.3em] \frac{2}{3} & 0 & \frac{1}{3} & 0\\[0.3em] \frac{2}{3} & 0 & 0 & \frac{1}{3}\\[0.3em] 0 & 0 & 0 & 1 \end{bmatrix}$

and I want the expected number of steps from states $0 \rightarrow 3$ which I will denote $E_0(N(3))$.

Attempt at solving: First I write the transient states $\{0,1,2\}$ and recurrent state $\{3\}$ which I got from drawing the chain. I now want to write $\mathbf{P}$ in canonical form, i.e. with state space $S=\{3,0,1,2\}$ as so:

$\mathbf{P}=\begin{bmatrix} 1 & 0 & 0 & 0\\[0.3em] 0 & \frac{2}{3} & \frac{1}{3} & 0 \\[0.3em] 0 & \frac{2}{3} & 0 & \frac{1}{3}\\[0.3em] \frac{2}{3} & 0 & 0 & \frac{1}{3} \end{bmatrix}$

It's clear that the transient matrix is

$\mathbf{Q}= \begin{bmatrix} \frac{2}{3} & \frac{1}{3} & 0 \\[0.3em] \frac{2}{3} & 0 & \frac{1}{3}\\[0.3em] 0 & 0 & \frac{1}{3} \end{bmatrix}$

Now I can get the matrix I want for computing expected steps (calculated with Mathematica):

$\mathbf{M}=(\mathbf{I}-\mathbf{Q})^{-1}=\begin{bmatrix} 9 & 3 & 3\\[0.3em] 6 & 3 & 3\\[0.3em] 0 & 0 & \frac{3}{2} \end{bmatrix}$

From this, we get $E_0(N(3))=9+3+3=15$. Is this correct? I am sort of weak in finding the "canonical form" of a matrix. Note: although this looks like a homework question, it's simply a preparation problem for an upcoming exam, so a complete solution/correction of my work is appreciated.

Answer 1

The distribution for the number of time steps to move between marked states in a discrete time Markov chain is the discrete phase-type distribution. You made a mistake in reorganising the row and column vectors and your transient matrix should be $$\mathbf{Q}= \begin{bmatrix} \frac{2}{3} & \frac{1}{3} & 0 \\ \frac{2}{3} & 0 & \frac{1}{3}\\ \frac{2}{3} & 0 & 0 \end{bmatrix}$$ which you can then continue to find $$\mathbf M = (\mathbf I - \mathbf Q)^{-1} = \begin{bmatrix} 27 & 9 & 3\\ 24 & 9 & 3 \\ 18 & 6 & 3\end{bmatrix}$$ and summing the first row gives you (as you require) 39.

Generally when I have seen these distributions written the 'exit' state is put last, which would mean your matrix with elements in the order $\{0,1,2,3\}$ was already in canonical form and you needed to extract the top left portion as your transient matrix,

$$\mathbf P = \left( \begin{array}{ccc|c} \frac{2}{3} & \frac{1}{3} & 0 & 0\\ \frac{2}{3} & 0 & \frac{1}{3} & 0 \\ \frac{2}{3} & 0 & 0 & \frac{1}{3}\\ \hline\\ 0 & 0 & 0 & 1 \end{array} \right) $$ For further moments you might be interested in this paper:

• Dayar, Tuǧrul. "On moments of discrete phase-type distributions." Formal Techniques for Computer Systems and Business Processes. Springer Berlin Heidelberg, 2005. 51-63. doi:10.1007/11549970_5.

Answer 2

Usually, my approach to this kind of question is to solve a very simple recurrence.

Just look to $ E_{0} N(3)$ but conditioned in each of the two possible first steps to get (I will write $N$ instead of $N(3)$

$$E_0 N = \frac{2}{3}E_0N + \frac{1}{3}E_1N +1$$

The term +1 shows up because once you had walked one step you have to add this step to the account. (if you want a rigorous proof of this equation, use the simple property of Markov)

If you repeat this process to $E_1N$ and $E_2N$ and replace what you find in the first equation you will find that $E_0N = 39$ :(

Now I'm curious about the results... I made the calculations twice, but it is possible that I forgot something.