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 $$
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
9
2
|
|||||||
|
|
2
|
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$. |
|||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
1
|
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. |
||
|
|
