Anti-concentration of bernoulli sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:27:51Z http://mathoverflow.net/feeds/question/53669 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums Anti-concentration of bernoulli sums Luca Trevisan 2011-01-29T02:29:37Z 2011-11-11T06:06:03Z <p>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</p> <p>$S:= \sum_i X_i a_i$</p> <p>Are there absolute constants $\epsilon >0$ and $\delta&lt;1$ such that for every $a_1,\ldots,a_n$</p> <p>${\mathbb P} [|S| \leq \epsilon ] \leq \delta$ ?</p> http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/53674#53674 Answer by Igor Rivin for Anti-concentration of bernoulli sums Igor Rivin 2011-01-29T03:32:15Z 2011-01-29T03:32:15Z <p>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).</p> http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/53683#53683 Answer by George Lowther for Anti-concentration of bernoulli sums George Lowther 2011-01-29T03:58:15Z 2011-01-31T00:52:56Z <p>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 <a href="http://en.wikipedia.org/w/index.php?title=Khintchine_inequality&amp;oldid=295124090" rel="nofollow">Khintchine inequality</a>.</p> <p>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]&amp;=\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\\ &amp;\le 3. \end{align} The <a href="http://en.wikipedia.org/w/index.php?title=Paley%25E2%2580%2593Zygmund_inequality&amp;oldid=366994687" rel="nofollow">Paley-Zygmund</a> inequality gives \begin{align} \mathbb{P}(\vert S\vert >\epsilon)&amp;\ge(1-\epsilon^2)^2\frac{\mathbb{E}[S^2]^2}{\mathbb{E}[S^4]}\\ &amp;\ge(1-\epsilon^2)^2/3. \end{align}</p> <p>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$.</p> <p>See also the paper <a href="http://arxiv.org/abs/0909.2586v1" rel="nofollow">On Khintchine inequalities with a weight</a>, 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.</p> http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/53719#53719 Answer by Mark Meckes for Anti-concentration of bernoulli sums Mark Meckes 2011-01-29T14:32:34Z 2011-01-29T14:32:34Z <p>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 <a href="http://www-personal.umich.edu/~romanv/papers/rv-invertibility.pdf" rel="nofollow">this paper by Rudelson and Vershynin</a> 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.)</p> http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/80660#80660 Answer by garrit for Anti-concentration of bernoulli sums garrit 2011-11-11T06:06:03Z 2011-11-11T06:06:03Z <p>That is interesting questions... But what about anti-concentration inequality, P(|S|>a)>δ for a≥1?</p>