Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as

$$ P(X_t-X_0 \leq -t) \leq exp\left( -{\frac{t}{2c^2}} \right)\tag{1} $$

Now, is there anyway that we can bound this probability $$ P(X_n-X_0 \leq -n, \ \ \forall n\geq t ) \tag{2} $$ other than applying the union bound?

I am expecting (1) and (2) to have close value.

In other words, I'm looking for a way to tighten the union bound for events with large overlap, in the setting of this multiple joint tail event probability.

Any reference is appreciated. Thanks.


Yes, but with the price of additional assumptions on variances $\sigma^2$ of samples $X_t$([1]'s proof can be extended to non-identical variance $\sigma ^2_i$). For example, [1] Theorem 2 strengthens the result to (28). These results can also be proved using the methods of types as mentioned in [1] part IV. Consider the case of martingale first, for submartingale in OP, see part III E., Theorem 2 stated that $$P(|X_n-X_0|>\alpha n)\leq 2 \exp \left(n\cdot \operatorname{KLdiv}\left(\frac{\frac{\alpha}{c}+\frac{\sigma^{2}}{c^{2}}}{1+\frac{\sigma^{2}}{c^{2}}},\frac{\frac{\sigma^{2}}{c^{2}}}{1+\frac{\sigma^{2}}{c^{2}}}\right) \right)$$ Specifically when $\sigma^2=c^2$, 1 showed this special case $$P(|X_n-X_0|>\alpha n)\leq 2 \exp \left(\frac{n\alpha^2}{2c^2}\right)$$ for some constant $d>0$. You can refine it further using (34). [1] Theorem 3 yields an even more complicated(but looser bound) Lambert-functional bound.

[1]Sason, Igal. "On refined versions of the Azuma-Hoeffding inequality with applications in information theory." arXiv preprint arXiv:1111.1977 (2011). https://arxiv.org/pdf/1111.1977.pdf

  • $\begingroup$ Thanks. I checked the reference you gave a bit before. But if I understand it correctly, this is refinement of the Azuma, not the refinement of the union bound of the joint event that I was looking for. How do we bound the probability that better than direct union + any refinement of Azuma, using the variance? $\endgroup$ Apr 26 '17 at 4:26
  • $\begingroup$ @Sung-EnChiu I do not think it is possible to improve union bound without further assumption on the martingale. $\endgroup$
    – Henry.L
    Apr 26 '17 at 11:00
  • $\begingroup$ Is there example or reason that the union bound is tight enough here? How do you see that it's not possible to improve the union bound? The events are having large overlap instead of disjoint, aren't they? $\endgroup$ Apr 26 '17 at 15:05
  • $\begingroup$ @Sung-EnChiu Yes, but the increments are not overlapping and how can you improve that? Or in other words, overlapping does not necessarily means that the bound can be improved since the events are not independent. $\endgroup$
    – Henry.L
    Apr 26 '17 at 16:24
  • $\begingroup$ Actually exactly because they are dependent, and the ways that they are dependent suggesting that union bound is a loose bound, although tight in exponent. It does not necessarily mean that we can improve the union bound easily, but do you have a counter-example says that it's not possible? Or an example says that the union bound is close to the actual value? I don't understand why it is not possible. What is the reason that you think it's not possible? $\endgroup$ Apr 27 '17 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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