Proving that expectation of stopping time of a random walk is finite

Question

Suppose we have a random walk, $S_n = X_1 + \cdots + X_n$ where $X_i = \pm 1$. I have proved that $M_n = S_n^2-n$ is a martingale. For fixed $N$, we define the stopping time \begin{align} T &= \min\{n: |S_n| = N\}\end{align} I am trying to prove that $\mathbb{E}[T] < \infty$ by showing that there exists $c<\infty$ and $\rho < 1$ (where $\rho$ depends on $N$) such that \begin{align} \mathbb{P}\{T>n\}\leq c\rho^n \end{align} I know that I should end up with $\mathbb{E}[T] = N^2$, so I am trying to reverse engineer a solution using Markov's inequality. However, this yields nothing fruitful. Any help would appreciated, thanks.

Answer 1

For any discrete random variable $T$ on the non-negative integers: $\mathbb E[T] = \sum\limits_{n=0}^\infty \mathbb P(T > n)$

So if $\mathbb P(T > n) \le c \rho^n$ then using a geometric series you get $\mathbb E[T] \le \frac{c}{1-\rho}$ which is finite

---

Added much later:

• If $|S_k| < N$ then $\mathbb P(|S_{k+2N} \ge N|) \ge \frac{1}{2^{2N}}$ since you just need $2N$ consecutive steps in the right direction of higher or equal probability

• This implies $\mathbb P(T > 2N) \le 1- \frac{1}{4^{N}}$ and $\mathbb P(T > k+2N) \le \left(1- \frac{1}{4^N}\right) \mathbb P(T > k)$

• This in turn implies $\mathbb P(T > n) \lt \left(1- \frac{1}{4^N}\right)^{(n-2N)/(2N)}$ $= \left(1- \frac{1}{4^N}\right)^{-1}\left(\left(1- \frac{1}{4^N}\right)^{1/(2N)}\right)^n $

• which means $\mathbb P(T > n) \lt c\rho^n$ with $c=\left(1- \frac{1}{4^N}\right)^{-1}$ and $\rho=\left(1- \frac{1}{4^N}\right)^{1/(2N)}$ and thus $\mathbb E[T]$ is finite

though this is extremely loose and $\mathbb P(T > n)$ and $\mathbb E[T]$ are in fact much smaller than this suggests