MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
1

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?

flag
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

1

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.

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.