Let $w\ll n$ (say $w=n^{0.1}$) and $a_1,\ldots,a_w$ be positive real numbers such that $\sum_{i \in w} a_i=n$. Also, let $x_1,x_2,\ldots, x_w$ be i.i.d. $\pm 1$ random variables. What is the best $t$ such that one always has $$ \Pr_{x_1,\ldots, x_w} [|\sum_{i\le w} a_i x_i| \ge t] \ge 0.01 $$
-
$\begingroup$ Does it matter that $w \ll n$ ? $\endgroup$– Suresh VenkatMar 7, 2011 at 8:21
-
$\begingroup$ @suresh: Somehow to me, the worst case for anti-concentration about the mean i.e. $0$ seemed to be when all the $a_i$'s are the same i.e. about $n/w$. In case $w\gg n$, then all the $a_i$'s can be like $n/w$ and then the anti-concentration will only be about $n/\sqrt{w}$ which will go to $0$ as $w$ becomes larger. Anyway, in my case $w \ll n$. $\endgroup$– Anindya DeMar 7, 2011 at 17:06
2 Answers
The best $t$ I do not know. But one can for example get some bounds by applying the Paley-Zygmund inequality to the random variable $Z=(\sum_i a_i X_i)^2$.
-
$\begingroup$ Oops. I only wanted to make a comment, not an answer. $\endgroup$ Mar 7, 2011 at 12:57
Okay, I used Paley Zygmund inequality and unless I messed up the calculation, one gets that for $Z= (\sum_{i=1}^w a_i x_i)^2$, $$ \Pr [ Z \ge \Theta E[Z]] \geq \frac{(1-\Theta)^2}{3} $$ Now, $E[Z] = \sum_{i=1}^w a_i^2 \geq n^2/w$. This implies that $$ \Pr \left[ Z \ge \frac{ n^2}{2w}\right] \geq \frac {1}{12} $$ Thus, $$ \Pr \left[ \left|\sum_{i=1}^w a_ix_i \right| \ge \frac{ n}{\sqrt{2w}}\right] \geq \frac {1}{12} $$ Up to constant factors, this is the best that can be said as putting all the $a_i$'s = $n/w$ and applying Berry Esseen theorem shows.