Large deviation/concentration inequality for submartingale

Question

Let $S_t = M_t + D_t$ be the sum of a martingale $\left(M_t\right)_{t=1,2,\ldots}$ and a predictable process $(D_t)_{t=1,2,\ldots}$ such that the variance of the increments of $M$ is uniformly bounded $$\mathbb{E}\left[\left(M_{t+1}-M_t\right)^2 | \mathcal{F}_t\right] \leq v$$ and the increments of $D$ are uniformly bounded from below. i.e. there exists $\Delta>0$ such that $$ D_{t+1} - D_t \geq \Delta > 0 \,. $$ I want to show that for all $\alpha<\Delta$ $$ \lim_{t \to \infty} \mathbb{P}[S_t \leq \alpha \, t ] = 0\,. $$

Answer 1

For convenience, suppose that $D_0 = 0$ and $M_0=0$. The lower bound $D_{t+1} - D_t \ge \Delta$ implies that $D_{t} \ge \Delta t$ a.s., i.e., $D_t$ grows at least linearly with $t$. Thus, for any $t \in \mathbb{N}$ we have that $$ \{ S_t = M_t + D_t \le \alpha t \} \subset \{ M_t + \Delta t \le \alpha t \} \tag{$\star$} $$
Also, note that $$ \mathbb{E} \left\{ (M_{t+1}-M_t)^2 \mid \mathcal{F}_t \right\} \le \nu \implies \mathbb{E} M_{t}^2 \le \nu t \tag{$\diamond$} $$ uniformly in $t$. We apply these two simple facts below.

Let $\tilde M_t = -M_t$ and $\tilde M_t^* = \max_{1 \le s \le t} \tilde M_s$. Then, ($\star$) implies that \begin{align*} \mathbb{P}( S_t \le \alpha t) &\le \mathbb{P}( M_t \le - (\Delta - \alpha) t ) \\ &\le \mathbb{P}( \tilde M_t \ge (\Delta - \alpha) t ) \\ &\le \mathbb{P}( \tilde M_t^* \ge (\Delta - \alpha) t) \\ &\le \frac{1}{(\Delta - \alpha) t} \mathbb{E} \tilde M_t^+ \\ &\le \frac{1}{(\Delta - \alpha) t} \frac{\sqrt{\mathbb{E}M_t^2 }}{2} \\ &\le \frac{\sqrt{\nu}}{2 (\Delta - \alpha) \sqrt{t}} \end{align*} where we used a discrete-time martingale inequality in terms of $(a)^+ = \max(a,0) = (a+|a|)/2$, Jensen's inequality to bound $\mathbb{E} |M_t|$, and the bound ($\diamond$) on the second moment of $M_t$.

Pass to the limit as $t \to \infty$ in the final inequality to obtain the desired asymptotic result.

Answer 2

This looks like a weak law of large numbers, and in fact a strong law holds: I claim that $\liminf_{t \to \infty} \frac{S_t}{t} \ge \Delta$ almost surely, which implies the desired result.

The key is to show that $\frac{M_t}{t} \to 0$ almost surely. Then we have $\frac{S_t}{t} = \frac{M_t}{t} + \frac{D_t}{t} \ge \frac{M_t}{t} + \Delta$ and can take the liminf of both sides.

Let $\newcommand{\qm}{\langle M \rangle}\qm_t$ be the quadratic variation of $M_t$. The given assumption implies that $\qm_t \le vt$. We know $\qm_t$ is an increasing process so its limit $\qm_\infty$ exists almost surely (but could take the value $+\infty$).

We need the following two results which can be found in http://math.ucsd.edu/~pfitz/downloads/courses/winter05/math280b/martslln.pdf. (I think they should also be in Williams's Probability with Martingales.)

1. (Theorem 2(a) from link) Almost surely, if $\qm_\infty < \infty$ then $M_t$ converges to a finite limit.

So in this case we have $\frac{M_t}{t} \to 0$.

2. (Theorem 3 from link) Almost surely, if $\qm_\infty = \infty$ then $\frac{M_t}{\qm_t} \to 0$.

Since $\frac{\qm_t}{t}$ is bounded between $0$ and $v$, again we have $\frac{M_t}{t} \to 0$.