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
 A: For $i\in\{1,\dots,6\}$, let $m_i = E(T_B | Z_t = i)$ be the expected number of steps until reaching $\{3,4,5\}$, starting from state $i$.  Trivially, $m_3=m_4=m_5=0$.
To obtain a system of linear constraints, apply first-step analysis (conditioning on the first step out of state $i$).  For $i=1$, we have
\begin{align}
m_1 &= \sum_{j\in\{2,6\}} E(T_B | Z_t = 1, Z_{t+1} = j) P(Z_{t+1} = j | Z_t=1)\\
&= \sum_{j\in\{2,6\}} (1 + E(T_B | Z_{t+1} = j)) \frac{1}{2} \\
&= \frac{1}{2}\sum_{j\in\{2,6\}} 1 + \frac{1}{2} \sum_{j\in\{2,6\}} E(T_B | Z_{t+1} = j) \\
&= 1+\frac{1}{2}\sum_{j\in\{2,6\}} m_j.
\end{align}
For $i=2$, we have
\begin{align}
m_2 &= \sum_{j\in\{1,3\}} E(T_B | Z_t = 2, Z_{t+1} = j) P(Z_{t+1} = j | Z_t=2) \\
&= \sum_{j\in\{1,3\}} (1 + E(T_B | Z_{t+1} = j)) \frac{1}{2} \\
&= \frac{1}{2} \sum_{j\in\{1,3\}} 1 + \frac{1}{2} \sum_{j\in\{1,3\}} E(T_B | Z_{t+1} = j) \\
&= 1+\frac{1}{2}\sum_{j\in\{1,3\}} m_j\\
&= 1+\frac{1}{2}(m_1+0).
\end{align}
The $i=6$ case is similar. So we obtain the following linear constraints:
\begin{align}
m_1 &= 1 + (m_2+m_6)/2 \\
m_2 &= 1 + m_1/2 \\
m_6 &= 1 + m_1/2
\end{align}
By substituting the last two constraints into the first one, we obtain
$$m_1 = 1 + (1 + m_1/2 + 1 + m_1/2)/2 = 2 + m_1/2,$$
which implies that $m_1 = 4$.
A: 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$.
A: As an alternative approach in the spirit of your initial attempt, you can condition on the number $2k$ of steps to reach $\{3,4,5\}$ from $1$:
\begin{align}
E(T_B) 
&= \sum_{k=1}^\infty 2k\ P(\text{$2k$ steps}) \\
&= \sum_{k=1}^\infty 2k\ 2^k \left(\frac{1}{2}\right)^{2k} \\
&= \sum_{k=1}^\infty k \left(\frac{1}{2}\right)^{k-1} \\
&= \frac{1}{(1-1/2)^2} \\
&= 4
\end{align}
