Markov Chain: Calculating Expectation Reach a Certain Set of States

Question

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:

1. 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:

1. I can go from State $1-2-3$. Time is $2$ when base is reached and probability $\frac{1}{2} \cdot \frac{1}{2}$
2. $1-2-1-2-3$. Time is $4$ when base is reached. Probability of occurring is $\frac{1}{16}$.
3. $1-2-1-2-1-2-3$. Time is $6$ when base is reached. Probability of occurring is $\frac{1}{64}$
4. $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}$

5. 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}$
6. $1-6-1-6-5$. Time is $4$ when base is reached. Probability of occurring is $\frac{1}{16}$.
7. $1-6-1-6-1-6-5$. Time is $6$ when base is reached. Probability of occurring is $\frac{1}{64}$
8. $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:

8. $1-2-1-6-5.$ The time is $4$ probability $1/16$
9. $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

Answer 1

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$.

Answer 2

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$.

Answer 3

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}