# Azuma's Inequality when the conditions hold with high probability?

In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the above inequality (for each $k$) holds with high probability?

-
Do you mean almost surely vs. surely? Almost surely implies probability 1... – TerronaBell Aug 14 '12 at 16:26
Yes, I mean almost surely instead of surely. – Patt Geffrey Aug 14 '12 at 16:31
What do you mean by high probability? Do you just want $|X_k - X_{k-1}|< c_{k}$ to hold with probability tending to $1$, as $k \to \infty$? I guess, that when this convergence is fast enough, then some sort of Azuma's inequality still holds, but only for tails distant enough and, of course, with worse constants. I haven't thought about it too long, so I may be wrong. – Mateusz Wasilewski Aug 14 '12 at 16:38
If the martingales considered is $(X_k)_{k=1}^{N}$, what I mean is that $\mathbb{P}(\forall k, |X_k - X_{k-1}| < c_k) \to 1$ as $N$ goes to $\infty$. – Patt Geffrey Aug 14 '12 at 16:54
The absolute values $|d_k|$ of the martingale differences can have any joint distribution subject to the boundedness constraint, so you can make the exceptional sets disjoint for a long time and $|d_k|$ large on the $k$-th exceptional set $A_k$. Piecing things together, you get a counterexample if $\Bbb{P}(A_k)\to 0$ but is not summable. – Bill Johnson Aug 14 '12 at 21:02

There is a large literature on variations of Azuma's inequality. One lemma that is similar to what you ask is Lemma 3.1 of this old paper of Wormald and myself. It considers the case where $|X_k-X_{k-1}|$ is within one bound with very high probability and within some wider bound always. There are lots of such results.