Question (4.8.2 from the Probabilistic Method 4th edition by Alon and Spencer):

Show that there is a positive constant $c$ such that for any $n$ real numbers $a_1,\dots,a_n$ satisfying $\sum\limits_{i=1}^na_i^2=1$, if $(\epsilon_1,\dots,\epsilon_n)$ is a random vector of iid random variables uniformly distributed on $\{\pm1\}$ then $\mathbb P[|\sum \epsilon_i a_i|\le1]\ge c$ .

I let $X=\sum\limits_{i=1}^n \epsilon_ia_i$, and I have computed $\Bbb E[X]=0$ and Var$(X)=1$.

By Chebyshev's inequality we get $\Bbb P[|X|\le 1]=1-\Bbb P[|X|>1]>1-\frac{\text{Var}(X)}{1}=0$ which is useless...

I guess I need a hint.

One other thing that is true from Cauchy Schwarz inequality is $$|X|^2=|\langle \epsilon,a\rangle|^2\le\sum\epsilon_i^2\sum a_i^2=n\cdot1=n\implies |X|\le \sqrt{n}$$

and it is true not matter how $\epsilon $ is chosen. So the density of $|X|$ is supported on $[0,\sqrt{n}]$.

  • $\begingroup$ Sorry I keep commenting half-baked things and deleting: Here is an approach that (might) work: There must be an $a_i$ such that $a_i^2\geq 1/n$. WLOG assume that is $a_n$. Define $Y=\sum_{i=1}^{n-1} a_i\epsilon_i$ and use a bound such as Hoeffding inequality on $P[Y\geq 1-a_n] + P[Y\leq -1-a_n]$. $\endgroup$
    – Michael
    Dec 29 '20 at 22:24
  • $\begingroup$ I think this will work with the following modification: Define $Y$ as in my previous comment and compute a bound on $$P\left[\{Y>0, \epsilon_n<0\}\cap \{Y\leq 1+a_n\}\right]$$ $\endgroup$
    – Michael
    Dec 29 '20 at 22:44
  • 1
    $\begingroup$ This question already has an answer here. $\endgroup$
    – Ankitp
    Dec 30 '20 at 22:06

Your Answer

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

Browse other questions tagged or ask your own question.