3
$\begingroup$

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, \ \ \text{for some }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.

$\endgroup$
2
  • $\begingroup$ The event in (2) is an intersection, not a union $\endgroup$ Sep 18, 2021 at 21:21
  • $\begingroup$ Sry I corrected the question to be union. Basically I want to ensure that for all time after t, the whole martingale behaves "nice" and above the (n,-n) line , and trying to bound the probability of the "bad event" defined in the edited eq (2) $\endgroup$ Feb 2, 2022 at 23:08

2 Answers 2

3
$\begingroup$

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

$\endgroup$
7
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 1:43
0
$\begingroup$

There are better bounds than the Azuma-Hoeffding bound for the tail probability of a Martingale . A good starting point is the classical inequality of Freedman (1975) [1]. But in the union bound for your question, only a constant factor is lost. Let's see this in a more general context of estimating probability of a union of overlapping events in a probability space $(\Omega, {\cal F}, P)$. Let $A=\cup_{k=n}^M A_k$ where we allow $M$ to be infinity. Define $\tau(\omega):=\infty$ for $\omega \in A^c$, and $\tau(\omega):=\min\{k: \omega \in A_k\}$ for $\omega \in A$.

[In the question, $A_k=\{X_k\le -k\}$.]

Write $S:=\sum_{k=n}^M {\bf 1}_{A_k}$, so $E(S)$ is exactly the union bound for $P(A)$. We have $$E(S)= P(A)E(S|A)=P(A)E[S|\tau<\infty]\,.$$ If the events $A_k$ arise from a Markov chain or a Martingale, one can often estimate the conditional expectation $E[S|\tau<\infty]$ quite well, by averaging over the value of $\tau$. For instance, in the question proposed by the OP, we have $$\{\tau=k\} \Rightarrow \{ 1-k-c<X_k<-k\}$$, so for $ \ell >0$ we obtain $$ P(A_{k+\ell} | \tau=k) \le \exp\Bigl(\frac{-(\ell-c)^2}{2\ell}\Bigr)<e^{c}e^{-\ell/2}\,,$$ whence $$E[S| \tau=k] <B:=\frac{e^{c}}{1-e^{-1/2}}\,.$$ Since the RHS does not depend on $k$, we conclude that $$E[S| \tau<\infty] <B \,.$$ and $$P(A) >E[S]/B\,.$$

[1] Freedman, David A. "On tail probabilities for martingales." the Annals of Probability (1975): 100-118. [Cited 686 times according to Google scholar.]

$\endgroup$
1
  • $\begingroup$ Yes, the union bound is tight in the exponent in this case. But what I was looking for was to tighten the constant B. Even though it is just a constant, in practice it can be very large if we simply use the union-bound summation like what you did. $\endgroup$ Sep 21, 2022 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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