# 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.

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.
• Wow, I simply copied it down incorrectly! Thanks a lot for the insight; the sources help tons. Feb 27, 2014 at 15:44

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.

• This method was not addressed at any point in my textbook or in lectures. Would you be able to point me to the correct answer (39?) by means of the method I tried? Feb 26, 2014 at 20:46
• To be honest, I have no idea about your method. :/ Feb 27, 2014 at 2:29