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).



concentration inequality for averages of dependent random variables
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.


