# Supermartingales and convergence

These feel like basic enough questions, but I don't know where to find the answer.

Let $X_1,X_2,X_3,\dots$ be a supermartingale such that $|X_{n+1} - X_n| < K$ for all $n$ ($K$ fixed). Does the event $X_n \rightarrow +\infty$ necessarily have probability zero? What if we also have the condition that given $X_1,\dots,X_n$ there are only $N$ possibilities for $X_{n+1}$, each with probability $1/N$?

Suppose in addition that $\mathbb{E}(X_{n+1}|X_1,\dots,X_n) \le X_n - c_n$, where $\sum c_n \rightarrow +\infty$. Is $X_n \rightarrow -\infty$ almost certain?

-
Sounds like the ans are yes to the first and no to the second. Yes: by the decomposition it's a martingale minus something. The mg can't go to $+\infty$ by @Camomille's ans so nor can the supermg. No: If you define $X_n$=(position of a r.w. at time $n$) - $\log n$ then you get $c_n\approx 1/n$ but $X_n\not\to-\infty$. –  Anthony Quas Feb 17 '11 at 15:47
To add another example to that of Anthony: If $X_n=-\infty$ with probability $p_n$ and 0 otherwise and $\sum p_n < \infty$ then $X_n = 0$ for all $n$ with positive probability, but the expectation you wrote is $-\infty$. –  Ori Gurel-Gurevich Feb 18 '11 at 3:06

For a martingale $M_n$ with bounded increment, then, almost surely :

• either $M_n$ converges to a finite limite.

• or $\limsup M_n=\infty$ and $\liminf M_n=-\infty$.

Sketch of the proof. One can assume that $M_0=0$. Let $T$ be the first time at which the martingale goes below $-A$. Then $M_{n \wedge N}$ is a martingale bounded from below, therefore it converges. Then $M_n$ converges if $N$ is infinite etc.

For your problem consider the Doob decomposition.

-
This appears as Theorem 5.3.1 in R. Durrett, Probability: Theory and Examples (4ed). –  Nate Eldredge Feb 17 '11 at 15:46
Sounds like just the result I wanted, thanks! –  Colin Reid Feb 17 '11 at 15:53
A little English note. We don't say "either A either B" instead we say "either A or B". Unlike many other languages that use the same introductory word on both clauses. –  Gerald Edgar Feb 17 '11 at 18:25
Gerald: thanks for this note! –  camomille Feb 17 '11 at 18:57
Let $X_t=M_t+Y_t$ where $M_t$ is a martingale and $Y_t$ is predictable. Let $\mu_t=\mathbb E[X_t]=\mathbb E[Y_t]$ and $\sigma_t^2=\sum_{s\le t}\mathbb E[(M_s-M_{s-1})^2|M_1,\ldots,M_{s-1}]$. By martingale central limit theorem, $M_t$ is asymptotically normal with mean 0 and variance $\sigma_t^2$, so a sufficient condition for $X_t\rightarrow-\infty$ almost surely is $\sigma_t=o(|\mu_t|)$ as $t\rightarrow\infty$.
(To be precise, $\sigma_t$ is a random variable, so you really need to do some fiddling with stopping times as demonstrated in the Wikipedia article on martingale CLT, but the gist of it is that it will converge almost surely if the mean dominates the variance.)