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 $$
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The best $t$ I do not know. But one can for example get some bounds by applying the PaleyZygmund 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. 

