Overshoots and Failures of Optional Stopping

When Stopping Does Not End the Argument

A random walk may reach a boundary with probability one, yet its stopped values at bounded approximations can have expectations that do not converge to the expectation at the boundary. The obstacle is not pointwise convergence: if the exit time is finite, the bounded stopping times eventually agree with it on each sample path. The obstacle is that rare paths can carry increasingly large contributions to expectation.

Overshoots make the issue especially visible. A nearest-neighbor walk that crosses a level lands exactly on it; a walk with larger jumps can pass beyond it. Even when the overshoot is bounded, the stopped martingale before exit need not be uniformly integrable. We will separate these two issues and see precisely why almost-sure stopping alone is insufficient.

Exit Times and Overshoots

Let \((\xi_k)_{k\ge1}\) be independent, identically distributed integer-valued increments, and define the random walk by \(S_0=x\) and \(S_n=x+\sum_{k=1}^n \xi_k\). For a level \(b>x\), its upward crossing time is \(T_b=\inf\{n\ge0:S_n\ge b\}\), with the convention \(\inf\varnothing=\infty\).

Definition: On the event \(T_b<\infty\), the overshoot above \(b\) is \(O_b=S_{T_b}-b\). Thus \(O_b\ge0\), and it is zero exactly when the walk lands on the boundary.

If every increment is at most \(c\), where \(c>0\), then \(0\le O_b<c\): immediately before crossing, the walk is below \(b\), and its last jump is at most \(c\). This controls the terminal overshoot, but it does not control the values \(S_{T_b\wedge n}\) along paths that have not yet crossed. Those values can be far below the boundary.

For a martingale \(M_n\) and a stopping time \(T\), the bounded stopping times \(T\wedge n\) satisfy \(\mathbb E[M_{T\wedge n}]=\mathbb E[M_0]\) under the usual integrability assumptions. If \(T<\infty\) almost surely, then \(M_{T\wedge n}\to M_T\) almost surely. But almost-sure convergence alone does not imply convergence of expectations. A sufficient condition is uniform integrability.

Definition: A family of integrable random variables \(\{Y_n:n\ge1\}\) is uniformly integrable if, for every \(\varepsilon>0\), there is a \(K<\infty\) such that \(\sup_n\mathbb E\bigl[|Y_n|\mathbf 1_{\{|Y_n|>K\}}\bigr]<\varepsilon\).

A Safe Passage to the Limit

Theorem: Suppose \(M_n\) is a martingale with \(\mathbb E|M_0|<\infty\), \(T<\infty\) almost surely, and the family \(\{M_{T\wedge n}:n\ge1\}\) is uniformly integrable. Then \(M_T\) is integrable and \(\mathbb E[M_T]=\mathbb E[M_0]\).

Proof. Since \(T<\infty\) almost surely, for every path with finite \(T\), \(M_{T\wedge n}=M_T\) for all \(n\ge T\). Hence \(M_{T\wedge n}\to M_T\) almost surely. Fatou's lemma gives \(\mathbb E|M_T|\le\liminf_n\mathbb E|M_{T\wedge n}|<\infty\); the expectations on the right are bounded because a uniformly integrable family has bounded first moments.

Uniform integrability and almost-sure convergence imply convergence in \(L^1\). To see the relevant mechanism, truncate each variable to the interval \([-K,K]\). The truncated variables converge almost surely and are bounded, so their expectations converge by dominated convergence. Uniform integrability makes the expected absolute truncation errors uniformly small for sufficiently large \(K\); Fatou's lemma gives the same tail control for the limit. Letting \(K\) increase therefore yields \(\mathbb E|M_{T\wedge n}-M_T|\to0\). In particular, their expectations converge. Applying optional stopping at the bounded time \(T\wedge n\), \(\mathbb E[M_{T\wedge n}]=\mathbb E[M_0]\); passing to the limit proves the claim. \(\square\)

The hypothesis is about the whole family of stopped values, not just the terminal value. Even if \(M_T\) is bounded, the approximating variables can have rare, large excursions that prevent uniform integrability.

Worked Example: A Symmetric Walk That Hits but Has Infinite Mean Hitting Time

Let \(S_0=0\) and let the increments be independent with probabilities \(1/2\) each of \(+1\) and \(-1\). Set \(T=\inf\{n\ge0:S_n=-1\}\). First, \(T<\infty\) almost surely. For each positive integer \(N\), the finite-interval ruin probability gives \(\mathbb P(\text{hit }-1\text{ before }N)=N/(N+1)\). Each such event implies \(T<\infty\); letting \(N\to\infty\) proves the assertion.

The walk \((S_n)\) is a martingale. At each bounded time \(T\wedge n\), optional stopping gives \(\mathbb E[S_{T\wedge n}]=0\). Yet \(S_{T\wedge n}\to S_T=-1\) almost surely, so the limiting expectation is \(-1\), not \(0\). Here \(S_T\) is bounded; it is the family of approximating stopped values that fails the needed expectation convergence.

In fact, \(\mathbb E[T]=\infty\). If \(\mathbb E[T]<\infty\), write \(S_T=\sum_{k\ge1}\xi_k\mathbf 1_{\{T\ge k\}}\). Since \(\{T\ge k\}\) depends only on the first \(k-1\) increments, it is independent of \(\xi_k\), whose mean is zero. Moreover, \(\sum_{k\ge1}\mathbb E[|\xi_k|\mathbf 1_{\{T\ge k\}}]=\sum_{k\ge1}\mathbb P(T\ge k)=\mathbb E[T]<\infty\). Thus the series can be integrated term by term and \(\mathbb E[S_T]=0\), contradicting \(S_T=-1\). So almost-sure hitting does not imply finite expected hitting time.

Overshoot in a Centered Walk

The next example has nonzero overshoots and gives a second failure of expectation convergence. Its increments have mean zero, so the walk itself is a martingale. We verify that the upward crossing occurs almost surely rather than assuming it.

Worked Example: A Centered Walk Crossing Above a Level

Let \(S_0=0\), with independent increments satisfying \(\mathbb P(\xi_k=2)=1/3\) and \(\mathbb P(\xi_k=-1)=2/3\). Since \(\mathbb E[\xi_k]=2/3-2/3=0\), \((S_n)\) is a martingale. Let \(T=\inf\{n\ge0:S_n\ge1\}\).

For a positive integer \(m\), define \(\tau_m=\inf\{n\ge0:S_n\ge1\text{ or }S_n\le-m\}\). This exit time is finite almost surely: while the walk is inside the finite set \(\{-m+1,\ldots,0\}\), a run of \(m\) consecutive \(-1\) increments forces exit. In successive blocks of \(m\) steps, the conditional probability of such a run is \((2/3)^m>0\), so the probability of remaining inside for \(j\) blocks is at most \((1-(2/3)^m)^j\), which tends to zero.

Before exit, \(S_n\in\{-m+1,\ldots,0\}\); at exit, the value lies between \(-m-1\) and \(2\). Thus \(S_{\tau_m\wedge n}\) is bounded in absolute value by \(m+1\), uniformly in \(n\). Bounded-time optional stopping and dominated convergence give \(\mathbb E[S_{\tau_m}]=0\). If \(p_m\) is the probability of exiting at the upper boundary, the upper exit value is at most \(2\), and the lower exit value is at most \(-m\). Therefore \(0=\mathbb E[S_{\tau_m}]\le2p_m-m(1-p_m)\), so \(p_m\ge m/(m+2)\). Upper exit implies \(T<\infty\); hence \(\mathbb P(T<\infty)\ge p_m\) for every \(m\), and letting \(m\to\infty\) shows that \(T<\infty\) almost surely.

At the crossing, \(S_{T-1}\le0\), so a \(+2\) jump lands at either \(1\) or \(2\), and a \(-1\) jump cannot cross the level. Consequently \(S_T\in\{1,2\}\) and \(O_1\in\{0,1\}\). On the event \(\xi_1=2\), which has probability \(1/3\), \(T=1\) and \(O_1=1\). Thus \(\mathbb E[S_T]=1+\mathbb P(O_1=1)\ge4/3\).

For every \(n\), bounded-time optional stopping gives \(\mathbb E[S_{T\wedge n}]=0\). But \(S_{T\wedge n}\to S_T\) almost surely, and the terminal value is bounded between \(1\) and \(2\), with expectation at least \(4/3\). The expectations cannot pass to the limit. The overshoot itself is bounded; the failure comes from lack of uniform integrability of the stopped family, whose values before crossing can be far below zero.

What Conditions Actually Protect the Argument?

A finite interval offers a useful contrast. For the same centered walk in the preceding example, stop on first exit from the integer interval \(\{-m+1,\ldots,0\}\). The exit time is almost surely finite by the consecutive-downward-jumps argument above. The stopped walk stays in the finite set \(\{-m-1,\ldots,2\}\), including at exit. Consequently the stopped family is uniformly bounded, hence uniformly integrable, and the theorem applies. The fact that the process is kept in a bounded region—not merely the fact that it eventually exits—is what makes the expectation limit safe.

There are several common ways to justify a stopping argument:

Bound the stopped process uniformly. A common deterministic bound on \(|M_{T\wedge n}|\) gives uniform integrability directly.
Prove uniform integrability by another estimate. For example, a uniform bound on the second moments implies uniform integrability, since \(\mathbb E[|Y|\mathbf 1_{\{|Y|>K\}}]\le\mathbb E[Y^2]/K\).
Check an appropriate integrability condition on the stopping time. For a martingale formed from independent, centered increments with uniformly bounded absolute first moment, finite \(\mathbb E[T]\) permits term-by-term expectation of the stopped increment sum, as in the first example.

These are sufficient strategies, not interchangeable assumptions that can be omitted. In particular, bounded overshoots only bound the value at the crossing. They say nothing by themselves about the negative excursions before crossing, nor about how much probability is carried by paths that have not yet stopped at time \(n\).

Key takeaway: Almost-sure finiteness of \(T\) gives \(M_{T\wedge n}\to M_T\) almost surely, but expectation convergence needs additional control. Verify uniform integrability, domination, or another valid integrability argument before concluding \(\mathbb E[M_T]=\mathbb E[M_0]\).

Check Your Understanding

Use the definitions and arguments above to test whether the limit and stopping-time conditions are clear.

Why does a uniform upper bound \(c\) on positive jumps imply \(O_b<c\) when the walk starts below \(b\)?
In the symmetric-walk example, what contradiction follows from assuming \(\mathbb E[T]<\infty\)?
For the centered \(+2,-1\) walk, why is the probability of upper exit from \([-m+1,0]\) at least \(m/(m+2)\)?
Why does a bounded terminal value \(M_T\) not alone imply uniform integrability of \(\{M_{T\wedge n}\}\)?
Give one sufficient condition that permits passage from \(\mathbb E[M_{T\wedge n}]\) to \(\mathbb E[M_T]\), and state what it controls.