Convergence of Positive Supermartingales

I really enjoyed reading Chapter two of Discrete Parameter Martingales and I thought why not making a blog post.

The book is quite advanced, but I’ll try my best state everything clearly and simply given my temporal boredom threshold. Haha :)!

Let me fix the probability space first. Our probability space (as usual) is $(\Omega, \mathscr{F}, \mathbb{P})$. HOWEVER, in what follows it is more convenient to define a subset of the above probability space as $(\Omega’, \mathscr{B}, \mathbb{P})$ (because we’re going to work with filterations and naturally they are sub-$\sigma$-algebras that are growing, so we’re always in the subset case). A mapping $X$ only defined on $\Omega’$ is random variable on $\Omega’$ if it is measurable with respect to (w.r.t.) the trace $\sigma$-algebra $\mathscr{F} \cap \Omega’$. So, what is a trace $\sigma$-algebra? I found it here.

Definition. Let $\Omega$ be a set, and let $\mathscr{F}$ be a $\sigma$-algebra on $\Omega$. Let $\Omega’ \subseteq \Omega$ be a subset of $\Omega$. Then, the trace $\sigma$-algebra (of $\Omega’$ in $\mathscr{F}$), $\mathscr{B}$, is defined as:

It is a $\sigma$-algebra on $\Omega’$.

Now we can define what a positive supermartingale is. Let $(\Omega, \mathscr{F}, \mathbb{P})$ be our probability space and $(\mathscr{B}_n, n \in \mathbb{N})$ an increasing sub-$\sigma$-algebrs of $\mathscr{F}$ (a.k.a a filteration).

Definition. An adapted sequence $(X_n, n \in \mathbb{N})$ of positive random variables is called a positive supermartingale if the almost sure (a.s.) inequality

is satisfied for all $n \in \mathbb{N}$. A supermartingale is by definition a sequence of random variables (r.v.s) which “decrease in conditional mean”. For a sequence positive r.v.s denoting the sequence of values of the fortune of a gambler, the supermartingale condition expresses the property that at each play the game is unfavourable to the player in conditional mean.

We note that the inequality defining a supermartingale implies that

In fact the defintion implies that,

if $n \geq m$. Therefore, the sequence ($\mathbb{E}^{\mathscr{B}_m}(X_n)$) is decreasing.

The following proposition is so cool and is so fundamental.

Proposition (Maximal inequality). For every positive supermartingale, the r.v. $\sup_n X_n$ is a.s. finite on the set {$X_0 < \infty$}, and satisfies the following inequality

for all constants $a > 0$.

Before going into the proof, remember that $\mathbb{P}^{\mathscr{B}}(A) = \mathbb{E}^{\mathscr{B}}(\mathbb{1}_A)$ and

First, we need an auxiliary lemma which constitutes the switching principle for supermartingales. But before that, I need to talk about the concept of the stopping time.

Stopping time (unsurprisingly) is a concept from gambling. A stopping rule for the player is a rule for leaving the game, based at each time on information it his/her disposal at that time. By this definition, a “dishonest” player who decides to leave the game any time already knowing certain subsequent outcomes of the game is excluded. Also, note that the stopping time could be $\infty$ meaning that the game never ends.

Definition. Let $\mathbb{N}^*$ denote $\mathbb{N} \cup {\infty}$. A mapping $\nu: \Omega \to \mathbb{N}^*$ is called a stopping time if

The $\sigma$-algebra $\mathscr{B}_\nu$ is associated with the stopping time as the subsets of $\Omega$ defined by

Note that events in $\mathscr{B}_\nu$ are prior to $\nu$.

Back to the considered lemma:

Lemma (master). Given tow positive supermartingales $(X^{(i)}_n)(i =1, 2)$ and a stopping time $\nu$ such that $X_\nu^{(1)} \geq X_\nu^{(2)}$ on {$\nu < \infty$}, the formula

defines a new positive supermartingale.

Proof. Indeed, the defining formula of the $X_n$ can also be written

then it is clear that $X_n$ is $\mathscr{B}_n$ measurable. The supermartingale property of $X^{(i)}_n$ allows us to write

The assumption $X_\nu^{(1)} \geq X_\nu^{(2)}$ implies that $X_{n + 1}^{(1)} \geq X_{n + 1}^{(2)}$ on {$\nu = n + 1$}, and

Hence,

Using the above lemma, let us associate with the positive supermartingale of the proposition the stopping time defined by

Since $X_{\nu_a} > a$ on {$\nu_a < \infty$} and since the constant $a$ can be considered a supermartingale, the formula,

\(Y_n = \begin{cases} X_n & n < \nu_a\\ a & n \geq \nu_a \end{cases}\) defines a new supermartingale by our previous lemma. Hence, $Y_0 \geq \mathbb{E}^{\mathscr{B}_0}[Y_n]$. Since $Y_0$ is equal to $X_0$ or $a$ according to the relation between $X_0$ and $a$, and since $Y_n \geq a \mathbb{1}_{{\nu_a \leq n}}$, we have:

Letting $n$ tend to infinity, we obtain

Since {$\nu_a < \infty$} = {$\sup_n X_n > a$}. It suffices to replace $a$ by $a\left(1 - k^{-1}\right)$ in the inequality above and let $k$ tend to infinity to obtain the same inequality with $\geq$ instead of $>$ on the left-hand side. Let us integrate both sides over the event {$X_0 < \infty$}, which belongs to $\mathscr{B}_0$. Let $A := {\sup_n X_n > a}$ we find that

As $a$ tends to infinity, the R.H.S. tends to zero by the dominated convergence theorem and we have

Box. (Analysis II) A box $B$ in $\mathbb{R}^n$ is any set of the form

where $b_i \geq a_i$ are real numbers. The volume of this box is defined as

Outer Measure. (Analysis II) If $\Omega$ is a set, we define the outer measure $m^*(\Omega)$ of $\Omega$ to be quantity

Measurable Sets. (Analysis II) Let $E$ be a subset of $\R^n$. We say $E$ is Lebesgue measurable, or measurable for short, iff we have the identity

\(m^*(A) = m^*(A \cap E) + m^*(A-E)\) for every subset $A$ of $\R^n$.  If $E$ is measurable, we define the Lebesgue measure of $E$ to be $m(E)= m^*(E)$; if $E$ is not measurable, we leave $m(E)$ undefined. In words, $E$ being measurable means that if we use the set $E$ to divide up an arbitrary set $A$ into two parts, we keep the additivity property.

Measurable Functions. (Analysis II) Let be a measurable subset of $\mathbb{R}^n$ and let $f: \Omega \to \R^m$ be a function. A function $f$ is measurable iff $f^{-1}(V)$ is measurable for every open set $V \subseteq \R^m$. Another characterization of measurable functions is given by: Let $\Omega$ be a measurable subset of $\R^n$. A function $f: \Omega \to \R^*$ is said to be measurable iff $f^{-1}((a, \infty]))$ is measurable for every real number $a$.

Absolutely Integrable. (Analysis II) Let $\Omega$ be a measurable subset of . A measurable function $f: \Omega \to \mathbb{R}^* := \mathbb{R} \cup {-\infty, +\infty}$ is said to be absolutely integrable if the integral $\int_\Omega f$ (w.r.t. the Lebesgue measure) is finite.

Pointwise Convergence. (Analysis II) The most obvious notion of convergence of functions is pointwise convergence, or convergence at each point of the domain. Let $\left(f^{(n)} \right)_{n = 1}^\infty$ be a sequence of functions from one metric space $(X, d_X$) to another $(Y, d_Y)$, and let $f: X \to Y$ be another function. We say that $\left(f^{(n)} \right)_{n = 1}^\infty$ converges pointwise to $f$ if we have

i.e.,

We call the function f the pointwise limit of the functions $f^{(n)}$.

Limits of measurable functions are measurable (Analysis II) Let $\Omega$ be a measurable subset of $\mathbb{R}^n$, for each positive integer $n$, let $f_n: \Omega \to \mathbb{R}^*$ be a measurable function. Then, the functions $\sup_n f_n, \inf_n f_n, \limsup_{n \to \infty} f_n, \mathrm{and}\, \liminf_{n \to \infty} f_n$ are also measurable. In particular, if $f_n$ converge pointwise to another function $f: \Omega \to \mathbb{R}^*$, then $f$ is also measurable.

Proof. We first prove the claim about $\sup_n f_n$. Call this function $g$. We have to prove that $g^{-1}((a, \infty]))$ is measurable for every $a$. First we show that

then the claim follows since the countable union of measurable sets is measurable. To show the above display consdier two cases:

• $\subseteq$

If $x \in g^{-1}((a, \infty]))$, then $g(x) = sup_n f_n(x) > a$. If every $f_n(x) \leq a$, then $\sup_n f_n(x) \leq a$ which is a contradiction. Hence, there exists some $n$ with $f_n(x) > a$. Thus, $x \in f^{-1}((a, \infty]))$ for that $n$, so $x$ belongs to the union.

• $\supseteq$

If $x \in \cup_{n \geq 1}f_n^{-1}((a, \infty]))$, then for some $n$ we have $f_n(x) > a$. Therefore, $g(x) = \sup_n f_n(x) \geq f_n(x) > a$ and $x \in g^{-1}((a, \infty]))$.

Since both inclusions hold, the sets are equal.

One important note that we know {$g > a$} $= \cup_n$ {$f_n > a$}. But, {$g \geq a$} $\neq \cup_n$ {$f_n \geq a$}. Because if the supremum is at least $a$ does not mean that at least one of the $f_n$s will match it. We can fix this by using an approximation from below:

Back to the main proposition, a similar argument works for $\inf_n f_n$. The claim for $\limsup$ and $\liminf$ then follow from the identities

Lebesgue Monotone Convergence Theorem. (Analysis II) Let $\Omega$ be a measurable subset of $\R^n$, and let $f_n$ be a sequence of non-negative functions from $\Omega$ to $[0, \infty]$, which are increasing in the sense that

Note we are assuming that $f_n(x)$ is increasing with respect to $n$; this is a different notion from $f_n(x)$ increasing with respect to $x$. We have

and

Proof. For the first conclusion, we should prove that

If $0 \leq f(x) \leq g(x)$ for all $x \in \Omega$ for measurable non-negative functions $f, g$, then we have $\int_\Omega f \leq \int_\Omega g$. Let $h := g - f \geq 0$. We proceed by showing that $0 \leq \int_\Omega h \leq \infty$. Since $f, g$ are measurable, $h$ is measurable and since $h$ is non-negative as well, its Lebesgue integral is equal to

Fix an $s$. Since $s$ is simple, it can be written as $s = \sum_{j = 1}^{N} c_j m(E_j)$, where $c_j > 0, \cup_j E_j = \Omega$. The sum of non-negative numbers is between zero and $\infty$, hence their $\sup$ is between zero and infinity.

Now the second conclusion. Following a similar argument of above,

for every $n$ including its superimum, i.e.,

If we show that $\int_\Omega \sup_m f_m \leq \sup_n \int_\Omega f_n$, then the proof will be completed. To proceed, by the definition of $\int_\Omega \sup_m f_m$, it is sufficient to show that for all non-negative measurable function $s$ that it is dominated by $\sup_m f_m$ the following holds

\(\int_\Omega s \leq \sup_n \int_\Omega f_n.\) If we show that

\(\int_\Omega s \leq \sup_n \int_\Omega f_n + \epsilon\int_\Omega s\) for every $0 < \epsilon < 1$ (note that our functions are all non-negative hence the range of the epsilon); the claim follows by taking limits as $\epsilon \to 0$. $(\star)$

By construction,

Hence, for all $x \in \Omega$, there exists an $N$ such that

\(f_N(x) \geq (1 - \epsilon)s(x).\) Since $f_n$ are increasing, this implies taht $f_n(x) \geq (1 - \epsilon)s(x)$ for all $n \geq N$.

Define the sets

\(E_n := \{x \in \Omega: f_n(x) \geq (1 - \epsilon) s(x)\}.\) Since $f_n$ is measurable by assumption, $s$ is measurable because it’s a simple function, the function $f_n(x) - s(x) + \epsilon f(x)$ is measurable, hence is each $E_n$. We also have that $E_1 \subseteq E_2 \subseteq \dots$, and $\cup_{n = 1}^\infty E_n = \Omega$. We have that

if we show that $(\star\star)$ holds. Then by taking limits as $\epsilon \to 0$ and taking suprema, it suffices to show that

which would prove $(\star)$.

Since $s$ is a simple function, $\int_\Omega s = \sum_{j = 1}^N c_j \cdot m(F_j)$, where $F_1, F_2, \dots$ are disjoint and in $\Omega$. Similarly, $\int_{E_n} s = \sum_{j = 1}^N c_j \cdot m(F_j \cap E_n)$. Since the sums are finite and the summands are positive, it suffices to show that $\sup_n m(F_j \cap E_n) = m(F_j)$. $(\star\star\star)$

So to summarize, we need to prove the following that prove $(\star)$.

1. $\int_{E_n} f_n \leq \int_{\Omega} f_n$. $(\star\star)$
2. $\sup_n m(F_j \cap E_n) = m(F_j)$. $(\star\star\star)$

The following proposition proves $(\star\star)$:

Let $\Omega$ be a measurable set, and $f: \Omega \to [0, \infty]$ be a non-negative measurable function. If $\Omega’ \subseteq \Omega$ is measurable, then $\int_{\Omega’} f = \int_{\Omega} f \mathbb{1}_{{\Omega’}} \leq \int_\Omega f$.

Proof. By the definition of the Lebesgue integral

Fix $s$. We have

But, $F_j \cap \Omega’ \subseteq F_j$. Therefore, $m\left(F_j \cap \Omega’\right) \leq m(F_j)$. By multiplying both sides by positive constants $c_j$ and summing over $j$ we get that $\int_{\Omega’} s \leq \int_{\Omega} s$. Taking suprema from both sides competes the proof.

The following proposition helps proving $(\star\star\star)$:

If $A_1 \subseteq A_2 \subseteq \dots$ is an increasing sequence of measurable sets, then

Proof.

Define

Then, $A := \cup_{j = 1}^\infty A_j = \cup_{j = 1}^\infty B_j$, and $A_N := \cup_{j = 1}^N A_j = \cup_{j = 1}^N B_j$. Hence,

So in $(\star\star\star)$, we have

Fatou’s Lemma. (Analysis II) Let $\Omega$ be a measurable subset of $\mathbb{R}^n$, and let $f_1, f_2, \dots$ be a sequence of non-negative functions from $\Omega$ to $[0, \infty]$. Then

Proof.

$\inf_{n \geq m} f_n \leq f_j$ for all $j \geq m$. Hence, $\int_\Omega \inf_{n \geq m} f_n \leq \int_\Omega f_j$. By taking infima w.r.t. $j$, we have

Therefore, we obtained the following that completes the proof

Lebesgue Dominated Convergence Theorem. (Analysis II) Let $\Omega$ be a measurable subset of $\mathbb{R}^n$, and let $f_1, f_2, \dots$ be a sequence of measurable functions from $\Omega$ to $\mathbb{R} \cup {-\infty, +\infty}$ which converge pointwise. Suppose also that there is an absolutely integrable function $F: \Omega \to [0, \infty]$ such that $|f_n(x)| < F(x)$ for all $x \in \Omega$ and all $n = 1, 2, 3, \dots$. Then,

Proof. If $F$ was infinite on a set of non-zero meaure, then $F$ would not be absolutely integrable thus the set where $F$ is infinite has zero measure. We may delete this set from (this does not affect any of the integrals) and thus assume without loss of generality that $F(x)$ is finite for every $x \in \Omega$, which implies the same assertion for the $f_n(x)$.

Let $f:\Omega \to \mathbb{R} \cup$ {$-\infty, +\infty$} be the function $f(x) := \lim_{n \to \infty}f_n(x)$ which exists by assumption. Since $f$ is the limit of measurable functions, it’s measurable. Also, since $|f_n(x)| \leq F(x)$ for all $n$ and all $x \in \Omega$ , we see that each $f_n$ is absolutely integrable, and by taking limits we obtain $| f(x)| \leq F(x)$ for all $x \in \Omega$ , so $f$ is also absolutely integrable. Our task is to show that $\lim_{n \to \infty}\int_{\Omega} f_n = \int_\Omega f$. The functions $F + f_n$ are non-negative and converge pointwise to $F + f$. So by Fatou’s lemma

But also, $F - f_n$ are non-negative and converge pointwise to $F + f$. So, again by Fatou’s lemma

Hence, we showed that

Hence, the $\liminf$ and $\limsup$ of $\int_\Omega f_n$ are equal as we wanted.

Remark. The preceding proof is valid without any change if we change the constant $a$ with any $\sB_0$-measurable r.v. Say $A$ is such an r.v. Then, it means if $\mathbb{P}^{\sB_0}(A \leq \sup_n X_n) = 1$, then $A \leq X_0$, i.e., $X_0$ is largest $\sB_0$-measurable r.v. dominated by $\sup_n X_n$. More generally, for any $\sB_p$-measurable r.v. $A$ that satisfies $A \leq \sup_{n \leq p} X_n$ can be seen as applying the preceding results to the supermartigale $(\sup_{n \leq p} X_n, X_{p+1}, X_{p+2}, \dots)$ adapted to the $(\sB_p, \sB_{p + 1}, \dots)$.

Theorem. Every positive supermartingale $(X_n)$ almost surely converges. Furthermore, the limit $X_\infty = \lim_{n \to \infty} X_n$ a.s. satisfies the following inequality

Proof.

First, we’ll discuss what it means that a sequence of real numbers converges.

Given a sequence of real number $(x_n)$ in $\R^*$ and a pair of real number $a, b$ where $a<b$, let us define $\nu_k (k \geq 1)$ as some special moments in time, where

If some $\nu_k$ is not defined, we put it equal to $\infty$ and all subsequent indices. Let $\beta_{a, b}$ be the largest value of $p$ where $\nu_{2p}$ is finite. If all $\nu_k$ are finite, then $\beta_{a, b} = \infty$. $\beta_{a, b}$ denote the number of upcrossings of the sequence $(x_n$) on $[a, b]$. We can see that

Therefore, we can deduce that a sequence in $\R^*$ is convergent iff $\beta_{a, b} <\infty$ for every $a < b \in R$. Now, let’s considering the case of the sequence of r.v.s $(X_n)$. Note that the r.v.s $\nu_k(\omega$) are $\sB_n$-measurable. This is due to

\(\{\nu_{2p} = n\} = \cup_{m < n} \{\nu_{2p - 1} = m\: \mathrm{and}\: X_{m + 1} < b, \dots, X_{n - 1} < 1, X_n \geq b\},\) and a similar argument for the odd indices. The event {$\beta_{a, b} \geq p$} $=$ {$\nu_{2p} < \infty$} shows that $\beta_{a, b}$ is also an r.v. Hence, the convergence criterion is

Rationals are dense. (Analysis 1) If $x$ and $y$ are two rationals that $x < y$, then there exists a third rational $z$ such that $x < z < y$.

Proof.

Set $z := \frac{x + y}{2}$. Since $x <y$, then $\frac{x}{2} < \frac{y}{2}$. If we add $\frac{y}{2}$ to the both sides, we get $z < y$. A symmetrical argument shows $x < z$, hence $x < z < y$. $\square$

A homeomorphism. (Topology) Let $X$ and $Y$ be topological spaces (like open intervals); let $f: X \to Y$ be a bijection. If both the function $f$ and the inverse function $f^{-1}: Y \to X$ are continuous, then $f$ is called homeomorphism. You may have studied in modern algebra the notion of an isomorphism between algebraic objects such as groups or rings. An isomorphism is a bijective correspondence that preserves the algebraic structure involved. The analogous concept in topology i s that of homeomorphism; i t is a bijective correspondence that preserves the topological structure involved.

Hence, to prove our proposition, we need to prove $\beta_{a, b} < \infty$ a.s. for every $0 < a < b \in \R$. We only considered positive numbers since $(X_n)$ is positive and we have a homeomorphism between $\R^*$ and $[0, \infty]$ using $f(x) = x, x \geq 0$.

To this end, we need the Dubin’s inequalities.

Dubin’s inequalities. For every positive super martingale $(X_n)$ the upcrossing numbers are r.v.s satisfying

for every integer $k \geq 1$ and real numbers $a < b$. Therefore, r.v.s $\beta_{a, b}$ are a.s. finite.

Proof. First note that the set of stopping times {$\omega: \nu_k(\omega) =n$} belong to $\sB_n$ so $\nu_k$ are $\sB_n$-measurable. Now extending the master lemma, we can define the following supermartingale:

In fact we have that:

By construction we have that $Y_0 = \min\left(1, \frac{X_0}{a}\right)$. Since {$Y_n$} is a supermartingale we have that $Y_0 \geq \Ev{Y_n}{\sB_0}$. Also on the set {$n \geq \nu_{2k}$}, $Y_n \geq \left(\frac{b}{a}\right)^{k}$, or equivalently $Y_n \geq \left(\frac{b}{a}\right)^{k} \cdot \I${$n \geq \nu_{2k}$}. Using all these facts, we have:

All that remains is to let $n \to \infty$ and noting that {$\nu_{2k} < \infty$} $=$ {$\beta_{a,b} \geq k$}. $\square$ ___

The final part of the proof involves showing that the limit $X_\infty = \lim_{n \to \infty} X_n$ a.s. satisfies the following inequality

\(\Ev{X_\infty}{\sB_n} \leq X_n, \quad n \ \in \mathbb{N}.\) The inequality

is valid if $n > p$. Let $n$ tend to infinity, then

where we used the Lebesgue dominated convergence theorem to exchange the expectation and the limit because $\left(\inf_{m \geq n} X_m, \, n \in \mathbb{N}\right)$ is an increasing bounded convergent sequence in $n$. The proof is completed.

We had already showed that $\sup_n X_n < \infty$ on {$X_0 < \infty$}, which implies that $X_\infty < \infty$ on {$X_0 < \infty$}; applying this result to the supermartingale $(X_n, n \geq p)$ adapted to the sequence $(\sB_n, n \geq p)$, we find that $X_\infty$ a.s. on {$X_p < \infty$} for all $p \in \mathbb{N}$ which is another way of completing the last part of our proof.

The end! :)

via GIPHY