Created by Knut M. Synstadfrom the Noun Project

Doob's Upcrossing Inequality

Definition (Upcrossings)

Let f:R+→R+f:\mathbb{R}^{+}\to \mathbb{R}^{+}, let F={S1,…,Sn}⊂R+F = \{ S_{1},\dots,S_{n} \}\subset \mathbb{R}^{+} and let a,b∈Ra,b\in\mathbb{R} where a<ba<b, with S1<⋯<SnS_{1}<\dots<S_{n}. Now let t1=inf⁡{s∈F:f(s)≤a}t2=inf⁡{s∈F:s>t1,f(s)≥b}t3=inf⁡{s∈F:s>t2,f(s)≥a}t4=inf⁡{s∈F:s>t3,f(s)≥b}\begin{align*}t_{1}&=\inf\{ s\in F:f(s)\le a \}\\t_{2}&=\inf\{ s\in F:s>t_{1},f(s)\ge b \}\\t_{3}&=\inf\{ s\in F:s>t_{2},f(s)\ge a \}\\t_{4}&=\inf\{ s\in F:s>t_{3},f(s)\ge b \}\end{align*} Let k∈Nk\in\mathbb{N}, be the largest integer for which f(t2k−1)≤af(t_{2k-1})\le a and f(t2k)≥bf(t_{2k})\ge b. If ∄k\not\exists k, then k=0k=0. We call kk the number of upcrossings from aa to bb over FF and is denoted by M(f,F,[a,b])M(f,F,[a,b])Let now S⊂R+S\subset \mathbb{R}^{+} arbitrary. We define, M(f,S,[a,b])=sup⁡F⊂SF finiteM(f,F,[a,b])M(f,S,[a,b])=\sup_{\mathclap{\substack{F\subset S \\ F\text{ finite}}}} M(f,F,[a,b])i.e. the highest number of upcrossings over all finite F⊂SF\subset S.

Definition (Upcrossings over sample path)

Let X=(Xn)n∈NX=(X_{n})_{n\in\mathbb{N}} be a process on (Ω,F,P)(\Omega,\mathcal{F},P) and let S⊂NS\subset \mathbb{N} arbitrary. Let a,b∈Ra,b\in\mathbb{R}, a<ba<b, then M(X,S,[a,b])(ω)=M(X(ω),S,[a,b]), ∀ω∈ΩM(X,S,[a,b])(\omega)=M(X(\omega),S,[a,b]), \ \forall\omega\in\Omegawhere X(ω)=(Xn)n∈NX(\omega)=(X_{n})_{n\in\mathbb{N}}, i.e. M(X,S,[a,b])(ω)=sup⁡F⊂SF finiteM(X(ω),F,[a,b]), ∀ω∈ΩM(X,S,[a,b])(\omega)=\sup_{\mathclap{\substack{F\subset S \\ F\text{ finite} }}}M(X(\omega),F,[a,b]), \ \forall\omega\in\Omega

Remark

We see M(X,S,[a,b]):Ω→R∪{+∞}M(X,S,[a,b]):\Omega\to \mathbb{R}\cup \{ +\infty \}and see that M(X,S,[a,b])M(X,S,[a,b]) is F\mathcal{F}-measurable i.e. it is a RV on (Ω,F,P)(\Omega,\mathcal{F},P).

Remark

This definition helps to disambiguate the situation of either no upcrossings or infinitely many.

Theorem (Doob’s upcrossing inequality)

Let (Xn)n∈N(X_{n})_{n\in\mathbb{N}} be a (Fn)n∈N(\mathcal{F}_{n})_{n\in\mathbb{N}}-supermartingale on (Ω,F,P)(\Omega,\mathcal{F},P), let a,b∈Ra,b\in\mathbb{R} with a<ba<b. Then, denoting Mab=M(X,N,[a,b])M_{a}^{b}=M(X,\mathbb{N},[a,b]) we have E[Mab]≤1b−asup⁡k∈NE[(Xk−a)−]≤1b−a(∣a∣+sup⁡k∈NE[∣Xk∣])E[M_{a}^{b}]\le \frac{1}{b-a}\sup_{k\in\mathbb{N}}E[(X_{k}-a)^{-}]\le \frac{1}{b-a}\left(|a|+\sup_{k\in\mathbb{N}}E[|X_{k}|]\right)