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?
Best Answer
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).$$