Upcrossing Inequality
1 Upcrossings
Let \((y_n)\) be a sequence of real numbers and fix an interval \([a,b]\) with \(a<b\). Define
\[ T_1 = \min\{ n : y_n \le a \}, \qquad T_2 = \min\{ n > T_1 : y_n \ge b \}. \]
The interval \([T_1, T_2]\) is called an upcrossing of \([a,b]\). For \(k \ge 2\) define
\[ T_{2k-1} = \min\{ n > T_{2k-2} : y_n \le a \}, \qquad T_{2k} = \min\{ n > T_{2k-1} : y_n \ge b \}. \]
The number of upcrossings of \([a,b]\) by the finite sequence \((y_0,\dots,y_n)\) is denoted \(U_n(a,b;y)\), and the total number of upcrossings of \([a,b]\) by the infinite sequence is
\[ U(a,b;y) := \lim_{n\to\infty} U_n(a,b;y). \]
Downcrossings are defined similarly by reversing the inequalities and swapping \(a\) and \(b\).
If a sequence of real numbers \((y_n)\) diverges, then there exist rational numbers \(a<b\) such that \(U(a,b;y)=\infty\).
\begin{proof} If \((y_n)\) diverges, then \(\liminf y_n < \limsup y_n\), so there are rational numbers \(a<b\) with \(\liminf y_n < a < b < \limsup y_n\). Then \(y_n \le a\) for infinitely many \(n\) and \(y_n \ge b\) for infinitely many \(n\), so \((y_n)\) crosses \([a,b]\) upwards infinitely often, that is \(U(a,b;y)=\infty\). \end{proof}
This reduces convergence of a sequence to finiteness of \(U(a,b;y)\) for the countably many rational pairs \(a<b\), which is how the upcrossing inequality is used to prove the Martingale Convergence Theorems.
2 Upcrossing Inequality
Let \((X_n, \mathcal{F}_n)\) be a submartingale, \(a<b\), and let \(U_n(a,b;X)\) be the number of upcrossings of \([a,b]\) by \(X=(X_n)\) up to time \(n\). Then
\[ \mathbb{E}[U_n(a,b;X)] \le \frac{1}{b-a}\,\mathbb{E}[(X_n-a)^+]. \]
\begin{proof} Put \(Y_n = (X_n - a)^+\). This is a nonnegative submartingale (a convex nondecreasing function of a submartingale), and upcrossings of \([a,b]\) by \(X\) are upcrossings of \([0,b-a]\) by \(Y\), so \(U_n(a,b;X) = U_n(0,b-a;Y)\).
Define the predictable process \(C_1 = \mathbb{1}_{\{Y_0 = 0\}}\) and, for \(n \ge 2\),
\[ C_n = \mathbb{1}_{\{C_{n-1}=1\}}\mathbb{1}_{\{Y_{n-1} < b-a\}} + \mathbb{1}_{\{C_{n-1}=0\}}\mathbb{1}_{\{Y_{n-1} = 0\}}. \]
That is, we start betting when \(Y\) hits \(0\) and stop once it exceeds \(b-a\). Each completed upcrossing of \([0,b-a]\) contributes at least \(b-a\) to the transform \((C\bullet Y)_n = \sum_{k=1}^n C_k(Y_k - Y_{k-1})\), and an unfinished final stretch contributes at least \(0\) since \(Y \ge 0\). Hence
\[ (b-a)\,U_n(0,b-a;Y) \le (C\bullet Y)_n. \]
Since \(1-C\) is predictable and nonnegative, \(((1-C)\bullet Y)\) is a submartingale null at \(0\) (see Martingale Theory), so \(\mathbb{E}[((1-C)\bullet Y)_n] \ge 0\). Therefore
\[ \mathbb{E}[(C\bullet Y)_n] = \mathbb{E}[Y_n - Y_0] - \mathbb{E}[((1-C)\bullet Y)_n] \le \mathbb{E}[Y_n - Y_0] \le \mathbb{E}[Y_n], \]
and combining the two displays gives \((b-a)\,\mathbb{E}[U_n(a,b;X)] \le \mathbb{E}[(X_n - a)^+]\). \end{proof}