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


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.

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

1 Answer 1


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 :)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .