<s>[INST] Markov Chain: Calculating Expectation Reach a Certain Set of States Suppose I have a Markov chain $Z_k$ with $6$ states, as depicted below: 

The probability of moving from one node to a neighboring node is $1/2$. For example, the probability of moving from node $1$ to node $2$ is $1/2$ and the probability of moving from node $1$ to node $6$ is $1/2$ etc.
Suppose $P(Z_0=1)=1$. That is we start state $1$. We need to compute two things:


*

*Compute the expected time we first reach the bottom of our pyramid (states $3$, $4$, or $5$). That is compute $E[T_B]$ where $T_B=min\{j: Z_j \in \{3,4,5\}\}$
My attempt: I try listing out all the possibilities
I can go from:


*

*I can go from State $1-2-3$. Time is $2$ when base is reached and probability $\frac{1}{2} \cdot \frac{1}{2}$

*$1-2-1-2-3$. Time is $4$ when base is reached. Probability of occurring is $\frac{1}{16}$.

*$1-2-1-2-1-2-3$. Time is $6$ when base is reached. Probability of occurring is $\frac{1}{64}$

*$1-2-1-2-1-2-1-2-3$. Time is $8$ when base is reached. Probability of occurring is $\frac{1}{64}$.
etc...
Thus my conclusion for these types of sequences expected value is:


$2 \cdot \frac{1}{4}+ 4*\frac{1}{16}+6*\frac{1}{64}+8*\frac{1}{256}  ...$
$\sum_{k=1}^{\infty} 2k \cdot (\frac{1}{2})^{2k}=\frac{8}{9}$ 


*Now, I can also go from State $1-6-5$. Time is $2$ when base is reached and probability $\frac{1}{2} \cdot \frac{1}{2}$

*$1-6-1-6-5$. Time is $4$ when base is reached. Probability of occurring is $\frac{1}{16}$.

*$1-6-1-6-1-6-5$. Time is $6$ when base is reached. Probability of occurring is $\frac{1}{64}$

*$1-6-1-6-1-6-1-6-5$. Time is $8$ when base is reached. Probability of occurring is $\frac{1}{64}$.


Thus my conclusion for these types of sequences expected value is:
$2 \cdot \frac{1}{4}+ 4*\frac{1}{16}+6*\frac{1}{64}+8*\frac{1}{256}  ...$
$\sum_{k=1}^{\infty} 2k \cdot (\frac{1}{2})^{2k}=\frac{8}{9}$
But there are more possibilities:


*$1-2-1-6-5.$ The time is $4$ probability $1/16$

*$1-2-1-6-1-6-5$. The time is $6$ probability $1/64$
10.$1-2-1-6-1-6-1-6-5 etc..$. The time is $8$ with probability $1/256$.
$\sum_{k=2}^{\infty} 2k \cdot (\frac{1}{2})^{2k}=\frac{7}{18}$
Still more possibilities....:
Too many possibilities (unfortunately gave up) as its like the Markov Chain restarts when we go back to $1$. Couldn't figure it out. Please let me know what I should do and thank you for the help
 [/INST] Taking two steps in the Markov chain can lead to one of two things, with equal probability:


*

*$1 \to 2 \to 3$ or $1 \to 6 \to 5$ and we're done.

*$1 \to 2 \to 1$ or $1 \to 6 \to 1$ and we're back where we started.


We took $2$ steps. In the first case, we have $0$ steps left, and in the second case, we have $\mathbb E[T_B]$ more steps left in expectation. Therefore 
$$
   \mathbb E[T_B] = 2 + \frac12 (0 + \mathbb E[T_B])
$$
and, solving, $\mathbb E[T_B] = 4$.
</s>