Large deviation/concentration inequality for submartingale 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\,.
$$
 A: 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.)

  
*
  
*(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$.


  
*(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$.
A: 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.
