Consider a $4$ state Markov Chain that includes the row-stochastic
transition matrix
$$P = \left(\begin{array}{cccc} 1/4&1/4&1/4&1/4 \\ 1/2&0&0&1/2 \\
1/3&1/3&1/3&0 \\ 0&0&0&1 \end{array}
\right).$$
Assume that we start the chain in state $1$. I would like to find the expected
length of time intervals until we are absorbed (as in, before we reach state 4).
To me, this seems like a problem where we have a large number of potential
transitions, and I need some help on considering a clean way to calculate the
terms for the probability that the expected length is $\geq 3$. I see that for
the first term of this expectation, we have
$1 \times P_{1,4} = \frac{1}{4},$ and for the second term, we have
$$2 \times \sum_{i=1}^3 P_{1,i}P_{i,4}
= 2 \times (\frac{1}{4} \times \frac{1}{4} + \frac{1}{4} \times \frac{1}{2}
+ \frac{1}{4} \times 0)
= 2 \times (\frac{3}{16}) = \frac{3}{8}.$$
However, I see how this computation becomes much more complicated given the
length of the chain. Is there potentially a more efficient way to calculate
the individual terms of this expectation?
Best Answer
Considering this, assume $$Q = \left(\begin{array}{cccc} 1/4&1/4&1/4 \\ 1/2&0&0 \\ 1/3&1/3&1/3 \end{array} \right)$$
Then the expected number of transitions from state $i$ to $j$ is
$$N=(I-Q)^{-1}=\left(\begin{array}{cccc} 2.2857 &0.8571&0.8571 \\ 1.1429 & 1.4286 & 0.4286\\ 1.7143 & 1.1429 & 2.1429\end{array} \right)$$
The $i$th element of the vector $\mathbf{t}=N\mathbf{1}$ gives the expected number of transitions until absorption when beginning from state $i$.
For this case, $$\mathbf{t}=\left(\begin{array}{cccc} 2.2857 &0.8571&0.8571 \\ 1.1429 & 1.4286 & 0.4286\\ 1.7143 & 1.1429 & 2.1429\end{array} \right)\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}=\begin{pmatrix} 4\\ 3\\ 5 \end{pmatrix}$$ So the answer to your question is $\color{red}{4}$.