Concentration inequality of joint event over time of a submartingale

Question

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.

Answer 1

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

Answer 2

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.]