Nonnegative Supermartingale Convergence

Why Nonnegativity Leads to Convergence

A supermartingale may fluctuate, and its values need not decrease along every sample path. Nevertheless, if its values are nonnegative, it cannot oscillate forever between separated levels on a set of positive probability. The proof has two distinct parts: Fatou’s lemma controls the lower limit, while an upcrossing estimate applied to the negative of the process controls repeated downward crossings. Together they rule out a path that keeps returning between two different levels.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a discrete-time filtration \((\mathcal{F}_n)_{n\ge0}\). A process \((X_n)_{n\ge0}\) with state space \([0,\infty)\) is a nonnegative supermartingale if each \(X_n\) is \(\mathcal{F}_n\)-measurable and integrable, \(X_n\ge0\) almost surely, and \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]\le X_n\) almost surely for every \(n\ge0\). Since there are countably many \(n\), the nonnegativity conditions can be taken to hold simultaneously outside one null set.

The theorem asserts almost-sure convergence, not convergence in mean. Its assumptions do not assert uniform integrability, and the conclusion does not say that \(\mathbb{E}[X_n]\) converges to \(\mathbb{E}[X_\infty]\). The proof below establishes the almost-sure statement and the displayed expectation bound.

Downcrossings from an Upcrossing Bound

For a real-valued sequence \(y_0,\ldots,y_N\) and levels \(\alpha<\beta\), an upcrossing of \([\alpha,\beta]\) is a passage from a value at most \(\alpha\) to a later value at least \(\beta\). Write \(U_N(\alpha,\beta)\) for the maximum number of such passages that can be selected in time order, with each passage beginning after the preceding one ends. A standard submartingale upcrossing inequality, proved in the earlier material on expected upcrossings, states that if \((Y_n)\) is an integrable submartingale, then \[ (\beta-\alpha)\mathbb{E}[U_N(\alpha,\beta)] \le \mathbb{E}[(Y_N-\alpha)^+]+\mathbb{E}[(Y_0-\alpha)^-], \] where \(z^+=\max(z,0)\) and \(z^-=\max(-z,0)\). This finite-time inequality is the only upcrossing result needed here.

For a sequence \(x_0,\ldots,x_N\), define \(D_N(a,b)\) as the maximum number of time-ordered passages from a value at least \(b\) to a later value at most \(a\), where \(a<b\). This is a downcrossing count. Applying the stated inequality to \(Y_n=-X_n\) turns downcrossings of \([a,b]\) by \(X_n\) into upcrossings of \([-b,-a]\) by \(Y_n\).

Proof. The process \(Y_n=-X_n\) is an integrable submartingale: conditioning gives \(\mathbb{E}[Y_{n+1}\mid\mathcal{F}_n]=-\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]\ge-X_n=Y_n\). A downcrossing of \([a,b]\) by \(X_n\) is exactly an upcrossing of \([-b,-a]\) by \(Y_n\), so \(D_N(a,b)=U_N(-b,-a)\). In the upcrossing inequality take \(\alpha=-b\) and \(\beta=-a\), whose difference is \(b-a>0\). Its two expectation terms are \(\mathbb{E}[(-X_N+b)^+]=\mathbb{E}[(b-X_N)^+]\) and \(\mathbb{E}[(-X_0+b)^-]=\mathbb{E}[(X_0-b)^+]\). This proves the first inequality. Since \(X_N\ge0\), \((b-X_N)^+\le b\); since \(X_0\ge0\), \((X_0-b)^+\le X_0\). Taking expectations gives the second inequality. \(\square\)

The bound is finite for each fixed pair \(a,b\), uniformly over the time horizon \(N\). Let \(D_\infty(a,b)=\lim_{N\to\infty}D_N(a,b)\); this limit exists because downcrossing counts cannot decrease as the horizon grows. By monotone convergence, \(\mathbb{E}[D_\infty(a,b)]\le (b+\mathbb{E}[X_0])/(b-a)<\infty\). A nonnegative random variable with finite expectation is finite almost surely, so there are only finitely many such downcrossings almost surely.

Proof of Almost-Sure Convergence

Proof. First, iterated conditional expectation gives \(\mathbb{E}[X_{n+1}]\le\mathbb{E}[X_n]\), and induction gives \(\mathbb{E}[X_n]\le\mathbb{E}[X_0]<\infty\) for every \(n\). Set \(L=\liminf_{n\to\infty}X_n\), which is a measurable, nonnegative extended random variable. Fatou’s lemma yields \[ \mathbb{E}[L]\le\liminf_{n\to\infty}\mathbb{E}[X_n]\le\mathbb{E}[X_0]<\infty. \] Consequently \(L<\infty\) almost surely; otherwise \(L=\infty\) on an event of positive probability and its expectation would be infinite.

It remains to show that the upper and lower limits agree almost surely. There are countably many rational pairs \(0\le a<b\). For each such pair, the downcrossing bound and monotone convergence show that \(D_\infty(a,b)<\infty\) almost surely. Thus, outside a single null set, all these rational-pair downcrossing counts are finite and \(\liminf X_n<\infty\).

Suppose on a path outside that null set that \(\limsup X_n>\liminf X_n\). Since the lower limit is finite and the values are nonnegative, there are rational numbers \(0\le a<b\) with \(\liminf X_n<a<b<\limsup X_n\). There are arbitrarily late indices with \(X_n\le a\) and arbitrarily late indices with \(X_n\ge b\). Starting at a sufficiently late index with \(X_n\ge b\), one can choose a later index with \(X_n\le a\), then a still later index with \(X_n\ge b\), and continue in this way. This constructs infinitely many downcrossings of \([a,b]\), contradicting \(D_\infty(a,b)<\infty\). Therefore \(\limsup X_n=\liminf X_n<\infty\) almost surely, which proves convergence to a finite nonnegative limit \(X_\infty\). Finally, Fatou’s lemma applied once more to the convergent nonnegative sequence gives \(\mathbb{E}[X_\infty]\le\liminf_n\mathbb{E}[X_n]\le\mathbb{E}[X_0]\). \(\square\)

Worked Examples

A Common Pitfall

A bounded expectation at each time is not, by itself, a pathwise bound on the whole sequence. For a nonnegative supermartingale, Markov’s inequality gives \(\mathbb{P}(X_n>K)\le\mathbb{E}[X_0]/K\) at each fixed \(n\). A tempting but incorrect next line is \(\mathbb{P}(\sup_n X_n>K)\le\mathbb{E}[X_0]/K\), as if the bound for one time applied to the union over all times. The union bound only gives \(\mathbb{P}(\sup_n X_n>K)\le\sum_{n\ge0}\mathbb{P}(X_n>K)\), and substituting the fixed-time estimate produces the generally useless sum \(\sum_{n\ge0}\mathbb{E}[X_0]/K=\infty\), not the claimed finite bound. The convergence proof does not make that step: it uses a uniform-in-\(N\) bound on downcrossings for each fixed pair of levels, then rules out oscillation using countably many rational pairs. A fixed-time tail estimate and an almost-sure statement about the entire path are different claims.

The theorem is useful when a process has a one-sided bound and a conditional drift inequality, even when no explicit formula for its limiting value is available. Its conclusion is deliberately limited: almost-sure convergence to a finite value and an upper bound on the expectation of that value. Stronger conclusions about convergence in mean require additional hypotheses and are not part of this result.