Anti-concentration of bernoulli sums - MathOverflow

Anti-concentration of bernoulli sums

2011-01-29T02:29:37Z

Let $a_1,\ldots,a_n$ be real numbers such that $\sum_i a_i^2 =1$ and let $X_1,\ldots,X_n$ be independent, uniformly distributed, Bernoulli $\pm 1$ random variables. Define the random variable

$S:= \sum_i X_i a_i $

Are there absolute constants $\epsilon >0$ and $\delta<1$ such that for every $a_1,\ldots,a_n$

${\mathbb P} [|S| \leq \epsilon ] \leq \delta$ ?

Answer by Igor Rivin for Anti-concentration of bernoulli sums

2011-01-29T03:32:15Z

I think that the point is to observe that for $a_i$ all equal to $1/\sqrt{n},$ the statement follows from the central limit theorem (since $1/\sqrt{n}$ is precisely the needed normalizing factor). When the $a_i$ are sufficiently slowly varying, you again get a central limit theorem, and hence a similar result (if you look at Feller v 2, section XVI.5, you will see that a condition like $$\lim_{n\rightarrow \infty} {\sum a_i^3} = 0$$ is sufficient, though it is probably too strong).

Answer by George Lowther for Anti-concentration of bernoulli sums

2011-01-29T03:58:15Z

The answer to your amended question is yes. In fact, for any $\epsilon\in[0,1)$ we have $$ \mathbb{P}(\vert S\vert > \epsilon)\ge (1-\epsilon^2)^2/3. $$ So, we can take $\delta = 1-(1-\epsilon^2)^2/3$. This is the $L^0$ version of the Khintchine inequality.

To prove it, you can use $\mathbb{E}[X_iX_j^3]=0$ for $i\not=j$ and $X_i^4=X_i^2X_j^2=1$ to get $$ \begin{align} \mathbb{E}[S^4]&=\sum_ia_i^4+3\sum_{i\not=j}a_i^2a_j^2=3\left(\sum_ia_i^2\right)^2-2\sum_ia_i^4\\ &\le 3. \end{align} $$ The Paley-Zygmund inequality gives $$ \begin{align} \mathbb{P}(\vert S\vert >\epsilon)&\ge(1-\epsilon^2)^2\frac{\mathbb{E}[S^2]^2}{\mathbb{E}[S^4]}\\ &\ge(1-\epsilon^2)^2/3. \end{align} $$

This bound gives $\delta=2/3$ for $\epsilon=0$. By considering the example with $a_1=a_2=1/\sqrt{2}$ and $a_i=0$ for $i > 2$, which satisfies $\mathbb{P}(S=0)=1/2$ we see that it is necessary that $\delta\ge1/2$. In fact, a simple argument noting that the distribution is symmetric under a sign change for $X_1$ (as mentioned by Luca in the comments) shows that $\mathbb{P}(S=0)\le1/2$.

See also the paper On Khintchine inequalities with a weight, where they prove the same bound as I just did above. Also, using the optimal constants for the $L^p$ Khintchine inequality, as in Lemma 3 of that paper, gives an improved bound for $\mathbb{P}(\vert S\vert\le\epsilon)$ tending to $1-2e^{-2+\gamma}\approx0.517$ as $\epsilon$ goes to zero, which is close to optimal.

Answer by Mark Meckes for Anti-concentration of bernoulli sums

2011-01-29T14:32:34Z

Your question is part of what's called Littlewood-Offord theory, which has seen a lot of progress lately in work of Tao and Vu and of Rudelson and Vershynin. Take a look at Section 1.2 and especially Theorem 1.5 of this paper by Rudelson and Vershynin for more precise results than in George's answer. (Incidentally, that paper also contains arguments based on the central limit theorem, in the Berry-Esseen form, along the lines of what Igor suggests.)

Answer by garrit for Anti-concentration of bernoulli sums

2011-11-11T06:06:03Z

That is interesting questions... But what about anti-concentration inequality, P(|S|>a)>δ for a≥1?