# there is a positive constant $c$ such that for any $n$ real numbers $a_i$ with $\sum a_i^2=1$, $\mathbb P[|\sum \epsilon_i a_i|\le1]\ge c$

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

• 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]$. Dec 29 '20 at 22:24
• 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]$$ Dec 29 '20 at 22:44
• This question already has an answer here. Dec 30 '20 at 22:06