Stochastic Calculus

Lesson 3 of 11

First Passage and the Running Maximum

How long a random walk or a stock takes to first reach a level. It always gets there but the average wait is infinite, and touching a level is twice as likely as finishing above it.

The first time a walk hits a level

Start a fair ±1\pm1 walk MnM_n at 00 and fix a level mm. The first passage time τm=min⁡{n:Mn=m}\tau_m = \min\{n : M_n = m\} is the first step at which the walk stands on mm. It is a stopping time: you can tell whether τm=n\tau_m = n from the first nn steps alone.

Take m=1m = 1 and count paths, writing U for a step up and D for a step down. The walk can only land on 11 after an odd number of steps. It gets there at step 1 with U, probability 12\tfrac12. At step 3 it needs DUU, probability 18\tfrac18. At step 5 there are two paths, DUDUU and DDUUU, so 232=116\tfrac{2}{32} = \tfrac1{16}. At step 7 there are five. The counts 1,1,2,5,14,…1, 1, 2, 5, 14, \dots are the Catalan numbers, and in general

P(τ1=2j−1)=Cj−122j−1,Ck=1k+1(2kk).P(\tau_1 = 2j-1) = \frac{C_{j-1}}{2^{2j-1}}, \qquad C_k = \frac{1}{k+1}\binom{2k}{k}.

The reason is that the first 2j−22j-2 steps must bring the walk back to 00 without ever going above it, and the last step goes up. Catalan numbers count exactly those returns.

Adding the first four terms,

P(τ1≤7)=12+18+116+5128=93128≈0.73,P(\tau_1 \le 7) = \tfrac12 + \tfrac18 + \tfrac1{16} + \tfrac5{128} = \tfrac{93}{128} \approx 0.73,

so after seven fair flips about 27% of walkers have never been ahead.