Skip to main content
2 of 4
added 308 characters in body; added 11 characters in body; deleted 2 characters in body
gappy3000
  • 461
  • 3
  • 8

concentration inequality for averages of dependent random variables

Let $X \in R^n$ be a random vector such that

$$P(|X_i| > \epsilon) \le e^{-\epsilon^2}$$

What is a tight bound on

$$P(\sum_{i=1}^n |X_i| > \epsilon)$$

and on

$$P(\max_{1\le i\le n} |X_i| > \epsilon)?$$

The $X_i$ can be arbitrarily dependent.

A simpler question, which I believe can help to answer the question above, is the following: if $X_1, X_2\ge 0$ are two possibly dependent random variables such that $P(X_i > \epsilon) \le e^{-\epsilon^2}$, what is the best bound on $P(\max\left{X_1, X_2\right}> \epsilon)$?

gappy3000
  • 461
  • 3
  • 8