First exit time for Brownian motion without drift

I am dealing with the simulation of particles exhibiting Brownian motion without drift, currently by updating the position in given time steps $\Delta t$ by random displacement in each direction drawn from $N(0,k\Delta t)$ (k being a particle-specific constant).

Now, I would rather fix the displacement to a specific value and calculate random numbers representing the time it would take a particle to first travel that far from its previous position (no matter whether that is in the positive or negative direction). What is the appropriate distribution to draw these $\Delta t$ from?

I learned (from wikipedia, since I do not have much of a background here) that for Brownian motion with drift the first passage time follows an Inverse Gaussian distribution and for zero drift a Lévy distribution, but do not see how to arrive at the appropriate parameters. As a test, I generated random numbers from N(0,1) and summed them up until |sum| exceeded some threshold $\alpha$ (I tested 3 to 7). The number of summands needed seemed to be distributed according to an Inverse Gaussian distribution with the parameters roughly following $\mu = \alpha^2+\alpha+1$ and $\lambda = 1.5\alpha^2+2\alpha+1$. I cannot see it matching any Lévy distribution, and it is not intuitively clear to me why the values I am looking for should have an expected value of $\infty$ anyway.

• – Shai Covo Apr 11 '11 at 14:19
• If I understand you correctly, you want the first exit time of a symmetric interval $(-\alpha,\alpha)$. That exit time is roughly exponential and has finite mean and variance. This is quite different from the first exit time of $(-\infty,\alpha)$, which might be what your references are discussing. – Douglas Zare Apr 11 '11 at 15:33
• @Shai Covo: Thanks for the link. I looked at quite a few questions including "Brownian motion" before asking, but at this one, I did not get far past "[t]his is easily derived"...well, not easy for me. @Dougla Zare: Yes! Exit time is the term I was missing. However, with an exponential distribution it would be a memoryless process, right? That seems to contradict my ad-hoc test results (mode > 0). – arne.b Apr 11 '11 at 19:19
• There's no closed for expression for this. You can compute the distribution of the exit time as an infinite sum of distributions of hitting times at the positive levels $n\alpha$ ($n=1,2,...$). As a first approximation, the probability of $\vert B_t\vert$ hitting $\alpha$ is about twice the probability of $B_t$ hitting $\alpha$. For a next approximation, you can subtract off the probability of B hitting both $\alpha$ and $-\alpha$, which is about twice the probability of B hitting $2\alpha$. Continue in this way, applying inclusion-exclusion to get an infinite series (with alternating signs). – George Lowther Apr 12 '11 at 2:37
• This is just applying the reflection principle about the barriers at $\alpha$ and $-\alpha$. Reflecting about two barriers gives you an infinite sequence (much like the infinite reflections when you have mirrors on opposing walls). This is quite common, and well known in finance for pricing double barrier options. – George Lowther Apr 12 '11 at 2:41

My interpretation is that you want to know how long it takes a Brownian motion without drift $B(t)$ to exit $(-\alpha,\alpha)$. This is quite different from the exit time from $(-\infty,\alpha)$ which is discussed in some of the references you mention. I think this is a standard problem, but I'll just work out some of the properties from first principles.

Let the first exit time be $\tau_\alpha$. The value of $E[\tau_\alpha]$ is easy to determine since $B(t)^2 - t$ is a martingale. $B(\tau_\alpha)^2-\tau_\alpha = \alpha^2 - \tau_\alpha$ so $0=E[\alpha^2 -\tau_\alpha],$ so $E[\tau_\alpha]=\alpha^2$.

We can get the probability density function for $B(t\wedge\tau_\alpha)$ by using the reflection principle, reflecting on $2$ barriers instead of $1$. Count paths ending in each band of width $2\alpha$, $((2k-1)\alpha,(2k+1)\alpha)$ with weight $(-1)^k$. This weighting means that reflecting the Brownian motion the first time you hit $\pm\alpha$ will reverse the sign, so the weights of the paths which hit the barrier at least once cancel. The sum of the weighted densities equals the density of $B(t\wedge \tau_\alpha)$. For $-\alpha \lt y \lt \alpha$ the density of $B(t\wedge\tau_\alpha)$ is $\sum_k \mu_t(y+4k\alpha) - \sum_k \mu_t(-y+(4k-1)\alpha)$ where $\mu_t(x) =\frac{1}{\sqrt{2\pi t}}\exp(\frac{-x^2}{2t})$ is the density of $N(0,t)$ at $x$. This sum can be expressed in terms of theta functions. For $-\alpha \lt y \lt \alpha$, the density of $B(t \wedge \tau_\alpha)$ is

$$\frac {1}{4\alpha} \left( \theta_3\left(\frac{\pi y}{4 \alpha},\exp(\frac{-\pi^2 t}{8 \alpha^2})\right) - \theta_3\left(\frac{\pi}{4} + \frac{\pi y}{4\alpha},\exp(\frac{-\pi^2 t}{8 \alpha^2})\right) \right)$$

The integral of this on $(-\alpha,\alpha)$ gives you the probability that $\tau_\alpha \gt t$. I don't recall if this simplifies. You can also read off the density of $\tau_\alpha$ from this.

Anyway, for most purposes you don't need to get the times exactly right, and you may prefer to use a constant time of $\alpha^2$.

If you dig further in Wikipedia then you will find the statement

The time of hitting a single point $\alpha$ (different from the starting point 0) by the Brownian motion has the Lévy distribution with $c = \alpha^2$.

though this applies to a standard Wiener process without drift.

It therefore gives a cumulative distribution function

$$Pr(\tau _a \le t) = \operatorname{erfc} \left( \frac{\alpha}{\sqrt {2t}} \right) = 2 \Phi\left(\frac{-\alpha}{\sqrt {t}} \right)$$

related to the complementary error function and the cumulative distribution of a standard normal.

Added: I had missed that you were looking for the distribution leaving a corridor rather than hitting a single boundary. That makes a big difference as the process cannot head a long way off in the other direction.

This note (top of page 15) states that for a driftless Brownian process starting at $0$ the expected exit time from the corridor $(x_1, x_2)$ with $x_1 < 0 < x_2$ is $-x_1 x_2$. So in your case the expected time is $\alpha^2$. Earlier it gives the more complicated equivalent for a Brownian process with drift.

Wikipedia's article Wiener process produces the same result when it says

$W_t^2 - t$ is a martingale, which shows that the quadratic variation of $W$ on $[0,t]$is equal to $t$. It follows that the expected time of first exit of $W$ from $(-c,c)$ is equal to $c^2$.

You should find something similar in your simulations of random walks, that the expected number of steps to first hit $\pm \alpha$ is $\alpha^2$

• I think it is interesting that, since $\mathbb{P}(\tau_a \leq t) = \mathbb{P}(\sup_{0 \leq s \leq t} W_t \geq a)$, then this means that $M_t = \sup_{0 \leq s \leq t} W_t$ is equal in distribution to $\sqrt{t}|Z|$ where $Z$ is standard normal. That doesn't seem obvious at first blush. – cardinal Apr 12 '11 at 3:00
• $W_t$ should be $W_s$ (of course) in two places in my comment above. – cardinal Apr 12 '11 at 11:57