This is a question in the book Probabilistic Method by Noga Alon. The question is from the chapter second moment. Show that there is a positive constant $c$ such that the folowing holds. For any $n$ reals $a_{1}, a_{2},....,a_{n}$ such that $\sum_{i=1}^{i=n} (a_{i})^{2} =1 $ if $b_{1}, b_{2}....b_{n}$ is a $ \{-1,1\} $ random vector obtained by choosing each $b_{i}$ randomly, independently with uniform distribution to be either $-1$ or $1$ then $Pr |\sum_{i=1}^{i=n}b_{i}a_{i}| \leq 1 | \geq c $

  • 1
    $\begingroup$ The average of the quantity inside the absolute value is zero and it's second moment is $1$. Can it be larger in value than $1$ always? $\endgroup$
    – A.S.
    Nov 21, 2015 at 8:08
  • $\begingroup$ i had worked that out. However we have to use something more to solve this question, I believe somewhere we will have to use the fact that the maximum value of the quantity will be $\sqrt{n}$ and there are at max $2^{n}$ distinct values taken by the quantity $\endgroup$
    – Varun
    Nov 21, 2015 at 13:03


You must log in to answer this question.

Browse other questions tagged .