23
$\begingroup$

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.

$\endgroup$
5
  • $\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

6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Now there is a complete proof due to Lawrence and Julien (yet to be published): arxiv.org/pdf/2306.07811.pdf $\endgroup$
    – ohad
    Jun 15, 2023 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.