# 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? Feb 22, 2013 at 7:13
• What is known about the dependency? Feb 22, 2013 at 14:24
• Brendan, thanks for point out the inequality typo. tipanverella: the rvs can be arbitrarily dependent. Feb 22, 2013 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. Feb 22, 2013 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.