Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Oops. I only wanted to make a comment, not an answer. –  camomille Mar 7 '11 at 12:57
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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