# 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]$. Commented Dec 29, 2020 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]$$ Commented Dec 29, 2020 at 22:44
• This question already has an answer here. Commented Dec 30, 2020 at 22:06

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.

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