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

  • $\begingroup$ Hint: Can you show that $$P(T>n+b-a\mid T>n)\leqslant1-\frac1{2^{b-a}}$$ for every $n$? $\endgroup$ – Did Oct 26 '16 at 22:02
  • $\begingroup$ @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}}$ $\endgroup$ – clubkli Oct 26 '16 at 22:45
  • $\begingroup$ No, already the first equality is wrong. $\endgroup$ – Did Oct 26 '16 at 22:48
  • $\begingroup$ 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}}}$$ $\endgroup$ – clubkli Oct 26 '16 at 23:03
  • $\begingroup$ ?? 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? $\endgroup$ – Did Oct 26 '16 at 23:11


  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.
  • $\begingroup$ 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? $\endgroup$ – Charlie Shuffler Nov 13 '18 at 18:13
  • 1
    $\begingroup$ @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. $\endgroup$ – saz Nov 13 '18 at 18:34
  • $\begingroup$ 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? $\endgroup$ – Charlie Shuffler Nov 13 '18 at 18:35
  • $\begingroup$ 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 $\endgroup$ – Charlie Shuffler Nov 13 '18 at 19:18
  • 1
    $\begingroup$ @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 $\endgroup$ – saz Nov 13 '18 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.