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?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Do you mean almost surely vs. surely? Almost surely implies probability 1... $\endgroup$– TerronaBellCommented Aug 14, 2012 at 16:26
-
$\begingroup$ Yes, I mean almost surely instead of surely. $\endgroup$– Patt GeffreyCommented Aug 14, 2012 at 16:31
-
$\begingroup$ 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. $\endgroup$– Mateusz WasilewskiCommented Aug 14, 2012 at 16:38
-
$\begingroup$ 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$. $\endgroup$– Patt GeffreyCommented Aug 14, 2012 at 16:54
-
1$\begingroup$ 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. $\endgroup$– Bill JohnsonCommented Aug 14, 2012 at 21:02
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 14, 2012 at 23:02