Concentration inequality of joint event over time of a submartingale 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.
 A: 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
A: 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.]
