Doob upcrossing inequality

If $(M_n)$ is a martingale and $U_N[a,b]$ counts its completed upcrossings of $[a,b]$ by time $N$, thenEquivalent conventions may add an initial endpoint term.

For a nonnegative supermartingale and $0<a<b$, let $U$ count completed upcrossings of $[a,b]$, allowing the first entry at time zero. The displayed bound holds for every integer $k\ge 1$. Construct the multiplicative upcrossing supermartingale, stop at the $k$th completed crossing, and use its initial expected value and nonnegativity. The bound is exponential in the number of crossings, and complements the first-moment Doob upcrossing inequality.

Start with cash one, switch to $X/a$ when a nonnegative supermartingale first reaches at most $a$, and switch to cash $q=b/a$ when it next reaches at least $b$. Repeat with coefficients multiplied by $q$ after every completed upcrossing. At each switch the new value is at most the old one, so pasting supermartingales with downward jumps gives a supermartingale when stopped after any fixed number of switches. Its initial value is $\min (X_0/a,1)$, and its value at the $k$th completed crossing is exactly $q^k$. Applying its expected value bound proves the Dubins upcrossing inequality.

An upcrossing of an interval $[a,b]$ consists of an observation at or below $a$ followed by a later observation at or above $b$. Successive completed upcrossings use disjoint buy-sell pairs.

The upcrossing count $U_N[a,b]$ counts completed upcrossings by time $N$, allowing the first purchase at time zero. For a martingale, the Doob upcrossing inequality bounds its expected value by $\mathbb{E}(M_N-a{)}^{-}/(b-a)$.

A discrete-time martingale with ${\sup }_n\mathbb{E}|M_n|<\infty$ converges almost surely to an integrable random variable. If the martingale is uniformly integrable, convergence also holds in $L^1$.

This is one of Doob's martingale convergence theorems; uniform integrability upgrades almost-sure convergence to convergence in mean.

Let independent increments ${\xi }_k$ equal $4^k$ or $-4^k$ with probabilities $2^{-k-1}$ each, and zero otherwise. Every partial sum $M_n={\sum }_{k\le n}{\xi }_k$ is integrable and is a martingale. The Borel-Cantelli lemma makes only finitely many increments nonzero almost surely, so $M_n$ has a finite almost-sure limit $Y$. Yet $\mathbb{E}|Y|=\infty$: the disjoint events that only the $k$th increment is nonzero have probabilities at least $c{2}^{-k}$ for $c={\prod }_j(1-2^{-j})>0$, and contribute at least $c{2}^k$ each. This does not contradict the martingale convergence theorem, whose integrability conclusion requires a uniform first-moment bound.

// Target: markov-process.bigb

An $L^2$-bounded real martingale has a square-integrable terminal value, converges to it almost surely and in $L^2$, and satisfies $M_t=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_t]$. The $L^2$ Cauchy property follows from orthogonality of increments and monotonicity of $\mathbb{E}{M}_t^2$. This terminal representation permits optional sampling at finite unbounded stopping times and uniform-integrability control of stopped squares by conditional Jensen.

For independent fair Bernoulli variables, this nonnegative martingale starts at one, doubles on every success, and becomes zero permanently on the first failure. Its expectation is always one, but it tends to zero almost surely because the probability of success forever is zero. Thus it satisfies the martingale convergence theorem while failing convergence in L1. This illustrates how rare large values obstruct uniform integrability.

A submartingale with ${\sup }_n\mathbb{E}{Y}_n^{+}<\infty$ converges almost surely to a finite integrable random variable. The positive-part bound also bounds negative parts because $\mathbb{E}{Y}_n\ge \mathbb{E}{Y}_0$. The result specializes to an $L^1$-bounded martingale, and hence to every nonnegative martingale. It does not by itself give convergence in L1; uniform integrability supplies that stronger conclusion.

A martingale satisfying ${\sup }_n\mathbb{E}|M_n{|}^p<\infty$, for $1<p<\infty$, has almost sure convergence and convergence in Lp to a limit $M_{\infty }\in L^p$. Also $M_n=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_n]$. The Doob Lp maximal inequality makes ${\sup }_n|M_n|$ integrable to the power $p$; the martingale convergence theorem gives the almost-sure limit, and the dominated convergence theorem gives convergence in the Lp norm. Boundedness in $L^1$ alone does not imply convergence in L1.

A uniformly integrable martingale $M_n$ has almost sure convergence and convergence in L1 to an integrable random variable $M_{\infty }$, and $M_n=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_n]$.

Stopping a uniformly integrable discrete-time martingale at any stopping time preserves uniform integrability, including when the stopping time can be infinite. For $C={\sup }_n\mathbb{E}|X_n|$, the optional stopping theorem and the Markov inequality giveChoose $R$ first, then $K$, to make this uniformly small.

For a decreasing sequence of sigma-algebras ${\mathcal{F}}_n$ and an integrable random variable $X$,almost surely and in $L^1$.

A nonnegative supermartingale, or more generally a supermartingale whose negative parts have uniformly bounded expectations, converges almost surely to a finite integrable random variable.

Suppose $X_n\ge 0$ is an integrable adapted process, $Y_n\ge 0$ is finite and adapted, and $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]\le (1+Y_n)X_n$. The displayed correction is a nonnegative supermartingale: its next denominator is measurable at time $n$, and its reciprocal is at most one. If ${\sum }_n{Y}_n<\infty$ almost surely, the denominators converge to a finite positive limit since $\log (1+y)\le y$. The almost sure supermartingale convergence theorem then gives finite almost sure convergence of $X_n$. No integrability of the infinite product or of ${\sum }_n{Y}_n$ is needed.

Suppose $X_n\ge 0$ is integrable and adapted, and $Y_n\ge 0$ is finite and adapted. Use the stopped predictable budget for adapted increments with an integer budget $a$. The process $X_{n\wedge {\tau }_a}+a-U_{n\wedge {\tau }_a}$ is an integrable nonnegative supermartingale, because its budget decrement cancels the localized drift. It has a finite almost-sure limit. On the event that the total drift is smaller than $a$, the stopping time is infinite, so $X_n$ itself converges. Taking the countable union over integer budgets proves finite almost sure convergence. No expectation of the total drift is needed.

When the drift bound is a deterministic summable sequence ${\delta }_n\ge 0$, the displayed correction is a nonnegative supermartingale. Its added tail tends to zero, so the almost sure supermartingale convergence theorem directly implies finite almost sure convergence of $X_n$. This simpler tail correction requires deterministic bounds; an arbitrary future random drift tail is not generally measurable at the current time.

If ${\mathcal{F}}_{\infty }=\sigma ({\bigcup }_n{\mathcal{F}}_n)$ and $Z$ is bounded, thenalmost surely and in $L^1$. Testing the almost-sure martingale limit on the algebra ${\bigcup }_n{\mathcal{F}}_n$ identifies it with the terminal conditional expectation.

If bounded random variables $X_n$ converge almost surely to $X$, thenalmost surely and in $L^1$. For $Z_n={\sup }_{m\ge n}|X_m-X|$, the variables $\mathbb{E}[Z_n\mid {\mathcal{F}}_n]$ form a nonnegative supermartingale with expectations tending to zero.

A right-continuous continuous-time martingale with ${\sup }_{t\ge 0}\mathbb{E}|M_t|<\infty$ has an almost-sure finite limit as $t\to \infty$.