Skip to main content
3 of 5
edited tags
Henry.L
  • 8.1k
  • 8
  • 48
  • 74

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, \ \ \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.