Exercise: Expected Exit Time from a Bounded Interval

Prerequisites: Optional Stopping Theorem, Martingales (Discrete Time)

Problem

A symmetric random walk $S_n$ starts at $k \in (0, N)$ and exits the interval $(0, N)$ at the stopping time $\tau = \inf\{n : S_n \in \{0, N\}\}$.

1. Show that $Y_n = S_n^2 - n$ is a martingale. (Hint: expand $(S_n + X_{n+1})^2$ and use $\mathbb{E}[X_{n+1}] = 0$, $\mathbb{E}[X_{n+1}^2] = 1$.)

2. Verify that OST applies to $Y_n$ at the stopping time $\tau$. Use condition (3): bounded increments and $\mathbb{E}[\tau] < \infty$.

3. Apply OST to $Y$ at $\tau$ and derive $\mathbb{E}[\tau] = k(N - k)$. (You will use the symmetric walk's gambler's-ruin result $\mathbb{P}(S_\tau = N) = k/N$.)

4. Concrete case. Compute $\mathbb{E}[\tau]$ for $(k, N) = (50, 100)$. If each step takes $1$ second, how many seconds on average until the walk exits? Plot $\mathbb{E}[\tau]$ as a function of $k$ for $N = 100$ and observe the parabola.

Hint

For part 2, that $\mathbb{E}[\tau] < \infty$ can be proved by a geometric tail bound — e.g. the probability of exiting in any block of $N$ consecutive steps is at least some $\epsilon > 0$, so $\tau$ has an exponential tail.