3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Why did you put $\gt$ in one place and $\ge$ in the other places? $\endgroup$
    – Brendan McKay
    Feb 22, 2013 at 7:13
  • $\begingroup$ What is known about the dependency? $\endgroup$
    – tipanverella
    Feb 22, 2013 at 14:24
  • $\begingroup$ Brendan, thanks for point out the inequality typo. tipanverella: the rvs can be arbitrarily dependent. $\endgroup$
    – gappy3000
    Feb 22, 2013 at 15:19
  • $\begingroup$ 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. $\endgroup$
    – tipanverella
    Feb 22, 2013 at 16:26

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.