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

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

Answer 1

The previous answer (and the link) did answer a reversed side of the question... not necessary the original question. But the methods are the same.

Suppose (WLOG) $a_1\ge a_2\ge \dots \ge a_n\ge 0$. We have two cases:

(1) $a_1\ge 1/2$

Then $\sum_{i=2}^n a_i^2 =1-a_1^2$, and by Chebyshev, $\mathbb{P}(|\sum_{i\ge 2} \varepsilon_i a_i|\ge 1+a_1)\le \frac{1-a_1^2}{(1+a_1)^2}=\frac{1-a_1}{1+a_1}\le 1/3$. So $\mathbb{P}(|\sum_{i\ge 2} \varepsilon_i a_i|\le 1+a_1)\ge 2/3$ and since the distribution is symmetric along $0$, we have $\mathbb{P}(\sum_{i\ge 2} \varepsilon_i a_i\in [-(1+a_1),0])\ge 1/3$. Therefore, there is $1/6$ probability that $a_1$ takes $+$, and other pull $a_1$ back into the region $[-1,a_1]$. Notice that $a_1$ takes $-$ we can get the same probability too, so in this case, it is $\ge 1/3$ probability that the total sum has absolute value $\le 1$.

(2) $a_1\le 1/2$

Therefore we can split all $a_i$ into two groups, and each group will have the sum of squares $[3/8,5/8]$. Call these two groups $b_j$ and $c_k$. So we have $\mathbb{P}(|\sum \varepsilon_j b_j|\ge 1)\le\sum b_j^2$, and $\mathbb{P}(|\sum \varepsilon_k c_k|\ge 1)\le\sum c_k^2$ by Chebyshev. There is a half of the probability (at least) if $\sum \varepsilon_k c_k$ and $\sum \varepsilon_j b_j$ are taking different signs. So, the probability that $|\sum \varepsilon_j b_j|\le 1$, $|\sum \varepsilon_k c_k|\le 1$, and they take the different signs is at least $(1-\sum c_k^2)(1-\sum b_j^2)/2$ which is at least $3/8\times 5/8\times 1/2=15/128$. So take $c=15/128$ will do the work.

Answer 2

As pointed out by Ankitp, the question has been answered here, on Math Overflow.

The global idea is to find a lower bound for $\mathbb P[|\sum \epsilon_i a_i|\le1]$ using the moment of order $4$ and $8$ of $ \sum \epsilon_i a_i$.