Positive-Drift First-Passage Times and Overshoots

Crossing a Threshold with Positive Drift

A random walk with positive mean increment tends to move upward over time, but it may fluctuate below its starting point before it crosses a given level. Its first crossing time is therefore random, and the crossing position need not equal the threshold. The difference—the overshoot—is essential when calculating the expected crossing time. Bounded increments make it possible to control both quantities without applying optional stopping to an unbounded time without justification.

Work on a probability space $(\Omega,\mathcal F,\mathbb P)$. Let $Y_1,Y_2,\ldots$ be independent, identically distributed random variables with $\mathbb E[|Y_1|]<\infty$, and define the discrete-time random walk $S_0=0$, $S_n=\sum_{k=1}^nY_k$, with state space $\mathbb R$. Let $\mathcal F_n=\sigma(Y_1,\ldots,Y_n)$, with $\mathcal F_0=\{\varnothing,\Omega\}$. Assume there are constants $c>0$ and $m>0$ such that $|Y_k|\le c$ almost surely for every $k$, and $\mathbb E[Y_1]=m$. For a fixed threshold $a>0$, define the first-passage time and overshoot by

T_a=\inf\{n\ge 0:S_n\ge a\},\qquad O_a=S_{T_a}-a

when $T_a<\infty$. The event $\{T_a\le n\}$ is determined by $S_0,\ldots,S_n$, so $T_a$ is a stopping time for $(\mathcal F_n)$. Since $S_0=0<a$, any finite $T_a$ is at least $1$.

Theorem (First-passage bound and overshoot identity): Under the assumptions above, $T_a<\infty$ almost surely, $\mathbb E[T_a]<\infty$, and $0\le O_a<c$ almost surely. Moreover, $$ m\mathbb E[T_a]=a+\mathbb E[O_a], \qquad \frac{a}{m}\le \mathbb E[T_a]<\frac{a+c}{m}. $$

The proof first works with the bounded stopping time $T_a\wedge n$. Before the crossing, the walk is below $a$; at the crossing, bounded increments prevent it from jumping as far as $a+c$ or beyond. These facts bound the stopped position from above. Positive drift then bounds the expected length of the stopped horizon, uniformly in $n$.

Proof. Write $T=T_a$. For each integer $n\ge1$, the finite sum defining the stopped position is $$ S_{T\wedge n}=\sum_{k=1}^{n}Y_k\mathbf 1_{\{T\ge k\}}. $$ Indeed, the $k$-th increment is included exactly when the walk has not crossed before step $k$. The event $\{T\ge k\}$ belongs to $\mathcal F_{k-1}$, and $Y_k$ is independent of $\mathcal F_{k-1}$. Thus $\mathbb E[Y_k\mathbf 1_{\{T\ge k\}}]=m\mathbb P(T\ge k)$. Summing the finite number of terms and using $\mathbb E[T\wedge n]=\sum_{k=1}^n\mathbb P(T\ge k)$ gives $$ \mathbb E[S_{T\wedge n}]=m\mathbb E[T\wedge n]. $$ Pathwise, if $T\le n$, then $S_{T-1}<a$ and $Y_T\le c$, so $S_{T\wedge n}=S_T<a+c$. If $T>n$, then $S_n<a$, so again $S_{T\wedge n}<a+c$. Therefore $m\mathbb E[T\wedge n]\le a+c$. As $n$ increases, $T\wedge n$ increases to $T$; monotone convergence yields $\mathbb E[T]\le(a+c)/m<\infty$. In particular, $T<\infty$ almost surely.

At the crossing, $S_{T-1}<a$ and $Y_T\le c$, so $a\le S_T<a+c$, proving $0\le O_a<c$. To obtain the identity at $T$, use the same sum over all $k\ge1$. Its terms are absolutely integrable in total because $$ \mathbb E\left[\sum_{k\ge1}|Y_k|\mathbf 1_{\{T\ge k\}}\right] \le c\sum_{k\ge1}\mathbb P(T\ge k) =c\mathbb E[T]<\infty. $$ Consequently expectation and summation can be interchanged. Independence of $Y_k$ from $\mathcal F_{k-1}$ gives $$ \mathbb E[S_T]=\sum_{k\ge1}m\mathbb P(T\ge k)=m\mathbb E[T]. $$ Since $S_T=a+O_a$, this is the claimed identity. Finally, $O_a\ge0$ gives $m\mathbb E[T]\ge a$, while $O_a<c$ almost surely and is bounded, so $\mathbb E[O_a]<c$. Dividing by $m>0$ gives both bounds. $\square$

Using the Identity

The exact identity separates the threshold from the extra distance travelled at the crossing. The lower bound $a/m$ is attained when the overshoot is zero almost surely. Otherwise the expected time exceeds $a/m$ by precisely $\mathbb E[O_a]/m$. The upper bound uses only the maximum increment; it does not require finding the distribution of the overshoot.

Worked Example: Positive Increments and a Nonzero Overshoot

Let each increment independently equal $1$ or $2$, each with probability $\tfrac12$, and take $a=3$. Here $m=\tfrac12(1)+\tfrac12(2)=\tfrac32$, and the bound $|Y_k|\le2$ holds. The threshold is crossed by step $3$. Listing the possible stopped paths gives:

In two steps, the path $2,2$ crosses at $S_2=4$, with probability $\tfrac14$, time $2$, and overshoot $1$.
The paths $1,2$ and $2,1$ cross at $S_2=3$, with total probability $\tfrac12$, time $2$, and overshoot $0$.
After the path $1,1$, whose probability is $\tfrac14$, the third increment crosses the threshold. A third increment of $1$ has joint probability $\tfrac14\cdot\tfrac12=\tfrac18$, gives $S_3=3$, and has overshoot $0$. A third increment of $2$ has joint probability $\tfrac18$, gives $S_3=4$, and has overshoot $1$.

Thus $\mathbb E[T_3]=2(\tfrac34)+3(\tfrac14)=\tfrac94$, and $\mathbb E[O_3]=1(\tfrac14)+1(\tfrac18)=\tfrac38$. Substitution checks the identity: $$ m\mathbb E[T_3]=\tfrac32\cdot\tfrac94=\tfrac{27}{8} =3+\tfrac38=a+\mathbb E[O_3]. $$ The theorem's bounds also give $\tfrac{3}{3/2}=2\le\tfrac94<\tfrac{3+2}{3/2}=\tfrac{10}{3}$, which the computed expectation satisfies.

Worked Example: Nearest-Neighbor Steps and Zero Overshoot

Suppose each increment equals $1$ with probability $\tfrac34$ and $-1$ with probability $\tfrac14$. Take $a=2$. The mean increment is $m=\tfrac34(1)+\tfrac14(-1)=\tfrac12>0$, and $|Y_k|\le1$. At the first crossing of $2$, the walk must be at $2$: its previous position is an integer less than $2$, and its next step is at most $1$. Thus $O_2=0$ almost surely. The theorem first guarantees that this crossing occurs almost surely with finite mean; its identity then gives $$ \mathbb E[T_2]=\frac{2+\mathbb E[O_2]}{m} =\frac{2+0}{1/2}=4. $$ For a bound check, the theorem gives $4\le\mathbb E[T_2]<\frac{2+1}{1/2}=6$, consistent with the exact value. The zero overshoot, rather than positive drift alone, is why the lower bound is attained.

Worked Example: Fractional Steps and Several Crossing Positions

Let each increment independently equal $\tfrac12$ or $\tfrac32$, each with probability $\tfrac12$, and take $a=2$. The mean is $m=\tfrac12(\tfrac12)+\tfrac12(\tfrac32)=1$, and $|Y_k|\le\tfrac32$. Write $L$ for an increment of $\tfrac12$ and $H$ for an increment of $\tfrac32$. All stopped paths are $HH$, $HL$, $LH$, $LLH$, $LLLH$, and $LLLL$. Their probabilities are respectively $\tfrac14,\tfrac14,\tfrac14,\tfrac18,\tfrac1{16},\tfrac1{16}$, which sum to $1$. Their stopping times and overshoots are:

$HH$: time $2$, position $3$, overshoot $1$.
$HL$ and $LH$: time $2$, position $2$, overshoot $0$ for each path.
$LLH$: time $3$, position $\tfrac52$, overshoot $\tfrac12$.
$LLLH$: time $4$, position $3$, overshoot $1$.
$LLLL$: time $4$, position $2$, overshoot $0$.

Therefore $$ \mathbb E[T_2]=2\left(\tfrac14+\tfrac14+\tfrac14\right) +3\left(\tfrac18\right)+4\left(\tfrac1{16}+\tfrac1{16}\right) =\tfrac{19}{8}, $$ and $$ \mathbb E[O_2]=1\left(\tfrac14\right) +\tfrac12\left(\tfrac18\right)+1\left(\tfrac1{16}\right) =\tfrac38. $$ The identity checks exactly: $m\mathbb E[T_2]=1\cdot\tfrac{19}{8}=2+\tfrac38$. The general bounds are $2\le\tfrac{19}{8}<\frac{2+3/2}{1}=\tfrac72$.

Why Truncation Matters

The proof does not assume that optional stopping applies directly to $S_{T_a}$. Instead, it first uses the finite sum for $S_{T_a\wedge n}$, where the stopping horizon is bounded, and then proves that $\mathbb E[T_a]$ is finite. The absolute-integrability argument justifies passing from the truncated sums to the sum at $T_a$. This order matters: a positive mean increment and bounded increments provide the needed control, but they do not make an unqualified optional-stopping step valid by themselves.

Common mistake: ignoring the overshoot. In the first example, setting $m\mathbb E[T_3]=a$ would give $\mathbb E[T_3]=3/(\tfrac32)=2$. That is incorrect: the computed crossing paths have mean overshoot $\tfrac38$, so the correct calculation is $$ \mathbb E[T_3]=\frac{a+\mathbb E[O_3]}{m} =\frac{3+\tfrac38}{\tfrac32}=\frac94. $$ The calculation $a/m$ is valid only when the overshoot has mean zero, which here would require $O_3=0$ almost surely.

Takeaway: For an iid random walk with bounded increments and positive mean $m$, crossing a positive threshold $a$ has finite expected time. The exact correction to $a/m$ is the expected overshoot divided by $m$; bounded increments keep that correction below $c/m$.

Check Your Understanding

For each question, specify the assumptions you use and verify any numerical result by substitution.

If $m=2$, $a=5$, and $|Y_k|\le3$, what bounds does the theorem give for $\mathbb E[T_a]$?
For increments $1$ and $2$, each with probability $\tfrac12$, find the probability that the walk crosses threshold $2$ at time $1$, and compute its overshoot on that event.
Why does $O_a<c$ hold at a finite crossing when $|Y_k|\le c$, rather than only $O_a\le c$?
In the nearest-neighbor example, which feature of the increment sizes forces the overshoot to be zero?
What integrability bound justifies interchanging expectation and the infinite sum in the proof of the overshoot identity?

Positive-Drift First-Passage Times and Overshoots

What You'll Learn