# Find expected time to reach a state in a Markov chain

Consider a Markov chain $(X_n)_{n\geq 0}$ with state space $E$, initial distribution $p(0)$ and transition probability matrix $P$ given by $E = \{0, 1, 2\}, p(0) = [1\;\; 0\;\; 0]$ and

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

Find $E[T]$ for $T = \min(n, X_n = 2).$

$$E[T] = E[Y \mbox{ with }p=1/2] + (1/3) 0 + (2/3) E[Y\mbox{ with }p = 1/3] = 2 + 0 + (2/3)3 = 4$$

where $Y$ should be the discrete waiting time random variable.

Anyone know what's going on here?

To go from state $0$ to state $2$, we have to first leave state $0$. Define $T^*=\inf(n\geq 0: X_n\in\{1,2\})$, so that $T^*\leq T.$ The additional number of steps needed to reach state $2$ after time $T^*$ depends on where we land in $\{1,2\}$, that is, on our new starting point $X_{T^*}.$ Putting it all together gives $$E[T]=E[T^*]+E[T\mid X_{T^*}=2]\,P(X_{T^*}=2)+E[T\mid X_{T^*}=1]\,P(X_{T^*}=1).$$ Since the first state visited in $\{1,2\}$ is twice as likely to be $1$ as compared to $2$, we get $$E[T]=E[T^*]+E[T\mid X_{T^*}=2]\,\left({1\over 3}\right)+E[T\mid X_{T^*}=1]\left({2\over 3}\right).$$
Now, $E[T\mid X_{T^*}=2]=0$ since we start in state $2$. Also, $T^*$ is a geometric random variable with $p=1/2$ and so $E[T^*]=2.$ Finally, starting in state $1$, the time to hit state $2$ is a geometric random variable with $p=1/3$, and so $E[T\mid X_{T^*}=1]=3.$ This gives $$E[T]=2+ 0\left({1\over 3}\right)+ 3\left({2\over 3}\right)=4.$$
• Lets say we have a 4*4 matrix instead. This method easily extends to larger matrices? , and in the 4*4 case just by adding to $$E[T]= ...+ E[T^*_*]+E[T^*_*\mid X_{T^*_*}=v]\,\left({a\over b}\right)+E[T\mid X_{T^*_*}=w]\left({c\over d}\right).$$ if you understand what i mean. Sorry about the ter latex...im still trying to learn that. (And this T is a newly defined T in a similar way as the T*.) Commented Dec 17, 2015 at 4:30