Frog jumping between states, expected time

Question

There is a frog which, when standing on the number $n$, will jump to $n-1$ with probability $0.6$ or to $n+1$ with probability $0.4$. The frog starts on number $2$, what is the expected value for the number of jumps the frog will take before reaching the number $1$ (for the first time)?

What I thought was: Let $T_{i,j}=\text{inf}\{n\in\mathbb{N}^{\star}:X_n=j\}|X_0=i$, where $X_n$ is the state of the frog after the jump number $n$. So we must find $\mathbb{E}[T_{2,1}]$. We have $$\mathbb{E}[T_{2,1}]=1+0.4 \mathbb{E}[T_{3,1}] \quad \text{and} \quad \mathbb{E}[T_{3,1}]=1+0.6 \mathbb{E}[T_{2,1}]+0.4 \mathbb{E}[T_{4,1}]$$ but then I couldn't figure out what to do next. The solution I found states that \begin{equation}\mathbb{E}[T_{3,1}]=2\mathbb{E}[T_{2,1}] \quad \quad \quad (\star)\end{equation} but I can't see why this is true. It says that the equality holds because of symmetry: "since the expected number of jumps to go from 3 to 2 is the same as the expected number of jumps to go from 2 to 1", but I think this means $\mathbb{E}[T_{3,2}]=\mathbb{E}[T_{2,1}]$ (I understand why this last equality is true) which I can't connect to $(\star)$. Could someone please explain why $(\star)$ is true?

Answer 1

Symmetry tells us that $\mathbb E[T_{3,2}] = \mathbb E[T_{2,1}]$, and we also have $\mathbb E[T_{3,1}] = \mathbb E[T_{3,2}] + \mathbb E[T_{2,1}]$ because

• In order to get from $3$ to $1$, you need to get to $2$ at some point, which takes $T_{3,2}$ steps.
• At that point, you're at $2$ and need to get to $1$, which takes $T_{2,1}$ steps.

So then you solve for $\mathbb E[T_{2,1}]$, with one catch: you should prove that these expectations are finite somehow.

For example, you could use the fact that $\mathbb E[T_{2,1}] = \sum_{k \ge 1} \Pr[T_{2,1} \ge k]$, and then put upper bounds on $\Pr[T_{2,1} \ge k]$. This is not hard, since $T_{2,1} \ge k$ requires at the very least that there are more $n+1$ steps than $n-1$ steps over an interval of length $k$, and the probability of this decays geometrically.

Answer 2

Let $e(k)$ be the expected number of jumps to reach the target if the frog is $k$ units to the right of the target.

We want to find $e(1)$.

Assuming $e(1)$ is finite, we get

\begin{align} e(1) &= {\small\frac{3}{5}}(1) + {\small\frac{2}{5}}(1 + e(2))\\[4pt] e(2) &= 2e(1)\quad\text{[i.e., e(1) + e(1)]}\\[4pt] \end{align}

Solving the above system of equations, we get $e(1) = 5.$

Explanation of why we have $e(2) = e(1) + e(1)\,$:

When the frog is $2$ units to the right of the target, it can set a new subgoal of reaching $1$ unit to the right of target. The expected number of jumps to achieve the subgoal is just $e(1).$ After achieving the subgoal, the frog is now $1$ unit to the right of the target, hence the expected number of jumps from that point is just another $e(1)$. Since the expected values add, we get $e(2) = e(1) + e(1).$