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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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... – fuzzytron Aug 14 at 16:26
Yes, I mean almost surely instead of surely. – Patt Geffrey Aug 14 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 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 at 16:54

1
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 at 21:02
show 3 more comments

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9268019795417786, "perplexity_flag": "middle"}