Let $r_1,r_2,r_3,\ldots$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\ldots$ 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.\qquad(*) $$ Is this a known result, or conjecture?

Stated in another way, for each finite sequence $a_1,a_2,\ldots,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\cdots\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$?


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 posted on 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. It was shown by Oleszkiewicz, in 1996, that a (non-optimal) lower bound of $1/10$ applies when $x=1$ (in this paper) 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 (*) 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 (*) 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\qquad(**) $$ for all $0 \lt x \le 1/\sqrt7$. In fact, it is not difficult to prove (**) 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). 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 (*) numerically on a dense grid of values for a and, by bounding the interpolation errors, should in principle lead to a (rather unsatisfactory) proof.

  • $\begingroup$ 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? $\endgroup$ – Anthony Quas Jul 29 at 19:35
  • $\begingroup$ Yes, and $1\ge1/2$, so that example satisfies the inequality. $\endgroup$ – George Lowther Jul 29 at 19:41
  • $\begingroup$ 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). $\endgroup$ – Anthony Quas Jul 29 at 19:44
  • $\begingroup$ @Anthony: I edited to clarify $\endgroup$ – George Lowther Jul 29 at 20:15
  • $\begingroup$ 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 $\endgroup$ – Sandeep Silwal Aug 2 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.