Skip to main content
5 of 5
added 1 character in body

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.