# Anti-concentration about the mean for sum of Bernoulli random variables

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$$

-
Does it matter that $w \ll n$ ? –  Suresh Venkat Mar 7 '11 at 8:21
@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$. –  Anindya De Mar 7 '11 at 17:06

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