# Prove that expectation of a stopping time is (in)finite

Let $S_n$ be a simple random walk, with $S_0 = 0$ and $S_n = \sum_{i=1} ^{n} X_i$, where $P(X_i = 1) = P(X_i = -1) = \frac{1}{2}$ and the $X_i$ i.i.d.

Define the stopping time $T := \inf \{n \geq 0 : S_n \in \{a,b\} \}$, with $a <0 < b$.

How can I show whether $E[T] < \infty$ ?

I know that random walk in dimension 1 is recurrent, so the hitting times of $a$ and $b$ are finite, but I don't see how I can use this to show $E[T] < \infty$.

• Hint: Can you show that $$P(T>n+b-a\mid T>n)\leqslant1-\frac1{2^{b-a}}$$ for every $n$? – Did Oct 26 '16 at 22:02
• @Did $P(T>n+b-a\mid T>n) = \frac{P(T>n+b-a) P(T>n)}{P(T>n)} = P(T>n+b-a) = 1- P(T \leq n+b-a) = 1- \frac{1}{2^{n+b-a}} \leqslant1-\frac1{2^{b-a}}$ – clubkli Oct 26 '16 at 22:45
• No, already the first equality is wrong. – Did Oct 26 '16 at 22:48
• Then let's write $$P(T>n+b-a\mid T>n) = \frac{P(T>n+b-a ,T>n)}{P(T>n)} = \frac{P(T>n+b-a)}{P(T>n)} = \frac{1 - P(T \leq n+b-a)}{1 - P(T \leq n)} = \frac{1- \frac{1}{2^{n+b-a}}}{1- \frac{1}{2^{n}}}$$ – clubkli Oct 26 '16 at 23:03
• ?? But $P(T\leqslant n+b-a)\ne\frac1{2^{n+b-a}}$ and $P(T\leqslant n)\ne\frac1{2^n}$ in general, right? So what are you talking about? – Did Oct 26 '16 at 23:11

Hints:

1. Show that $S_n^2 -n$ is a martingale.
2. Apply the optional stopping theorem to the bounded stopping time $T \wedge n$ to conclude that $$\mathbb{E}(T \wedge n) = \mathbb{E}(S_{n \wedge T}^2)$$ for all $n \in \mathbb{N}$.
3. Show that $|S_{n \wedge T}| \leq M:=\max\{|a|,|b|\}+1$ to conclude that $$\mathbb{E}(T \wedge n) \leq M^2.$$
4. Apply the monotone convergence theorem.
• I hope reviving this very old question is possible. If we are in a situation where $p\neq q$, this approach seems to fail. What other approach would be possible in that case? – Charlie Shuffler Nov 13 '18 at 18:13
• @S.Crim If $p \neq q$, then $M_n := S_n - n(p-q)$ is a martingale, and using a very similar reasoning as above, you can show that $$(p-q) \mathbb{E}(T \wedge n) \leq \max\{|a|,|b|\};$$ it just remains to apply the monotone convergence theorem. – saz Nov 13 '18 at 18:34
• Thanks alot, I'll be back if I get stuck somewhere else. Do you also happen to know why the proof in the question in this post: math.stackexchange.com/q/1085399/537747 is valid? How come it is allowed to apply Wald's identity here? Isn't the stopping time dependent on the sequence? – Charlie Shuffler Nov 13 '18 at 18:35
• I'm not sure how the commenting works here but perhaps you didn't see my comment because I forgot to tag you. Edit: hm tagging with @ doesn't seem to work anyway – Charlie Shuffler Nov 13 '18 at 19:18
• @S.Crim This is one version of Wald's equation but not the one which you need (as wikipedia says this is the "basic version"). You can either read the next 2 Sections on Wikipeda or e.g. take a look at this question: math.stackexchange.com/q/2237301/36150 – saz Nov 13 '18 at 19:38