Simple Random Walk, Generating Function and Markov Property

Question

My problem is about a simple random walk $ X_{n} $ with transition probabilities $ P_{i,i + 1} = p $ and $ P_{i, i-1} = 1-p $. I must prove that $ [\mathbb{E}_{1}(s^{T})]^2 = \mathbb{E}_{2}(s^{T}) $, where $ T = \min \{ n \ge 0: X_{n} = 0\} $. I would appreciate any hints. I've thought about it a lot but can't find a way to do it. I know I must apply the Markov property at some point but no more.

Answer 1

Maybe it's easier to see what Will M. said if you rephrase the problem a little. Let's define $$T_i^j = \min \{n \ge 0 : X_0=i, X_n=j\}$$ Note that $E(s^{T_i^{i-1}}) = E(s^{T_1^0}) = E(s^T) \text{, for every $i\in Z$}$, which is the generator function of the first passage time for $1$ step to the left.

Now for the exercise, it's easy to prove that: $$E(s^T | X_0=1) = s (1-p) + psE(s^T|X_0=2)$$ What you then have to note is that $E(s^T|X_0=1)^2 = E(s^T|X_0=2)$ since the first passage time for $2$ step to the left means that you first have to step $1$ to the left, then another. More precisely: $$T_i^{i-2} = T_{i}^{i-1} + T_{i-1}^{i-2}$$ $T_{i}^{i-1}$ and $T_{i-1}^{i-2}$ are independent, so $$E(s^{T_i^{i-2}}) = E(s^{T_{i}^{i-1} + T_{i-1}^{i-2}}) = E(s^{T_{i}^{i-1}}) E(s^{T_{i-1}^{i-2}}) = {E(s^T)}^2$$

You can substitute it to the above equation, and solve it, and you get: $$ E(s^T) = \frac{1 - \sqrt{1-4p(1-p)s^2}}{2ps} $$