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).$
I know how to solve this in the usual way but I'm wondering about this solution:
$$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?
Best Answer
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.$$