From Upcrossings to Convergence
An oscillating real sequence must repeatedly move from below some level to above a higher one. Upcrossings make this observation precise: if a sequence fails to settle toward any extended-real limit, at least one interval is crossed upward infinitely often. For stochastic processes, an expectation bound on these crossings can therefore yield almost-sure convergence.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be real-valued random variables. For real numbers \(a<b\), count an upcrossing by starting at an index where \(X_n\le a\), then looking for a later index where \(X_m\ge b\), and repeating this procedure after each completed crossing. Write \(U_N(a,b)\) for the number completed using indices \(0,\ldots,N\), and \(U_\infty(a,b)=\lim_{N\to\infty}U_N(a,b)\). The inequalities at both thresholds are inclusive.
Proof. First suppose \(x_n\) converges in the extended real line. For any fixed \(a<b\), set \(c=(a+b)/2\). If the limit is at most \(a\), eventually \(x_n<c\), so no later index can complete an upcrossing. If the limit is at least \(b\), eventually \(x_n>c\), so no later index can start one. These statements also apply to limits \(-\infty\) and \(+\infty\), respectively. In the remaining case the finite limit lies strictly between \(a\) and \(b\); convergence implies that eventually \(a<x_n<b\), so there can be no new completed upcrossings. Thus the count is finite.
Conversely, suppose \((x_n)\) does not converge in the extended real line. Its lower and upper limits then satisfy \(\liminf_n x_n<\limsup_n x_n\). Choose rational numbers \(a<b\) strictly between these two limits; this is possible also when one or both limits are infinite. There are infinitely many indices with \(x_n\le a\) and infinitely many with \(x_n\ge b\). Moreover, after any fixed index there are further indices of both kinds. Starting at an index with \(x_n\le a\), one can therefore find a later index with \(x_m\ge b\), and then a still later index with value at most \(a\). Repeating this constructs infinitely many completed upcrossings of \([a,b]\), contradicting the assumed finiteness for every rational interval. Hence the sequence converges in the extended real line. \(\square\)
In the random setting, there are only countably many rational intervals. If \(U_\infty(a,b)<\infty\) almost surely for each rational pair \(a<b\), then the intersection of these probability-one events still has probability one. On that intersection, the pathwise criterion says that \(X_n\) has an extended-real limit. The remaining task is to show that, under suitable integrability assumptions, the limit is finite.
A Corrected Upcrossing Bound
Let \((\mathcal{F}_n)_{n\ge0}\) be a filtration, and suppose \((X_n)\) is an integrable submartingale: each \(X_n\) is \(\mathcal{F}_n\)-measurable and integrable, and \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]\ge X_n\) almost surely. To count upcrossings, use a strategy that holds one unit of \(X\) after the first time its value is at most \(a\), and stops holding after its value reaches at least \(b\). Its holdings over the increment from \(k-1\) to \(k\) are denoted \(H_k\). They are predictable: \(H_k\) is \(\mathcal{F}_{k-1}\)-measurable.
Proof. For \(N\ge1\), let \(G_N=\sum_{k=1}^N H_k(X_k-X_{k-1})\) be the holding strategy’s gain. Every completed upcrossing buys at a value at most \(a\) and sells at a value at least \(b\), contributing at least \(b-a\). If there is an unfinished final holding, it was bought at a value at most \(a\); its gain at time \(N\) is at least \(X_N-a\), and therefore at least \(-(a-X_N)^+\). Consequently, path by path, $$ G_N\ge (b-a)U_N(a,b)-(a-X_N)^+. $$ For each \(k\), the submartingale property and predictability give \(\mathbb{E}[H_k(X_k-X_{k-1})]\ge0\). The complementary holdings \(1-H_k\) are also predictable and nonnegative, so \(\mathbb{E}[(1-H_k)(X_k-X_{k-1})]\ge0\). Summing the latter inequalities and using \(H_k+(1-H_k)=1\) gives $$ 0\le\mathbb{E}[G_N]\le\mathbb{E}[X_N-X_0]. $$ Taking expectations in the pathwise gain inequality now yields $$ (b-a)\mathbb{E}[U_N(a,b)] \le \mathbb{E}[X_N-X_0]+\mathbb{E}[(a-X_N)^+]. $$ For every real \(x\), \(x+(a-x)^+=(x-a)^++a\). Applying this identity to \(X_N\) proves the stated bound. When \(N=0\), the left side is zero, and the right side is \(\mathbb{E}[(a-X_0)^+]\ge0\), so the bound holds there as well. \(\square\)
The complementary strategy matters. The submartingale property says that both nonnegative predictable strategies have nonnegative expected gains. Since their gains add to \(X_N-X_0\), the expected gain of the upcrossing strategy is bounded above by \(\mathbb{E}[X_N-X_0]\). A lower bound on its expected gain alone would not provide an upper bound on the expected number of upcrossings.
Worked Example: Checking the Bound at an Inclusive Crossing
Take a probability space with one outcome, the trivial filtration, and \(X_0=0,\ X_1=1\). This is an integrable submartingale because \(X_1\ge X_0\). For \(a=0,\ b=1,\ N=1\), the single move completes one inclusive upcrossing: \(X_0\le0\) and \(X_1\ge1\), so \(U_1(0,1)=1\). The holding strategy buys at \(0\) and sells at \(1\), giving \(G_1=1\); the complementary strategy makes no trade and has gain \(0\). Thus the expected gain of the holding strategy is bounded above by the total gain, \(1\), and the theorem gives $$ (1-0)\mathbb{E}[U_1(0,1)] =1 =\mathbb{E}[(X_1-0)^+]+0-\mathbb{E}[X_0] =1+0-0. $$ The bound holds with equality. In particular, replacing its right side by \(\mathbb{E}[(a-X_N)^+]\) would give \(0\) here, which cannot bound the left side \(1\).
Almost-Sure Convergence of Submartingales
Proof. Write \(C=\sup_{n\ge0}\mathbb{E}[X_n^+]\), which is finite by hypothesis. For fixed real \(a<b\), the upcrossing bound and \((x-a)^+\le x^++|a|\) imply, for all \(N\), $$ (b-a)\mathbb{E}[U_N(a,b)] \le C+|a|-\mathbb{E}[X_0]. $$ The right side is finite and independent of \(N\). Since \(U_N(a,b)\) increases to \(U_\infty(a,b)\), monotone convergence gives \(\mathbb{E}[U_\infty(a,b)]\le (C+|a|-\mathbb{E}[X_0])/(b-a)<\infty\). A nonnegative random variable with finite expectation is finite almost surely, so each rational interval has finitely many upcrossings almost surely. Countability of the rational pairs and the pathwise criterion show that \(X_n\) converges almost surely in the extended real line.
It remains to rule out infinite limits. The submartingale property implies \(\mathbb{E}[X_n]\ge\mathbb{E}[X_0]\) for every \(n\), by taking expectations and iterating. Since \(X_n=X_n^+-X_n^-\), $$ \mathbb{E}[X_n^-]=\mathbb{E}[X_n^+]-\mathbb{E}[X_n]\le C-\mathbb{E}[X_0]<\infty. $$ Fatou’s lemma applied to \(X_n^+\) gives \(\mathbb{E}[\liminf_n X_n^+]\le C\); hence the limit cannot be \(+\infty\) on an event of positive probability. Applying Fatou’s lemma to \(X_n^-\), whose expectations have the finite uniform bound just shown, rules out a limit of \(-\infty\) on an event of positive probability. The extended-real limit is therefore finite almost surely. \(\square\)
Worked Example: A Bounded Martingale with an Explicit Limit
Let \((\varepsilon_k)_{k\ge1}\) be independent random variables with \(\mathbb{P}(\varepsilon_k=1)=\mathbb{P}(\varepsilon_k=-1)=\tfrac12\), and let \(\mathcal{F}_n=\sigma(\varepsilon_1,\ldots,\varepsilon_n)\), with \(\mathcal{F}_0\) trivial. Define $$ X_n=1+\sum_{k=1}^n 2^{-k}\varepsilon_k. $$ For \(n\ge1\), the increment is \(X_n-X_{n-1}=2^{-n}\varepsilon_n\), whose conditional expectation given \(\mathcal{F}_{n-1}\) is \(2^{-n}\mathbb{E}[\varepsilon_n]=0\). Thus \((X_n)\) is a martingale. Also, for every \(n\), $$ |X_n-1|\le\sum_{k=1}^n2^{-k}=1-2^{-n}, $$ so \(0<X_n<2\) and \(\mathbb{E}[X_n^+]=\mathbb{E}[X_n]=1\). The convergence theorem applies. More explicitly, the tail after time \(n\) satisfies $$ |X_m-X_n|\le\sum_{k=n+1}^m2^{-k}\le2^{-n}\qquad(m>n), $$ so every sample path converges to \(1+\sum_{k=1}^\infty2^{-k}\varepsilon_k\). The tail bound tends to zero, verifying convergence directly as well as through the theorem.
Worked Example: Why the Positive-Part Bound Is Needed
On a one-outcome probability space with trivial filtration, set \(X_n=n\). This is an integrable submartingale since \(X_{n+1}=n+1\ge n=X_n\). For any fixed \(a<b\), once \(n\ge b\), the sequence remains at least \(b\), so it cannot start another upcrossing; hence it has finitely many upcrossings of every such interval. Nevertheless, \(X_n\to+\infty\), not to a finite real number. The positive-part expectations are \(\mathbb{E}[X_n^+]=n\), so their supremum is infinite. This example shows why the pathwise criterion alone gives only an extended-real limit, and why the expectation hypothesis is used to exclude infinite limits.
Common Pitfall and Practical Use
A common error is to infer an upper bound on \(\mathbb{E}[U_N(a,b)]\) from a lower bound on the expected gain \(G_N\). A lower bound on one quantity does not, by itself, give the needed upper bound on another. The correct argument combines the pathwise inequality for the gain with the upper bound \(\mathbb{E}[G_N]\le\mathbb{E}[X_N-X_0]\), obtained by considering the complementary predictable strategy. The resulting term is \(\mathbb{E}[(X_N-a)^+]+a-\mathbb{E}[X_0]\), not just the expected shortfall below \(a\).
In applications, the proof has two distinct jobs. The upcrossing bound controls oscillation: for each fixed rational interval, the expected number of completed crossings is uniformly bounded in the time horizon, so infinitely many crossings have probability zero. The pathwise criterion then gives an extended-real limit. The positive-part and submartingale expectation bounds control the two possible infinite limits, leaving a finite almost-sure limit. This conclusion is almost-sure convergence; it does not assert convergence in expectation or in probability.
Check Your Understanding
Use the inclusive convention \(X_n\le a\) to start and \(X_m\ge b\) to complete an upcrossing.
- Explain why a real sequence with distinct lower and upper limits has infinitely many upcrossings of some rational interval.
- For the deterministic submartingale \(X_0=0,\ X_1=1\), compute both sides of the corrected upcrossing bound for \(a=0,\ b=1,\ N=1\).
- Why does the complementary predictable strategy give an upper bound on the expected gain of the holding strategy?
- In the convergence theorem, which expectation bounds rule out limits \(+\infty\) and \(-\infty\), respectively?
- Give a submartingale with finite upcrossings of every fixed interval that does not converge to a finite real value, and identify the failed hypothesis.