The Pathwise Upcrossing Inequality

From Crossings to a Pathwise Bound

An upcrossing records a particular kind of oscillation: a sequence reaches a level at or below $a$, and later reaches a level at or above $b$, where $a<b$. The pathwise upcrossing inequality bounds how many such completed trips can occur in a finite sequence. Its proof turns the sequence into a simple trading strategy: enter when the sequence is at or below the lower level and leave when it reaches the upper level.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $X_0,\ldots,X_n$ be real-valued random variables on it, for a fixed integer $n\ge 0$. No martingale, Markov, or integrability assumption is needed. The result is deterministic: it holds for each sample path on which these random variables are real. In particular, it does not require conditioning or a filtration.

Definition: Fix real numbers $a<b$. A completed upcrossing of $[a,b]$ by $x_0,\ldots,x_n$ is a pair of indices $s<t$ such that $x_s\le a$ and $x_t\ge b$. To count nonoverlapping completed upcrossings, choose the first available index $s_1$ with $x_{s_1}\le a$, then the first later index $t_1$ with $x_{t_1}\ge b$. Repeat the search after $t_1$: choose the first $s_2>t_1$ with $x_{s_2}\le a$, then the first $t_2>s_2$ with $x_{t_2}\ge b$, and continue. The number of pairs obtained is $U_n(a,b)$. If no such pair is available, the count is zero.

The endpoint inequalities in this definition are weak: equality with $a$ qualifies as a lower-level visit, and equality with $b$ qualifies as an upper-level visit. The strict condition $s<t$ means that a single observation cannot make both visits when $a<b$. The greedy procedure gives the usual count of completed upcrossings: each new crossing starts only after the previous crossing has finished.

For a real number $z$, write $z^+=\max(z,0)$ and $z^-=\max(-z,0)$. Thus the negative part of an increment $X_k-X_{k-1}$ is $(X_k-X_{k-1})^-=(X_{k-1}-X_k)^+$. The bound will charge the sequence for each downward move, as well as using its terminal position.

Theorem (Pathwise upcrossing inequality): For every finite real sequence $x_0,\ldots,x_n$ and every $a<b$, $$ (b-a)U_n(a,b)\le (x_n-a)^+ + \sum_{k=1}^{n}(x_{k-1}-x_k)^+. $$ For random variables $X_0,\ldots,X_n$, the same inequality holds pointwise with $x_k=X_k(\omega)$. The sum is zero when $n=0$.

Proof by a Trading Strategy

Shift the sequence so that the lower threshold becomes zero. Define $y_k=(x_k-a)^+$ and $c=b-a>0$. Then $y_k\ge0$; $y_k=0$ exactly when $x_k\le a$; and $y_k\ge c$ whenever $x_k\ge b$. Consequently, each completed upcrossing of $[a,b]$ gives a trip from $y=0$ to $y\ge c$.

Consider a strategy that holds one unit during each such trip: it starts holding at an index $s$ with $y_s=0$, and stops holding at the first later index $t$ with $y_t\ge c$. After a sale, it waits until the sequence returns to zero before starting another trip. For $k=1,\ldots,n$, let $H_{k-1}=1$ if the strategy is holding over the increment from $y_{k-1}$ to $y_k$, and $H_{k-1}=0$ otherwise. This choice uses only observations through index $k-1$. Define the cumulative gain $G=\sum_{k=1}^n H_{k-1}(y_k-y_{k-1})$.

Proof. Fix one sample path. We prove the inequality for its real values $x_0,\ldots,x_n$. Let $U=U_n(a,b)$. First suppose $U>0$, and consider the holding intervals selected by the strategy. On a completed interval from $s$ to $t$, the strategy’s gain is $y_t-y_s=y_t\ge c$, because $y_s=0$. If the sequence ends with an unfinished holding interval starting at $s$, its gain is $y_n-y_s=y_n\ge0$. Summing these interval gains gives $G\ge cU$.

Now let $r$ be the first index with $y_r=0$. Since $U>0$, such an index exists. The strategy holds only over increments with indices $k>r$, and $H_{k-1}$ is either zero or one. For every increment, $H_{k-1}(y_k-y_{k-1})\le (y_k-y_{k-1})^+$. Therefore $$ G\le \sum_{k=r+1}^{n}(y_k-y_{k-1})^+. $$ For any real increment $d$, $d=d^+-d^-$. Summing this identity from $r+1$ to $n$, and using $y_r=0$, gives $$ \sum_{k=r+1}^{n}(y_k-y_{k-1})^+ =y_n+\sum_{k=r+1}^{n}(y_{k-1}-y_k)^+. $$ The terms in the latter sum are nonnegative, so extending that sum to all $k=1,\ldots,n$ can only increase it. Hence $cU\le G\le y_n+\sum_{k=1}^n(y_{k-1}-y_k)^+$.

It remains to relate the negative increments of $y$ to those of $x$. If $x_{k-1}\le x_k$, then $y_{k-1}\le y_k$, so $(y_{k-1}-y_k)^+=0$. If $x_{k-1}>x_k$, there are three cases. If both values are at most $a$, the difference in $y$ is zero. If both are greater than $a$, the difference in $y$ is $x_{k-1}-x_k$. If $x_{k-1}>a\ge x_k$, the difference in $y$ is $x_{k-1}-a\le x_{k-1}-x_k$. In every case, $$ (y_{k-1}-y_k)^+\le (x_{k-1}-x_k)^+. $$ Also $y_n=(x_n-a)^+$. Substitution proves the claimed inequality when $U>0$. If $U=0$, its left side is zero and its right side is a sum of nonnegative terms, so the inequality holds in that case as well. This proves the deterministic statement for every finite real sequence. Applying it to the values $X_k(\omega)$ proves the pointwise random-variable statement. $\square$

The two terms on the right have distinct roles. The terminal positive part records how far the final observation lies above $a$. The sum of negative increments accounts for downward moves that can separate one completed upcrossing from the next. The argument does not say that a martingale or submartingale is needed: it is a pathwise statement about a finite sequence, before any expectation is taken.

Worked Examples

Worked Example: Two Upcrossings and a Nonsharp Bound

Take $a=1$, $b=3$, and the sequence $x=(0,2,3,1,0,4,2)$. Here $b-a=3-1=2$. The first lower-level index is $0$, where $x_0=0\le1$; the first subsequent upper-level index is $2$, where $x_2=3\ge3$. The next lower-level index is $3$, where $x_3=1\le1$; the next upper-level index is $5$, where $x_5=4\ge3$. There is no later lower-level index, so $U_n(1,3)=2$, and the left side is $2\cdot2=4$.

The terminal term is $(x_6-a)^+=(2-1)^+=1$. The negative increments, in order, are $$ (0-2)^+=0,\quad (2-3)^+=0,\quad (3-1)^+=2,\quad (1-0)^+=1,\quad (0-4)^+=0,\quad (4-2)^+=2. $$ Their sum is $0+0+2+1+0+2=5$. The right side is $1+5=6$, so the inequality reads $4\le6$.

Check: The two lower-to-upper pairs are $(0,2)$ and $(3,5)$, both satisfying the required weak endpoint inequalities. The computed negative increments total $5$, and the terminal term is $1$; thus the right side is $6$, as stated.

Worked Example: Equality in the Inequality

Take $a=0$, $b=2$, and $x=(0,2,0,2)$. The pair of indices $(0,1)$ is one completed upcrossing, and $(2,3)$ is a second, so $U_n(0,2)=2$. Since $b-a=2$, the left side is $2\cdot2=4$.

The terminal term is $(2-0)^+=2$. The three negative increments are $$ (0-2)^+=0,\qquad (2-0)^+=2,\qquad (0-2)^+=0, $$ which sum to $2$. The right side is $2+2=4$, exactly the left side.

Check: Both crossings begin at a value equal to $a=0$ and end at a value equal to $b=2$, so both count under the weak endpoint convention. Substitution gives $4\le4$.

Worked Example: The Sequence Must Visit the Lower Level First

Take $a=1$, $b=4$, and $x=(2,4,1,5,0)$. Although $x_1=4$, that upper-level visit is not preceded by an observation at or below $1$: $x_0=2>1$. The value $x_2=1$ is a lower-level visit, and $x_3=5\ge4$ is the first subsequent upper-level visit. Thus there is exactly one completed upcrossing, and the left side is $(4-1)\cdot1=3$.

The terminal term is $(x_4-a)^+=(0-1)^+=0$. The negative increments are $$ (2-4)^+=0,\qquad (4-1)^+=3,\qquad (1-5)^+=0,\qquad (5-0)^+=5. $$ They sum to $0+3+0+5=8$. The right side is $0+8=8$, and the inequality reads $3\le8$.

Check: The only qualifying ordered pair is $(2,3)$, since $x_2=1\le1$ and $x_3=5\ge4$; after index $3$, no upper-level visit occurs. The count is therefore one, not two.

Why the Negative-Part Term Matters

A common mistake is to bound the number of upcrossings using only the terminal positive part, as if $$ (b-a)U_n(a,b)\le (x_n-a)^+. $$ The equality example above disproves this claim: for $a=0$, $b=2$, and $x=(0,2,0,2)$, the left side is $4$, but the terminal positive part is only $2$. The omitted term is the downward move $2\to0$, whose negative part is $(2-0)^+=2$. Including it gives the correct bound $4\le2+2$.

The strategy proof also clarifies why the terminal term is a positive part rather than the terminal value itself. After shifting by $a$, the transformed sequence $y_k=(x_k-a)^+$ is nonnegative. If a trade remains open at the final index, its gain is $y_n\ge0$; if no trade is open, the terminal term still provides a nonnegative bound. The negative increments then account for losses during the intervals in which the strategy can hold the sequence.

For a random sequence, this theorem remains a pointwise inequality. Its value is that it provides a deterministic bound that can later be combined with assumptions about expectations or martingales. Those probabilistic steps require their own hypotheses; the pathwise argument itself uses no such assumptions.

Check Your Understanding

Use the endpoint convention $x_s\le a$ and $x_t\ge b$, with $s<t$, in each question.

For $a=0$, $b=3$, and $x=(0,1,3,2,0,4)$, find the upcrossing count and both sides of the pathwise inequality.
Explain why an observation above $b$ at the start of a sequence does not by itself complete an upcrossing.
For $x=(1,3,1)$, compute the right side of the inequality when $a=1$ and $b=3$. Does the sequence complete an upcrossing?
In the proof, why can the negative-increment sum from the first index with $y_r=0$ be extended to include all indices $1,\ldots,n$?
Give a finite sequence showing that the terminal positive-part term alone cannot always bound $(b-a)U_n(a,b)$.

The Pathwise Upcrossing Inequality

What You'll Learn