9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does it matter that $w \ll n$ ? $\endgroup$ – Suresh Venkat Mar 7 '11 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 De Mar 7 '11 at 17:06
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oops. I only wanted to make a comment, not an answer. $\endgroup$ – camomille Mar 7 '11 at 12:57
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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