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.
Best Answer
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: