Expected number of steps between states in a Markov Chain 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.
 A: 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. 
A: 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.

