This is Exercise 3.2 from the book Understanding Markov Chains that I'm getting stuck at.
Consider a random walk $(S_n)$ on $\mathbb{Z}$ with independent increments and probabilities $p$, resp. $q = 1 – p$ of moving up by one step, resp. down by one step. Let
$$
T_0 = \inf\{n \ge 0: S_n = 0\}
$$
denote the hitting time of state $0$. Explain why for any $k \ge 1$, we have
$$
\mathbb{E}[T_0 \vert S_0 = k] = k\mathbb{E}[T_0 \vert S_0 = 1]
$$
I tried to show this by induction but this approach requires to compute $\mathbb{E}[T_0 \vert S_0 = 1]$ beforehand, which is not intention of this exercise. So if you guys have any hints/guides, it would be greatly appreciated. Thanks in advanced !
Best Answer
Thanks to @RhysSteele's comment, I'll post this answer for future reference.
Let $T_0 = \inf\{n \ge 0: X_n = 0\}$ and $T_1 = \inf\{n \ge 0: X_n = 1\}$. Conditional on $S_0 = k \ge 1$, one must have $T_1 \le T_0$. Now, $$ \begin{align*} \mathbb{E}[T_0 \vert S_0 = k] &= \mathbb{E}[T_1 + (T_0 - T_1) \vert S_0 = k]\\ &= \mathbb{E}[T_1 \vert S_0 = k] + \mathbb{E}[T_0 - T_1 \vert S_0 = k] \end{align*} $$ By the Markov property, we have $\mathbb{E}[T_1 \vert S_0 = k] = \mathbb{E}[T_0 \vert S_0 = k - 1]$. Moreover, notice that $$ (T_0 - T_1)\vert \{S_0 = k\} = \inf\{n \ge T_1: X_n = 0\} \vert \{S_0 = k\} $$ Thus, by the strong Markov property, $\mathbb{E}[T_0 - T_1 \vert S_0 = k] = \mathbb{E}[T_0 \vert S_0 = 1]$. Therefore, $$ \mathbb{E}[T_0 \vert S_0 = k] = \mathbb{E}[T_0 \vert S_0 = k - 1] + \mathbb{E}[T_0 \vert S_0 = 1] $$ Applying this for $k$ times, we have $$ \mathbb{E}[T_0 \vert S_0 = k] = k\mathbb{E}[T_0 \vert S_0 = 1] $$