Expected time for a random walk to exit an interval

Question

A simple symmetric random walk starts at $0$ and takes $\pm 1$ steps with probability $\tfrac12$ each. It stops upon reaching $-a$ or $+b$ (with $a, b > 0$ integers).

What is the expected number of steps until the walk stops?

Accepted Answer

Martingale route. For a symmetric walk, Mt = St^2 - t is a martingale: E[S{t+1}^2 \mid St] = 	frac12(St+1)^2 + 	frac12(St-1)^2 = St^2 + 1, so the drift of St^2 is exactly +1 per step, which -t cancels. Optional stopping at the exit time T (justified since the interval is bounded) gives E[ST^2] - E[T] = S0^2 - 0 = 0 \implies E[T] = E[ST^2]. Now ST \in \{-a, b\}. The gambler's-ruin probabilities give P(ST = b) = \frac{a}{a+b} (linear interpolation between barriers), so E[T] = E[ST^2] = \frac{a}{a+b}\,b^2 + \frac{b}{a+b}\,a^2 = \frac{ab(a + b)}{a+b} = ab. \boxed{E[T] = ab} Recurrence check. Tx…

Expected time for a random walk to exit an interval

Your answer

More Probability questions