# Upper bound for random walk to show stopping time is bounded

I have a simple symmetric random walk (SSRW), and a stopping time: $\tau=\inf\{ n \geq 0 ~:~ |S_n|=N\}$. I am showing that $\newcommand{\ee}[1]{\mathbb{E}[#1]}$ $\newcommand{\pp}[1]{\mathbb{P}[#1]}$

$\ee{\tau}=N^2$

Since $S_n^2-n$ is a martingale, provided we have $\tau < \infty$ a.s. then I can apply optional stopping theorem here and $\ee{S_\tau^2-\tau}=N^2-\ee{\tau}=0$ giving me the result.

I wanted to show that with $E_k:=\{ \tau\geq k\}$, we have $\pp{\limsup_n E_n}=0$ all I need is $\sum_{k=1}^\infty \pp{E_k} < \infty$ then I may apply the Borel-Cantelli lemma.

$E_k=\{ \max_{1\leq n \leq k}|S_n| \leq N \}$, there must be a summable upper bound for the probability of this event I may use?

Unfortunately, I'm not aware of a nice (simple) bound to estimate the probabilities. (Note that the Borel-Cantelli lemma gives only a sufficient condition for $\mathbb{P}(\limsup_{n \to \infty} E_n) = 0$; so, in general, we cannot expect that the series converges.)

However, there is a simple way out: First consider the stopping time $\tau_k := \min\{\tau,k\}$ for fixed $k \in \mathbb{N}$. Obviously, $\tau_k$ is a bounded stopping time (so we have in particular $\tau_k<\infty$), and therefore it follows from the optional stopping theorem that

$$\mathbb{E}(S_{\tau_k}^2) = \mathbb{E}(\tau_k). \tag{1}$$

Since $\tau_k \uparrow \tau$ as $k \to \infty$, it follows from the monotone convergence theorem (MCT) that

\begin{align*} \mathbb{E}(\tau) = \mathbb{E}\left( \sup_{k \in \mathbb{N}} \tau_k \right) \stackrel{\text{MCT}}{=} \sup_{k \in \mathbb{N}} \mathbb{E}(\tau_k) &= \lim_{k \to \infty} \mathbb{E}(\tau_k) \\ &\stackrel{(1)}{=} \lim_{k \to \infty} \mathbb{E}(|S_{\tau_k}|^2). \tag{2} \end{align*}

As $|S_{\tau_k}| \leq N$, this shows in particular that $\mathbb{E}(\tau) \leq N^2$. This, in turn, implies that $S_{\tau}$ is almost surely well-defined. Applying the dominated convergence theorem in $(2)$ we conclude

$$\mathbb{E}(\tau)= \mathbb{E}(S_{\tau}^2).$$

• Thank you for the answer. This is very similar to the solution given in the lecture notes but it is just not something I would have thought have by myself hence attempting it in a more obvious, though impractical way. I do have a question though - in the solution I was given $\tau \wedge k \to \tau$ if $P(\tau < \infty )=1$ and Borel-Cantelli is still used. Is this necessary? – shilov Dec 26 '15 at 20:31
• @shilov No, it is not necessary. If $\tau(\omega) = \infty$ for some $\omega$, then $k=\tau(\omega) \wedge k \uparrow \tau(\omega)=\infty$ still holds true. I have slighlty rewritten my answer. The important point is to notice first that $\mathbb{E}(\tau)<\infty$ (since this implies $\tau<\infty$ a.s) before applying the dominated convergence theorem. The reason is simply that we need pointwise convergence $S_{\tau_k} \to S_{\tau}$ in order to apply the dominated convergence theorem; and this holds only true for $\omega \in \{\tau<\infty\}$ (... the expression $S_{\infty}(\omega)$ is not [...] – saz Dec 26 '15 at 21:45
• ... even well-defined. – saz Dec 26 '15 at 21:45