Expected time to leave an open class

Question

Suppose that we have a markov chain $X_{n}$ and P is the transition matrix.

$P = \begin{bmatrix} 1/4 & 3/4 & 0 & 0 & 0 & 0 & 0 & 0\\ 3/4 & 1/4 & 0 & 0 &0 &0 &0 &0 \\ 1/4 &0 & 0 & 1/4 & 1/4 & 1/4 & 0 & 0 \\ 0& 1/4&1/2 &0 & 0&1/4 &0 &0 \\0 &0 &0 &0 &0 &1/4 &3/4&0 \\ 0& 0&0 &0 & 3/4& 0&1/4 &0 \\ 0&0 &0 &0 &1/4 &1/4 &1/4 &1/4 \\ 0&0 &0 &0 &0 &0 &1 &0 \end{bmatrix} $

It is clear that we have 3 classes , 2 closed and 1 open.

$C_{1}=\left\{1,2\right\}$ is closed

$C_{2}=\left\{3,4\right\}$ is open

$C_{3}=\left\{5,6,7,8\right\}$ is closed

Let's say that we start from state 3 , $X_{0}=3$ which is in class $C_{2}$ and we are asked first to estimate the expected time until we leave the class $C_{2}$ and secondly to estimate the probabilities to reach the two other classes.

So I suppose that for the first question we have to define a stopping time $T=\left\{k\geq 0:X_{k}\notin C_{2}\right\}$ and then estimate $\mathbb{E}\big[T|X_{0}=3\big]$ but is there a closed form in order to calculate that expectation , if not how do we calculate it ??

For the second question we also have $T_{1}=\left\{k\geq 0:X_{k}\in C_{1}\right\}$ and $T_{3}=\left\{k\geq 0:X_{k}\in C_{3}\right\}$

so we have to calculate the probabilities $\mathbb{P}\big[T_{1}|X_{0}=3\big]$ and $\mathbb{P}\big[T_{2}|X_{0}=3\big]$.The same is there a closed form ?? Or is there a standard technique to estimate that kind of probabilities ??

Answer 1

Let $g_x(k) = E \inf_t[X_t \in C_1 \cup C_3|X_0 = k]$ hence, \begin{align} g_x(3) &= 1+0.25g_x(4)\\ g_x(4) &= 1+0.5g_x(3) \end{align} thus $$ g_x(3) = 1+0.25+0.125g_x(3) \to g_x(3)=1.25/0.875. $$

Let $\rho_{ij} = P(T_j < \infty | X_0 = i)$, thus analogical recursive equations can be written \begin{align} \rho_{3,c_3} &= 1/2+0.25\rho_{4,c_3}\\ \rho_{4,c_3} &= 1/4 +0.5 \rho_{3,c_3} \end{align} by solving it you'll get $\rho_{3,c_3} = 9/14$ and $\rho_{3,c_1} = 5/14$.

Answer 2

One approach is to replace the two closed classes with a pair of absorbing states. In canonical form, the resulting transition matrix is $$\begin{bmatrix}0&\frac14&\frac14&\frac12\\\frac12&0&\frac14&\frac14\\0&0&1&0\\0&0&0&1\end{bmatrix}.$$ Its fundamental matrix is $$N = (I_2-Q)^{-1} = \begin{bmatrix}1&-\frac14\\-\frac12&1\end{bmatrix}^{-1} = \begin{bmatrix}\frac87&\frac27\\\frac47&\frac87\end{bmatrix}.$$ (Here, $Q$ is the upper-right $2\times2$ submatrix that involves only the transient states.) The entries of this matrix are the expected times in each transient state before absorption, given that the system started in a particular transient state. Its row sums are then the expected times before absorption, so the time spent in $C_2$ after starting in state 3 is $\frac87+\frac27 = \frac{10}7$.

The absorption probabilities are found by multiplying $N$ by the transition probabilities into the absorbing states—the upper-right $2\times2$ submatrix—giving $$\begin{bmatrix}\frac5{14}&\frac9{14}\\\frac37&\frac47\end{bmatrix}.$$ The specific probabilities we’re interested are the first row of this matrix.