# A Rademacher ‘root 7’ anti-concentration inequality

Let $$r_1,r_2,r_3,\dotsc$$ be an IID sequence of Rademacher random variables, so that $$\mathbb P(r_n=\pm1)=1/2$$, and $$a_1,a_2,\dotsc$$ be a real sequence with $$\sum_na_n^2=1$$. For $$S=\sum_na_nr_n$$, does the following inequality always hold? $$\mathbb P\left(\lvert S\rvert\ge1/\sqrt7\right)\ge1/2.\tag{*}\label{star}$$ Is this a known result, or conjecture?

Stated in another way, for each finite sequence $$a_1,a_2,\dotsc,a_N$$ with $$\sum_na_n^2=1$$, if we look at all $$2^N$$ sums $$\pm a_1\pm a_2\pm a_3\pm\dotsb\pm a_N$$, do we always have at least as many with absolute value at least $$1/\sqrt7$$ as with absolute value strictly less than $$1/\sqrt7$$?

Background

The statement is very similar to a conjecture of Tomaszewski, that at least as many of the $$2^N$$ sums have absolute value less than or equal to 1 as have value greater than one. This conjecture is equivalent to the concentration inequality $$\mathbb P(\lvert S\rvert\le1)\ge1/2$$, and is still unproven, other than possibly in a (not currently peer reviewed, as far as I know) paper Keller and Klein - Proof of Tomaszewski's conjecture on randomly signed sums posted on the arXiv recently.

We can also consider more general anti-concentration inequalities, which bound $$\mathbb P(\lvert S\rvert \ge x)$$ from below. For $$x=0$$ the lower bound is trivially 1 and, for $$x > 1$$, it is $$0$$. For $$0 < x < 1$$, then, as in a previous answer of mine, the Paley–Zygmund inequality can be used to obtain $$\mathbb P(\lvert S\rvert \ge x) \ge (1-x^2)^2/3,$$ but this is far from optimal. Also, for $$x=1$$, there does exist a strictly positive anti-concentration bound, as shown in the answers to another question of mine, An $L^0$ Khintchine inequality. It was shown by Oleszkiewicz, in 1996, that a (non-optimal) lower bound of $$1/10$$ applies when $$x=1$$ (in On the Stein property of Rademacher sequences) and also conjectured that the optimal bound is $$7/32$$, but this is still open as far as I am aware.

Running a Monte Carlo simulation to randomly pick the values of $$a$$ and compute the probability suggests that the optimal lower bound for $$\mathbb P(\lvert S\rvert\ge x)$$ is piecewise constant in $$x$$, so that there is only a small set of $$x$$ values at which the bound changes (specifically, $$x=0,1/\sqrt7,1/\sqrt5,1/\sqrt3,2/\sqrt6,1$$). As mentioned, for $$x=1$$ it is an open conjecture, so my question here is regarding the smallest non-trivial value for $$x$$.

Note that \eqref{star} is best possible, in the sense that it does not hold if either of the inequalities are strict and, consequently, does not hold if either the $$1/\sqrt7$$ inside the probability or the $$1/2$$ outside is increased. Considering $$a_n=1/\sqrt7$$ for $$n\le7$$, we obtain $$\mathbb P(\lvert S\rvert > 1/\sqrt7)=29/64$$, and considering $$a_n=1/\sqrt2$$ for $$n\le 2$$ gives $$\mathbb P(\lvert S\rvert\ge1/\sqrt7)=\mathbb P(\lvert S\rvert > 0)=1/2.$$ This example also shows that for any $$x \gt 0$$, the anti-concentration bound can never be better than 1/2, so \eqref{star} is also optimal in this sense, and it would immediately follow that we have optimal inequalities $$\mathbb P(\lvert S\rvert\ge x)\ge1/2 \tag{**}\label{starstar}$$ for all $$0 \lt x \le 1/\sqrt7$$. In fact, it is not difficult to prove \eqref{starstar} for $$x\le0.693/\sqrt7$$ as follows: Let $$\lVert a\rVert_\infty=\max_n\lvert a_n\rvert$$. We split into two cases,

1. $$\lVert a\rVert_\infty\ge x$$. In this case, choose $$n$$ such that $$\lvert a_n\rvert\ge x$$. Flipping the sign of $$r_n$$ does not affect the distribution of $$S$$, but if $$\lvert S\rvert < x$$ then it changes its value such that $$\lvert S\rvert\ge x$$, so that $$\mathbb P(\lvert S\rvert\ge x)\ge\mathbb P(\lvert S\rvert \lt x)$$, giving the result.
2. $$\lVert a\rVert_\infty < x$$. In this case, if we let $$\Phi(x)$$ be the standard normal cumulatiive probability function, the Berry–Esseen theorem gives $$\mathbb P(\lvert S\rvert\ge x)\ge 2\Phi(-x)-2C\lVert a\rVert_\infty \gt 2\Phi(-x)-2Cx$$ for a global constant $$C$$. We can use $$C=0.56$$ (as stated in the Wikipedia page, this was proven by Shevstova in 2010, in An improvement of convergence rate estimates in the Lyapunov theorem). Evaluating the right hand side with $$x=0.693/\sqrt7$$ gives a value greater than 1/2. QED

Finally, I mention that I have confirmed \eqref{star} numerically on a dense grid of values for $$a$$ and, by bounding the interpolation errors, should in principle lead to a (rather unsatisfactory) proof.

• What am I missing? If $a_1=\ldots=a_7=1/\sqrt 7$, isn't the sum at least $1/\sqrt 7$ in absolute value with probability 1? Jul 29 '20 at 19:35
• Yes, and $1\ge1/2$, so that example satisfies the inequality. Jul 29 '20 at 19:41
• Sorry - I thought you were saying the $(1/\sqrt 7,\ldots,1/\sqrt 7)$ example showed both inequalities are sharp, but in fact, it only shows you can't change the $1/\sqrt 7$ in the probability.(while the $1/\sqrt 2$ example shows you can't improve the 1/2). Jul 29 '20 at 19:44
• @Anthony: I edited to clarify Jul 29 '20 at 20:15
• Slightly unrelated but it seems that this (mathoverflow.net/questions/187938/lower-bound-for-prx-geq-ex/…) answer of Fedja avoids using a Barry Essen or Paley Zigmond approach for a similar problem so there might be some useful ideas there Aug 2 '20 at 2:49

## 1 Answer

Addressed in Theorem 1.3 in Dvořák and Klein - Probability mass of Rademacher sums beyond one standard deviation (not yet peer reviewed). It describes a computer program that verifies $$\Pr[\lvert S\rvert \geq 1/\sqrt{7} - \epsilon] \geq 1/2$$, with concrete $$\epsilon > 0$$. Giving it more time (polynomial in $$1/\epsilon$$), it empirically seems we may take $$\epsilon\to 0$$.

Apologizes for the unsatisfactory answer :)