# concentration inequality for averages of dependent random variables

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

$$P(|X_i| > \epsilon) > 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. The best I can get for both bounds is $n e^{-\epsilon^2}$ (using the union bound).

-
Why did you put $\gt$ in one place and $\ge$ in the other places? – Brendan McKay Feb 22 '13 at 7:13
What is known about the dependency? – tipanverella Feb 22 '13 at 14:24
Brendan, thanks for point out the inequality typo. tipanverella: the rvs can be arbitrarily dependent. – gappy3000 Feb 22 '13 at 15:19
I asked because you can get large deviation estimates if you have second moments estimates for the sum. This would imply (with some luck) exponential bounds for the probability of the sum. But of course this would require some covariance specification. – tipanverella Feb 22 '13 at 16:26

Without further assumptions you can't do better than the union bound (which should be $n e^{-\epsilon^2}$ as you've written things). If $X_i$ are identically distributed and the events $(|X_i| > \epsilon_0)$ are disjoint then you get equality in the union bound for the maximum whenever $\epsilon \ge \epsilon_0$. If the $X_i$ are $\epsilon$ times indicators of disjoint sets then you also get equality in the union bound for the sum.

Very little is true for arbitrarily dependent random variables which is both nontrivial and interesting. It's helpful to keep two extreme cases in mind: disjoint support, and all variables exactly equal to each other.

-