Exercise: Where OST Fails — The Symmetric Walk Hits One

Prerequisites: Optional Stopping Theorem, Stopping Times

Problem

Let $S_n$ be a symmetric random walk on $\mathbb{Z}$ starting at $S_0 = 0$, and $\tau = \inf\{n : S_n = 1\}$.

1. It is a classical result that a symmetric random walk on $\mathbb{Z}$ is recurrent — with probability 1, it visits every integer infinitely often. In particular, $\tau < \infty$ a.s. Compute $S_\tau$ and $\mathbb{E}[S_\tau]$.

2. Compute $\mathbb{E}[S_0]$.

3. The above shows $\mathbb{E}[S_\tau] \ne \mathbb{E}[S_0]$, so OST fails. Check each hypothesis of OST and identify which one is violated. Specifically:

   • Is $\tau$ bounded?
   • Is $S_n$ bounded on $\{n \le \tau\}$?
   • Is $\mathbb{E}[\tau] < \infty$ with bounded increments?
4. Numerical demonstration. Simulate $N = 10{,}000$ paths of the random walk starting at $0$, stopping each at the first hit of $+1$ (within a compute budget of, say, $T_{\max} = 100{,}000$ steps). Plot a histogram of $\tau$ values. Explain what the plot looks like and how it relates to the failure of OST.

Hint