# Probability Mass of Rademacher Sums
Beyond One Standard Deviation

Vojtěch Dvořák<EMAIL_ADDRESS>Ohad Klein<EMAIL_ADDRESS>
###### Abstract

Let $a_{1},\ldots,a_{n}\in\mathbb{R}$ satisfy $\sum_{i}a_{i}^{2}=1$, and let
$\varepsilon_{1},\ldots,\varepsilon_{n}$ be independent uniformly random $\pm$
signs and $X=\sum_{i=1}^{n}a_{i}\varepsilon_{i}$. It is conjectured that
$X=\sum_{i=1}^{n}a_{i}\varepsilon_{i}$ has $\Pr[X\geq 1]\geq 7/64$. The best
lower bound so far is $1/20$, due to Oleszkiewicz [12]. In this paper we
improve this to $\Pr[X\geq 1]\geq 6/64$.

Keywords: Rademacher sums; combinatorial probability; anti-concentration

##  1 Introduction

###  1.1 Background

Tail inequalities characterize the possible values of $\Pr[X\geq t]$ for
various thresholds $t$ and random variables $X$ with mean $0$. We consider the
case of Rademacher sums $X=\sum_{i\in[n]}a_{i}\varepsilon_{i}$ for real
numbers $a_{i}$ and independently and uniformly distributed signs
$\varepsilon_{i}\sim\\{-1,1\\}$. We further focus on lower bounds to
$\Pr[X\geq t]$.

If $t>\sqrt{\operatorname*{\mathrm{Var}}(X)}$ we may have $\Pr[X\geq t]=0$. If
$t\leq 0$, clearly $\Pr[X\geq t]\geq\frac{1}{2}$ because of the symmetry, and
if $0<t<\sqrt{\operatorname*{\mathrm{Var}}(X)}$, the Paley-Zygmund inequality
gives

$\Pr[X\geq
t]\geq\Pr[X>t]=\frac{1}{2}\Pr[X^{2}>t^{2}]\geq\frac{1}{2}(1-\frac{t^{2}}{\operatorname*{\mathrm{Var}}(X)})^{2}\frac{\operatorname*{\mathrm{Var}}(X)^{2}}{\mathbb{E}[X^{4}]}>0.$

What happens when $t=\sqrt{\operatorname*{\mathrm{Var}}{X}}$? This case was
studied in 1967 by Burkholder [3] with the conclusion that if
$C_{s}=\inf_{X}\Pr[X\geq s\sqrt{\operatorname*{\mathrm{Var}}(X)}]$, where the
infimum is taken over all Rademacher sums, then $C_{1}>0$. It was then
improved by Hitczenko and Kwapień [7] to $C_{1}\geq e^{-4}/8$, and then in
1996 by Oleszkiewicz [12] to $C_{1}\geq 1/20$. Hitczenko and Kwapień [7]
conjectured that $C_{1}=7/64$, having the tightness example
$a_{1}=\cdots=a_{6}>0$.

We point out that this problem is a natural counterpart to the Tomaszewski’s
problem [6], which in the same setting of Rademacher sums, is concerned with
the value of $\inf_{X}\Pr[|X|\leq\sqrt{\operatorname*{\mathrm{Var}}(X)}]$.
This problem attracted wide attention over the years before it was finally
settled recently by Keller and the second author [9] – the value is exactly
$\frac{1}{2}$ (and henceforth, $C_{-1}=3/4$).

###  1.2 Our results

The main result of our paper is the following.

######  Theorem 1.1.

Any Rademacher sum $X=\sum_{i}a_{i}\varepsilon_{i}$ has

$\Pr[X\geq\sqrt{\operatorname*{\mathrm{Var}}(X)}]\geq 6/64.$

This theorem improves on the previously best known bound by Oleszkiewicz [12],
who derived an analogous result with the constant $\frac{1}{20}=0.05$ instead
of our constant $\frac{6}{64}=0.09375$. We believe that our tools could be
useful in order to prove the conjectured optimal bound of $\frac{7}{64}$. We
make some progress toward this goal by handling certain difficult, near-
extremal, classes of Rademacher sums. See further Section 1.4.

While already $\Pr[X>\sqrt{\operatorname*{\mathrm{Var}}(X)}]$ might be $0$, as
demonstrated by $X=1\cdot\varepsilon_{1}$, the aforementioned proof by
Oleszkiewicz [12] in fact shows that
$\Pr[X>\sqrt{\operatorname*{\mathrm{Var}}(X)}]\geq 1/20$ whenever $X$ is not
of the form $a_{i}\varepsilon_{i}$. This bound is quite tight due to the
example $a_{1}=\cdots=a_{4}>0$ having
$\Pr[X>\sqrt{\operatorname*{\mathrm{Var}}(X)}]=1/16$. We show that this is
indeed the extremal case.

######  Theorem 1.2.

Any Rademacher sum $X=\sum_{i}a_{i}\varepsilon_{i}$ with $a_{1},a_{2}>0$ has

$\Pr[X>\sqrt{\operatorname*{\mathrm{Var}}(X)}]\geq 1/16.$

Another inequality in this vein was conjectured by Lowther [10] to be
$C_{1/\sqrt{7}}=1/4$, which is saturated by $a_{1}=\cdots=a_{7}>0$. We prove
the following slightly weaker result.

######  Theorem 1.3.

Any Rademacher sum $X=\sum_{i}a_{i}\varepsilon_{i}$ has

$\Pr[X>0.35\sqrt{\operatorname*{\mathrm{Var}}(X)}]\geq 1/4.$

In the paper of Ben-Tal, Nemirovski and Roos [1], the higher-dimensional
analogue of the $C_{1}=7/64$ problem first appeared. In this setting,
$X=\sum_{i}a_{i}\varepsilon_{i}$ with $a_{i}\in\mathbb{R}^{d}$ and we are
concerned with the probability
$P(X)\mathrel{\mathop{:}}=\Pr\big{[}\left\|{X}\right\|_{2}^{2}\geq\operatorname*{\mathbb{E}}[\left\|{X}\right\|_{2}^{2}]\big{]}$.
The best result in this framework is due to Veraar [16] who showed that
$P(X)\geq(\sqrt{12}-3)/15\approx 0.031$. We remark that the following holds.

######  Theorem 1.4.

Any $X=\sum_{i}a_{i}\varepsilon_{i}$ with $a_{i}\in\mathbb{R}^{d}$ (for any
$d\geq 1$) has

$\Pr\left[\left\|{X}\right\|_{2}^{2}\geq\operatorname*{\mathbb{E}}[\left\|{X}\right\|_{2}^{2}]\right]\geq\frac{1-\sqrt{1-1/e^{2}}}{2}>0.035.$

Interestingly, we are not aware of any example that would demonstrate that the
constant in Theorem 1.4 could not be as large as $\frac{7}{32}$ (which is the
best one could hope for, since the result does not hold for any constant
larger than that even when we only consider the case $d=1$, as commented
previously).

###  1.3 Overview of techniques

A prevalent method for understanding the distribution of Rademacher sums is to
partition their weights $\\{a_{i}\\}$ into two parts ($X=L+S$): large weights
and small weights. Such partitioning is efficient, as the Rademacher sum
having small weights is easy to analyze using quantitative versions of the
Central Limit Theorem, while the Rademacher sum having large weights can be
analyzed by enumeration over all the possibilities. In high level, this is the
approach we take, but let us dive a little further into the details.

Consider a Rademacher sum $X$ with $\operatorname*{\mathrm{Var}}(X)=1$. The
problem addressed in Theorem 1.1 concerns with lower bounding $\Pr[X\geq 1]$.
It turns out to be instructive to generalize this problem in two different
ways:

  * •

Enable a more flexible threshold $t$, and not only $t=1$.

  * •

Impose a restriction on the weights: $|a_{i}|\leq a$ for a parameter $a\leq
1$.

Denote by $G(a,t)$ the answer to this more general problem: the infimum of
$\Pr[X\geq t]$, assuming $|a_{i}|\leq a$ ($a\in(0,1]$, $t\in\mathbb{R}$).
Ultimately, Theorem 1.1 is encapsulated in the statement $G(1,1)\geq 6/64$,
but we study $G(a,t)$ for all parameters $a,t$ at once.

The crucial point is that using the decomposition of our Rademacher sum to its
large and small parts $X=L+S$, we can lower bound $G(a,t)$ by

$G(a,t)\geq\inf_{L}\operatorname*{\mathbb{E}}_{l\sim
L}[G(a^{\prime}/\sigma,(t-l)/\sigma)]$ (1)

where the infimum is taken over all possible values of $L$ induced by
decompositions $X=L+S$ (for example, if we decompose $X=L+S$ with
$L=a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}$ whenever $a_{1}+a_{2}\geq 1$ and
$L=a_{1}\varepsilon_{1}$ otherwise, the infimum is taken over all
$L=a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}$ with $a_{1}+a_{2}\geq 1$ and
with $a^{\prime}=\min(a_{2},\sqrt{1-a_{1}^{2}-a_{2}^{2})}$ and
$L=a_{1}\varepsilon_{1}$ with $a^{\prime}=\min(a_{1},1-a_{1})$), the
expectation is taken over $l$ being a realization of the random variable $L$,
$\sigma$ is the standard deviation of $S$ (that is,
$\sqrt{1-\operatorname*{\mathrm{Var}}(L)}$), and $a^{\prime}$ is an upper
bound on the weights of $S$ (whose value depends on the notion of how we
decompose $X=L+S$).

Equation (1) enables one to recursively compute lower bounds on $G(a,t)$, and
ultimately on $G(1,1)$. Roughly speaking, considering the decompositions
$X=L+S$ with $L$ containing at most the three largest weights of $X$, we
almost deduce Theorem 1.1. However, using solely this method, we run into the
following problem: In order to concretely define $G(a,t)$ through the
recursive (1), we have to propose an initial lower estimate for $G(a,t)$. The
initial estimate we use is ‘continuous’ in nature (the Berry-Esseen
inequality), and is unable to differentiate between bounds on $\Pr[X\geq t]$
and on $\Pr[X>t]$. However, there are various instances $X$, detailed in
Section 1.4, for which the stronger bound $\Pr[X>1]\geq\frac{7}{64}$ (or even
the bound $\Pr[X>1]\geq\frac{6}{64}$, that we prove) does not hold! (e.g. the
aforementioned $a_{1}=\cdots=a_{4}>0$.)

To handle these more tight cases, we take a completely different approach
toward lower bounding $\Pr[X\geq 1]$ (i.e. Theorem 1.1). That is, we _upper
bound_ $\Pr[X\in(-1,1)]$ (recall that $X$ is symmetric). To do that, we take
the advantage of the following trade-off that usually arises. The collections
$\\{a_{1},\ldots,a_{n}\\}$ that either contain large mass of their variance in
the small weights, or have their large weights very non-uniform, are harder to
describe precisely, but are nevertheless easy to analyze, since usually
stronger bounds hold for these. And the collections $\\{a_{1},\ldots,a_{n}\\}$
that contain only very small mass of their variance in the small weights and
have their large weights quite uniform are easier to describe precisely, so
despite only more tight bounds being true for these, we can derive those
bounds.

In various tight cases that arise, we commonly want to upper bound $\Pr[X\in
I]$ for some particular interval $I\subset\mathbb{R}$. To do that, we use a
chain lemma, and a few related observations.

In the chain lemma, we assume $X$ has some weights $a_{1},\ldots,a_{l}$ which
are ‘large’ compared to the length of $I$ and consider the signed sums $\pm
a_{1}\pm\ldots\pm a_{l}$ – ignoring the remaining ‘small’ weights. We then
associate the set of these $2^{l}$ signed sums with a hypercube graph in a
natural way and then use a famous result of Erdős [5] to show that these sums
are not very tightly concentrated. That in turn implies an upper bound on
$\Pr[X\in I]$.

Occasionally, we have to consider the case when $I$ is a very short interval
(much smaller than $(-1,1)$). In such a case we divide the small weights into
disjoint parts (a method introduced by Montgomery-Smith [11]), so that each
part has a substantial probability to be large compared to $I$, and apply the
chain lemma on these ‘large’ parts to deduce that $\Pr[X\in I]$ is small
enough.

###  1.4 Difficult cases

As described in the previous subsection, similarly to Tomaszewski’s problem
[9], the particular difficulty we are facing when trying to prove the
conjecture $C_{1}=7/64$, are the cases when $\Pr[X>1]<7/64$ despite $\Pr[X\geq
1]\geq 7/64$ (and their ‘neighborhoods’, i.e. the collections with the few
largest weights being roughly of the same sizes as in these cases). Notably,
we have

  * •

for $a_{1}=1$, $\Pr[X>1]=0$;

  * •

for $a_{1}=\ldots=a_{4}=\frac{1}{2}$, $\Pr[X>1]=\frac{1}{16}$;

  * •

for $a_{1}=\ldots=a_{9}=\frac{1}{3}$, $\Pr[X>1]=\frac{23}{256}\approx
0.0898\ldots<\frac{6}{64}$;

  * •

for $a_{1}=\frac{2}{3},a_{2}=\ldots=a_{6}=\frac{1}{3}$,
$\Pr[X>1]=\frac{6}{64}$;

  * •

for $a_{1}=a_{2}=\frac{1}{2},a_{3}=\ldots=a_{10}=\frac{1}{4}$,
$\Pr[X>1]=\frac{55}{512}<\frac{7}{64}$.

We have to deal with the first three cases even when proving our bound of
$6/64$, and the last two cases are further hurdles on the way to the optimal
bound.

In our proof of the $6/64$ bound, big part of the argument is spent dealing
with a subcase presented in Section 4.1.4, which corresponds to the
collections ‘close to’ the third case from above (which is the most intricate
of the first three ‘barriers’).

In Section 6, we discuss these difficulties in more detail and make progress
toward proving the $7/64$ bound, by proving it for families corresponding to
the ‘neighbourhoods’ of all the cases above except the third one.

###  1.5 Organization

In Section 2, we introduce notation, and define a certain type of a useful
random process. In Section 3, we describe our main tools and prove Theorem
1.3. We then use these tools in Section 4 to prove Theorem 1.1, the main
result of the paper. Section 5 contains the proof of Theorem 1.2. In Section
6, we discuss the deficiency of our $6/64$ proof and propose how to advance
toward $7/64$, proving the result in two out of three ‘difficult’ cases. In
Section 7, we discuss the high dimensional version of the problem as well as
of the problem of Tomaszewski and prove Theorem 1.4. Finally in Section 8, we
summarize the open problems arising in the paper.

Some of the more technical proofs from various parts of the paper are in
Appendix A and Appendix B.

##  2 Background and definitions

In this section, we describe our setting, notation and assumptions that we are
working with.

Throughout, we will consider $X=\sum_{i=1}^{n}a_{i}\varepsilon_{i}$, where
$\varepsilon_{i}$ are independent Rademacher random variables (i.e.
independent random variables such that
$\Pr\big{[}\varepsilon_{i}=+1\big{]}=\Pr\big{[}\varepsilon_{i}=-1\big{]}=\frac{1}{2}$)
and $a_{i}$ are real numbers with $\sum_{i=1}^{n}a_{i}^{2}=1$. Moreover, we
will always, without loss of generality, assume that

$a_{1}\geq a_{2}\geq\ldots\geq a_{n}>0.$

Sometimes, we will work with variables $\\{b_{i}\\}$ or $\\{c_{i}\\}$ instead
of $\\{a_{i}\\}$. For these, we do not assume any conditions on their ordering
unless so stated.

At some points, we will also write $\mathbf{a}$ to denote
$\\{a_{1},\ldots,a_{n}\\}$.

Our central aim will be to lower bound

$\Pr\big{[}X\geq 1\big{]}=\frac{1}{2}\Pr\big{[}|X|\geq 1\big{]}.$ (2)

At some points, we will work with $\Pr\big{[}X\geq 1\big{]}$, while at other
points, we will work with $\Pr\big{[}|X|\geq 1\big{]}$. As expressed by (2),
working with these two forms is of course equivalent and the entire proof
could be rewritten using just one of these. We use both quantities in order to
streamline the proof.

The function $D(a,x):(0,1]\times\mathbb{R}\to\mathbb{R}$ appears repeatedly
throughout the proof. This is a particular function that we construct in
subsection 3.3 and it has a property that for any $a\in(0,1],x\in\mathbb{R}$,
if we have $a_{1}\leq a$, then $\Pr\big{[}X\geq x\big{]}\geq D(a,x)$. While
its computation is computer-aided, we emphasize that by writing ‘$D$’, we
always refer to its exact value, and not to its approximation.

##  3 Tools

###  3.1 Stopped random walks and chain argument

We start with an observation (following trivially from a well known result of
Erdős [5]) which we will use repeatedly.

######  Observation 3.1.

Let $b_{1}\geq b_{2}\geq\ldots\geq b_{t}>0$ be such that
$b_{t-k+1}+\ldots+b_{t}\geq\alpha$ for some $\alpha>0$ and $0<k\leq t$. Then,
for any $x$ and any $b_{t+1},\ldots,b_{s}$, we have

$\Pr\big{[}\sum_{i=1}^{s}b_{i}\varepsilon_{i}\in\left(x-\alpha,x+\alpha\right)\big{]}\leq
f(k,t)/2^{t}$

where $f(k,t)$ denotes the sum of $k$ largest binomial coefficients of the
form $\binom{t}{i}$ for some $i,\ 0\leq i\leq t$.

###### Proof.

If the probability was more than $f(k,t)/2^{t}$ for some fixed $x$, then in
particular we can choose signs
$\varepsilon_{t+1}=\varepsilon_{t+1}^{\prime},\ldots,\varepsilon_{s}=\varepsilon_{s}^{\prime}$
in such a way that at least $f(k,t)+1$ of the sums

$\pm b_{1}\pm\ldots\pm
b_{t}+b_{t+1}\varepsilon_{t+1}^{\prime}+\ldots+b_{s}\varepsilon_{s}^{\prime}$

are within less than $2\alpha$ of each other. Let

$T=\\{\pm b_{1}\pm\ldots\pm
b_{t}+b_{t+1}\varepsilon_{t+1}^{\prime}+\ldots+b_{s}\varepsilon_{s}^{\prime}\\}.$

Consider the bijection $g:T\rightarrow Q_{t}\simeq\\{\pm 1\\}^{t}$ given by

$b_{1}\varepsilon_{1}+\ldots+b_{t}\varepsilon_{t}+b_{t+1}\varepsilon_{t+1}^{\prime}+\ldots+b_{s}\varepsilon_{s}^{\prime}\rightarrow(\varepsilon_{1},\ldots,\varepsilon_{t}).$

Let $S\subset T$ be the set of $f(k,t)+1$ elements of $T$ that are all within
$2\alpha$ of each other. Then by the result of Erdős [5, Theorem 5], $g(S)$
contains an chain of length at least $k$. But that contradicts the assumption
that $b_{t-k+1}+\ldots+b_{t}\geq\alpha$. ∎

Some times, we will only check the stronger condition that (in the cases
$k=2,3$) no two out of the sums $x_{0}\pm b_{1}\pm\ldots\pm b_{k}$ are within
less than $2\delta$ of each other, which in particular implies no two hit any
interval of the form $\left(x-\delta,x+\delta\right)$. For the special cases
we need, we will use the following two straightforward observations to verify
that.

######  Observation 3.2.

Fix $\delta>0$ and $b_{1},b_{2}\geq\delta$ such that
$|b_{1}-b_{2}|\geq\delta$. Then for any $x$ and any $b_{3},\ldots,b_{l}$, we
have

$\Pr\big{[}\sum_{i=1}^{l}b_{i}\varepsilon_{i}\in\left(x-\delta,x+\delta\right)\big{]}\leq\frac{1}{4}.$

###### Proof.

If the probability was more than $\frac{1}{4}$ for some fixed $x$, then in
particular we can choose signs
$\varepsilon_{3}=\varepsilon_{3}^{\prime},\ldots,\varepsilon_{l}=\varepsilon_{l}^{\prime}$
in such a way that at least two of the four sums

$\pm b_{1}\pm
b_{2}+b_{3}\varepsilon_{3}^{\prime}+\ldots+b_{l}\varepsilon_{l}^{\prime}$

are within less than $2\delta$ of each other. Looking at differences of this
set, it can only happen if the set

$D=\\{b_{1}+b_{2},\,b_{1},\,b_{2},\,|b_{1}-b_{2}|\\}$

contains some element smaller than $\delta$, and our assumptions guarantee
that can not happen. ∎

######  Observation 3.3.

Fix $\delta>0$ and $c_{1}\geq c_{2}\geq c_{3}\geq\delta$ such that
$c_{1}-c_{2},c_{2}-c_{3}\geq\delta$, $|c_{1}-c_{2}-c_{3}|\geq\delta$. Then for
any $x$ and any $c_{4},\ldots,c_{m}$, we have

$\Pr\big{[}\sum_{i=1}^{m}c_{i}\varepsilon_{i}\in\left(x-\delta,x+\delta\right)\big{]}\leq\frac{1}{8}.$

###### Proof.

If the probability was more than $\frac{1}{8}$ for some fixed $x$, then in
particular we can choose signs
$\varepsilon_{4}=\varepsilon_{4}^{\prime},\ldots,\varepsilon_{m}=\varepsilon_{m}^{\prime}$
in such a way that at least two of the eight sums

$\pm c_{1}\pm c_{2}\pm
c_{3}+c_{4}\varepsilon_{4}^{\prime}+\ldots+c_{m}\varepsilon_{m}^{\prime}$

are within less than $2\delta$ of each other. Looking at differences of this
set, it can only happen if the set

$D=\\{c_{1},\,c_{2},\,c_{3},\,c_{1}\pm c_{2},\,c_{1}\pm c_{3},\,c_{2}\pm
c_{3},\,c_{1}+c_{2}\pm c_{3},\,c_{1}-c_{2}+c_{3},\,|c_{1}-c_{2}-c_{3}|\\}$

contains some element smaller than $\delta$; our assumptions guarantee it is
impossible. ∎

In the easy cases, we are already given enough large weights as a part of our
collection $\\{a_{i}\\}$ and can use these weights in the anti-concentration
observations above. But if that is not true and we instead have a lot of very
small weights, we can ‘generate’ larger weights from them, as described in the
subsection that follows.

###  3.2 The random process $W(S;x)$ and its success probability

For a set of real numbers $S=\\{d_{1},\ldots,d_{n}\\}$ and a real number
$x>0$, we denote by $W(S;x)$ (or by $W(d_{1},\ldots,d_{n};x)$) the following
random process. We first fix a permutation $(i_{1},\ldots,i_{n})$ of
$\\{1,\ldots,n\\}$ which maximizes the probability that the process is
successful (what it means for this process to be successful will be defined in
due course). Next, we set $W_{0}=0$. After choosing $W_{j}$ for some $j<n$, if
$|W_{j}|\geq x$, we set

$W_{j+1}=\ldots=W_{n}=W_{j}.$

While if $|W_{j}|<x$, we let $\varepsilon_{i_{j+1}}$ be Rademacher random
variable independent of the previous part of the process, and set

$W_{j+1}=W_{j}+d_{i_{j+1}}\varepsilon_{i_{j+1}}.$

We denote by $r(S;x)$ (or by $r(d_{1},\ldots,d_{n};x)$) the final value of
this process, i.e. $W_{n}$. We call it successful if $|r(S;x)|\geq x$, and
unsuccessful otherwise.

We denote by $p(S;x)$ (or by $p(d_{1},\ldots,d_{n};x)$) the probability that
the process is successful. In particular, if we have $|d_{i}|\geq x$ for any
$i\in\\{1,\ldots,n\\}$, clearly the corresponding process will always be
successful because of our condition on ordering.

The following lemma is crucial for us when working with such random processes.

######  Lemma 3.4.

Assume we have positive reals $b_{1},\ldots,b_{k}$ such that
$\sum_{i=1}^{k}b_{i}^{2}\geq c\alpha^{2}$ for some fixed $c>1$ and fixed
$\alpha>0$. Then

$p(b_{1},\ldots,b_{k};\alpha)\geq\frac{c-1}{c+3}.$

Moreover, if for some $\eta\in(0,1)$, we have
$b_{1},\ldots,b_{k}\in(0,\eta\alpha]\cup[\alpha,\infty)$, then

$p(b_{1},\ldots,b_{k};\alpha)\geq\frac{c-1}{c+\eta^{2}+2\eta}.$

###### Proof.

If any term out of $b_{1},\ldots,b_{k}$ has size at least $\alpha$, then
clearly $p(b_{1},\ldots,b_{k};\alpha)=1$. So further assume none of the terms
has size at least $\alpha$.

Run the random process $W(b_{1},\ldots,b_{k};\alpha)$. Without loss of
generality (and for notational convenience), we can assume that the ordering
$b_{1},\ldots,b_{k}$ maximizes the probability that the process is successful.
We define the stopping time $T$ as follows. Let $T$ be the first time $i$ such
that $|W_{i}|\geq\alpha$ if this time is at most $k$, and let $T=k$ otherwise.
Let $p=p(b_{1},\ldots,b_{k};\alpha)$ be the probability that the process
$W(b_{1},..,b_{k};\alpha)$ is successful, i.e. that it hits absolute value at
least $\alpha$.

Now we will lower and upper bound $\mathbb{E}\big{[}W_{T}^{2}\big{]}$.

Clearly $|W_{T}|\leq 2\alpha$ (as every term has size at most $\alpha$ and $T$
is the first time we reach absolute value at least $\alpha$), and
$|W_{T}|\leq\alpha$ in the case when we never hit absolute value at least
$\alpha$. This gives

$\mathbb{E}\big{[}W_{T}^{2}\big{]}\leq 4p\alpha^{2}+(1-p)\alpha^{2}.$ (3)

But also, writing $A=b_{1}\varepsilon_{1}+\ldots+b_{T}\varepsilon_{T}$ and
$B=b_{T+1}\varepsilon_{T+1}+\ldots+b_{k}\varepsilon_{k}$ (setting $B=0$ if
$T=k$), we collect the following easy observations. Firstly

$\mathbb{E}\big{[}AB\big{]}=\sum_{T_{0},x}\Pr\big{[}T=T_{0},A=x\big{]}\mathbb{E}\big{[}AB|T=T_{0},A=x\big{]}=0,$
(4)

since for any $T_{0},x$, we have

$\mathbb{E}\big{[}AB|T=T_{0},A=x\big{]}=x\mathbb{E}\big{[}b_{T_{0}+1}\varepsilon_{T_{0}+1}+\ldots+b_{k}\varepsilon_{k}\big{]}=0.$

Furthermore, noting that if $T=k$, then $B=0$, we obtain

$\mathbb{E}\big{[}B^{2}\big{]}=\sum_{i=1}^{k-1}\Pr\big{[}T=i\big{]}\mathbb{E}\big{[}B^{2}|T=i\big{]}=\sum_{i=1}^{k-1}\Pr\big{[}T=i\big{]}\big{(}\sum\nolimits_{j=i+1}^{k}b_{j}^{2}\big{)}\leq
p\sum_{i=1}^{k}b_{i}^{2}.$ (5)

Using (4) we conclude

$\sum_{i=1}^{k}b_{i}^{2}=\mathbb{E}\big{[}(A+B)^{2}\big{]}=\mathbb{E}\big{[}A^{2}\big{]}+\mathbb{E}\big{[}B^{2}\big{]}+2\mathbb{E}\big{[}AB\big{]}=\mathbb{E}\big{[}A^{2}\big{]}+\mathbb{E}\big{[}B^{2}\big{]}.$
(6)

Overall, combining (5) and (6) we conclude

$\mathbb{E}\big{[}A^{2}\big{]}\geq(1-p)\sum_{i=1}^{k}b_{i}^{2}\geq(1-p)c\alpha^{2}.$
(7)

Combining (3) and (7), we obtain

$(1-p)c\alpha^{2}\leq\mathbb{E}\big{[}W_{T}^{2}\big{]}\leq
4p\alpha^{2}+(1-p)\alpha^{2}.$

Rearranging gives the first result.

For the second result, just note that with our additional condition
$b_{1},\ldots,b_{k}\in(0,\eta\alpha]$, we can replace the inequality

$\mathbb{E}\big{[}W_{T}^{2}\big{]}\leq 4p\alpha^{2}+(1-p)\alpha^{2}$

by the stronger inequality

$\mathbb{E}\big{[}W_{T}^{2}\big{]}\leq
p(1+\eta)^{2}\alpha^{2}+(1-p)\alpha^{2},$

and conclude in exactly the same way as before. ∎

###  3.3 Dynamic Programming bound

Denote by $\widetilde{G}(a_{1},x)$ the quantity $\inf_{X}\Pr[X>x]$ where the
infimum is taken over all Rademacher sums $X$ with
$\operatorname*{\mathrm{Var}}(X)=1$, and whose largest weight is at most
$a_{1}$.

For the proof, it is useful to understand the function $\widetilde{G}$.
Evaluating the function $\widetilde{G}(a_{1},x)$ is in general harder than the
problem we are concerned with in Theorem 1.1; the latter is, nonrigorously,
encapsulated in $\widetilde{G}(1,1-\epsilon)$.

The goal of the dynamic-programming approach is to derive a lower bound on
$\widetilde{G}$ by first obtaining some lower bound on
$\widetilde{G}(a_{1},x)$ for many values of $a_{1},x$, and then using an
iterative procedure to improve this bound further. The key tool enabling us to
iterate is elimination of the largest weight (see Section 3.4 for more details
about elimination).

####  3.3.1 Prawitz’s smoothing Inequality

We will use a smoothing inequality of Prawitz [15]. This inequality is a
useful tool, providing bounds on the values of the cumulative distribution
function of a random variable, in terms of a partial information regarding its
characteristic function. Specifically, given the characteristic function of a
random variable, it is possible to determine its distribution via the Gil-
Pelaez formula. In the case of a Rademacher sum
$X=\sum_{i}a_{i}\varepsilon_{i}$, we have the characteristic function
$\varphi_{X}(t)=\prod_{i}\cos(a_{i}t)$. Assuming that we know the largest
weight $a_{1}$, it is possible to estimate the value of $\varphi_{X}(t)$ for
$t\ll 1/a_{1}$. Although for $t\gg 1/a_{1}$, we have no information regarding
$\varphi_{X}(t)$, Prawitz’ inequality is still capable of providing a decent
estimate for the cumulative distribution function of $X$.

While the inequality is applicable to all random variables, it was shown in
[9] that its specialization to Rademacher sums gives tighter estimates.

Prawitz’ bound gives a lower bound on $\widetilde{G}(a_{1},x)$, for all
parameters $q\in[0,1],\ T>0$:

$\forall q\in[0,1],\,T>0\colon\qquad\widetilde{G}(a_{1},x)\geq
F(a_{1},x,T,q).$ (8)

Specifically, a formula for $F$ may be derived from [9, Proposition 4.2]
(which is derived from [15]):

$\displaystyle\begin{split}F(a,x,T,q)=1/2&-\int_{0}^{q}\left|k(u,x,T)\right|g(Tu,a)\mathrm{d}{u}-\int_{q}^{1}\left|k(u,x,T)\right|h(Tu,a)\mathrm{d}{u}\\\
&-\int_{0}^{q}k(u,x,T)\exp(-(Tu)^{2}/2)\mathrm{d}{u},\end{split}$ (9)

where111$k$ can be smoothly continued to the range $u\in\\{0,1\\}$ by setting
$k(0,x,T)=1+Tx/\pi$ and $k(1,x,T)=0$. $k(u,x,T)=\frac{(1-u)\sin(\pi
u+Tux)}{\sin(\pi u)}+\frac{\sin(Tux)}{\pi}$,

$g(v,a)=\begin{cases}\exp(-v^{2}/2)-\cos(av)^{1/a^{2}},&av\leq\frac{\pi}{2}\\\
\exp(-v^{2}/2)+1,&\mathrm{otherwise}\end{cases},\quad
h(v,a)=\begin{cases}\exp(-v^{2}/2),&av\leq\theta\\\
(-\cos(av))^{1/a^{2}},&\theta\leq av\leq\pi\\\
1,&\mathrm{otherwise}\end{cases},$

$Z\sim N(0,1)$ is a standard Gaussian and $\theta=1.778\pm 10^{-4}$ is the
unique solution of $\exp(-\theta^{2}/2)=-\cos(\theta)$ in the interval
$[0,\pi]$. We note that $F(a,x,T,q)$ is a function (weakly) decreasing in $a$.

####  3.3.2 Recursion

Note that as in (1), by considering the two values that the sign of the
largest weight can take (see subsection 3.4 for more details), we have

$\widetilde{G}(a_{1},x)\geq\frac{1}{2}\inf_{a\in(0,a_{1}]}\left(\widetilde{G}\left(\frac{a}{\sqrt{1-a^{2}}},\frac{x-a}{\sqrt{1-a^{2}}}\right)+\widetilde{G}\left(\frac{a}{\sqrt{1-a^{2}}},\frac{x+a}{\sqrt{1-a^{2}}}\right)\right).$
(10)

Hence, $\widetilde{G}$ is lower bounded by the lowest function satisfying both
inequalities (8), (10). Computationally, to obtain a concrete lower bound on
$\widetilde{G}$, we iteratively define the functions

${D_{i}}\colon{(0,1)\times\mathbb{R}}\to{\mathbb{R}}$

by $D_{0}(a_{1},x)=\max(F(a_{1},x),\ \mathbbm{1}\\{x<0\\}/2)$ with
$F(a_{1},x)=\sup_{T,q}\\{F(a_{1},x,T,q)\\}$ and

$D_{i+1}(a_{1},x)=\max\Big{(}D_{i}(a_{1},x),\frac{1}{2}\inf_{a\in(0,a_{1}]}\Big{(}D_{i}\Big{(}\frac{a}{\sqrt{1-a^{2}}},\frac{x-a}{\sqrt{1-a^{2}}}\Big{)}+D_{i}\Big{(}\frac{a}{\sqrt{1-a^{2}}},\frac{x+a}{\sqrt{1-a^{2}}}\Big{)}\Big{)}\Big{)},$
(11)

and observe that $\widetilde{G}(a_{1},x)\geq D_{i}(a_{1},x)$ for all $i$.
Choosing a large $I$ ($I=10$ suffices) and writing

$D(a_{1},x)=D_{I}(a_{1},x)$

we derive

$\forall X\in\mathcal{X}\colon(X=\sum b_{i}\varepsilon_{i}\wedge|b_{i}|\leq
a_{1})\implies\Pr[X>x]\geq D(a_{1},x).$ (12)

Note that $D$ is a function depending on two continuous variables, which
cannot be stored programmatically. We compute $D_{i}(a_{1},x)$ for
$a_{1}\in[0,1]$ and $x\in[-3,3]$ with granularity of $\delta=1/400$ ($a_{1}$
starting from $0$ and $x$ starting from $-3$). Correspondingly, we replace
(11) with a variant that feeds $D_{i+1}$ with arguments rounded up (to a
multiple of $\delta$), hence underestimating $D_{i+1}$; This enables
considering a finite set of $a\in[0,a_{1}]$ in the infimum at (11). We apply
this rounding-up to both the $\frac{a}{\sqrt{1-a^{2}}}$ and the $\frac{x\pm
a}{\sqrt{1-a^{2}}}$ arguments. Moreover, in any computation of $D(a_{1},x)$ we
round the arguments up to multiples of $\delta$. When $x<-3$ we round $x$ to
$-3$, and when $x\geq 3$ we round $x$ to $\infty$ and set $D(a_{1},\infty)=0$.
This results in a dynamic-programming method for computing $D_{i}(a_{1},x)$.

Our implementation of this computation can be found at [4].

##### Several concrete values.

Along the paper, we use the following lower bounds for values of $D$, derived
by the described computation.

$\displaystyle D(0.35,0.35)>\frac{1}{4},\qquad$ $\displaystyle
D(0.3,1)>\frac{3}{32},$ (13) $\displaystyle
D(0.3/\sqrt{0.51},0.3/\sqrt{0.51})>\frac{3}{16},\qquad$ $\displaystyle
D(0.4,1)>\frac{1}{12},$ $\displaystyle D(0.5,0.5)>\frac{1}{6},\qquad$
$\displaystyle D(0.34,1.42)>0.04,$ $\displaystyle D(0.43,1.42)>0.03,\qquad$
$\displaystyle D(0.51,1.01)=\frac{1}{16}.$

Note that $D(0.51,1.01)=1/16$ is a precise value (unlike the other values
mentioned for which we just have lower bounds). On the one hand, we clearly
see that $D(0.51,1.01)\leq 1/16$, as saturated by the weights
$a_{1}=\ldots=a_{4}=1/2$. On the other hand, to derive $D(0.51,1.01)\geq
1/16$, it is crucial that we set
$D_{0}(a_{1},x)=\max(F(a_{1},x),\mathbbm{1}\\{x<0\\}/2)$ instead of just using
$F(a_{1},x)$. Our iterative procedure and the lower bounds on $F(a_{1},x)$ are
then enough to prove $D(0.51,1.01)\geq 1/16$.

##### Precision.

As described, the lower bound $D(a,x)$ we numerically get for
$\widetilde{G}(a,x)$ is precise. The only detail disregarded so far is the
computation of $F(a_{1},x)$. Programmatically we replace $F(a_{1},x)$ by
$F(a_{1},x,\pi/a_{1},0.5)$, that is, we do not compute the maximum of
$F(a_{1},x,T,q)$ over all values of $T,q$, but set $T=\pi/a_{1}$ and $q=0.5$.
Since we use $F(a_{1},x)$ as a lower bound, this underestimation of
$F(a_{1},x)$ is valid. We further note that this choice of $T,q$ simplifies
the first integrand in $F(a_{1},x,T,q)$ to be continuous (specifically,
$g(v,a)$ is applied only when $av\leq\pi/2$). Finally, to numerically estimate
the integrals appearing in the definition of $F(a,x,T,q)$ we take two
approaches.

In the first approach we compute the integrals appearing in (9) verbatim by
using the standard Python integrator scipy.integrate.quad, and check that the
integrator estimates that its error is well below some constant ($0.01$) that
we discount from $F(a,x,T,q)$. We also split the domains of integration so
that the integrands are smooth in each subdomain. This evaluation of $F$ is
simple, but requires relying on the accuracy of scipy.integrate.quad.

In the second approach we compute the integrals with the trapezoid rule, using
explicit bounds $B$ on the derivatives of the integrands (more accurately, we
use that these are $B$-lipschitz functions), to get an explicit estimation of
the integrals, together with a provable error estimates. The bounds $B$ are
computed in [9, Appendix B.2].

While the first approach is neat and simple, the second approach is
transparent and reviewable. The accompanied code is available at [4].

###  3.4 Elimination

Elimination is the process of replacing a probabilistic inequality in
$X=\sum_{i=1}^{n}a_{i}\varepsilon_{i}$, by an inequality involving
$Z=\sum_{i=m}^{n}a_{i}\varepsilon_{i}$ with $m>1$. For example, the inequality

$\Pr[X\geq 1]\geq 3/32$

is equivalent to the following inequality, which involves
$Z=\sum_{i=2}^{n}a_{i}\epsilon_{i}$ (i.e. $m=2$),

$\Pr[Z\geq 1-a_{1}]+\Pr[Z\geq 1+a_{1}]\geq 3/16.$

via the law of total probability. A more elaborate derivation can be found at
[9, Lemma 2.1].

###  3.5 A $1/\sqrt{7}$-type inequality

Lowther [10] conjectured that $\Pr[|X|\geq 1/\sqrt{7}]\geq 1/2$ is true for
all Rademacher sums $X$ with $\operatorname*{\mathrm{Var}}(X)=1$. In the proof
of Theorem 1.1 we make use of Theorem 1.3, i.e. $\Pr[|X|>0.35]\geq 1/2$, which
we henceforth prove.

We split into two cases. If $a_{1}>0.35$, and
$\varepsilon^{\prime}=(-\varepsilon_{1},\varepsilon_{2},\ldots,\varepsilon_{n})$,
then at least one of $X(\varepsilon)$ and $X(\varepsilon^{\prime})$ has
absolute value more than $a_{1}$, hence $\Pr[|X|>0.35]\geq 1/2$. If $a_{1}\leq
0.35$, then we conclude using (13) since

$D(0.35,0.35)>1/4.$

##  4 Proof of $\Pr[X\geq 1]\geq 3/32$

In this section we show that for any Rademacher sum $X$ with
$\operatorname*{\mathrm{Var}}(X)=1$,

$\Pr[X\geq 1]\geq 3/32,$ (14)

that is, Theorem 1.1. The proof splits into two main cases - the case when
$a_{1}+a_{2}+a_{3}\leq 1$ and the case when $a_{1}+a_{2}+a_{3}>1$.

In the case $a_{1}+a_{2}+a_{3}\leq 1$, the tools we have developed in
subsections 3.3 and 3.4 enable us to handle most of the subcases.
Nevertheless, as discussed before, one can not hope for these tools to work in
the subcase $(a_{1},a_{2},a_{3})\approx(\frac{1}{3},\frac{1}{3},\frac{1}{3})$
and $a_{1}+a_{2}+a_{3}\leq 1$. Thus, we spend majority of this subsection
dealing with the subcase $a_{3}\geq 0.325$ and $a_{1}+a_{2}+a_{3}\leq 1$. To
do that, we use the tools developed in subsection 3.1. Our strategy is to show
that the family of such collections $\\{a_{i}\\}$ with $a_{3}\geq 0.325$ and
$a_{1}+a_{2}+a_{3}\leq 1$ is contained in the union of several subfamilies,
for each of which we can obtain the desired bound.

In the case $a_{1}+a_{2}+a_{3}>1$, the proof is less lengthy. We divide it
into several subcases and use the tools from subsections 3.3 and 3.4 and
crucially also Theorem 1.3, to resolve these cases.

###  4.1 Case $a_{1}+a_{2}+a_{3}\leq 1$

####  4.1.1 Subcase $a_{1}\leq 0.3$

Using (13) we have

$D(0.3,1)>3/32$

implying the assertion (14) through (12).

####  4.1.2 Subcase $a_{1}\geq 0.7$

Using elimination, in order to deduce (14) regarding
$X=\sum_{i=1}^{n}a_{i}\varepsilon_{i}$ it suffices to check

$\Pr\left[X^{\prime}\geq\frac{1-a_{1}}{\sqrt{1-a_{1}^{2}}}\right]\geq 3/16$
(15)

with
$X^{\prime}=\frac{1}{\sqrt{1-a_{1}^{2}}}\sum_{i=2}^{n}a_{i}\varepsilon_{i}$
the $a_{1}$-eliminated version of $X$. Using (13) we deduce (15) from

$D(0.3/\sqrt{0.51},0.3/\sqrt{0.51})>3/16,$

since $a_{1}+a_{2}\leq 1$. This argument does not rely on
$a_{1}+a_{2}+a_{3}\leq 1$, but only assumes $a_{1}+a_{2}\leq 1$ (and
$a_{1}\geq 0.7$). This is used in Section 4.2.2.

####  4.1.3 Subcase $a_{3}\leq 0.325$ and $a_{1}\in[0.3,0.7]$

Under the conditions $a_{1}\geq 0.3$ and $a_{3}\leq 0.325$ (and
$a_{2}\in[a_{3},a_{1}]$), denote $\sigma_{2}=\sqrt{1-a_{1}^{2}-a_{2}^{2}}$,
and note that $a=\min(1-a_{1}-a_{2},a_{2},0.325)$ is an upper bound on
$a_{3}$. We show in Appendix A.1 that

$\operatorname*{\mathbb{E}}_{\varepsilon\in\left\\{-1,1\right\\}^{2}}\left[D\left(\frac{a}{\sigma_{2}},\frac{1+a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}}{\sigma_{2}}\right)\right]\geq
3/32,$ (16)

verifying (14) in this case, via elimination of $a_{1},a_{2}$.

####  4.1.4 Subcase $a_{3}\geq 0.325$

Let $Y=\sum_{i=4}^{n}a_{i}\varepsilon_{i}$ and denote:

$\begin{gathered}q_{1}=\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}-a_{3}\big{]},\qquad
q_{2}=\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}+a_{3}\big{]},\\\ q_{3}=\Pr\big{[}|Y|\geq
1-a_{1}+a_{2}-a_{3}\big{]},\qquad q_{4}=\Pr\big{[}|Y|\geq
1+a_{1}-a_{2}-a_{3}\big{]},\\\ q_{5}=\Pr\big{[}|Y|\geq
1-a_{1}+a_{2}+a_{3}\big{]},\qquad q_{6}=\Pr\big{[}|Y|\geq
1+a_{1}-a_{2}+a_{3}\big{]},\\\ q_{7}=\Pr\big{[}|Y|\geq
1+a_{1}+a_{2}-a_{3}\big{]},\qquad q_{8}=\Pr\big{[}|Y|\geq
1+a_{1}+a_{2}+a_{3}\big{]}.\end{gathered}$

Then using elimination, we have $\Pr[X\geq
1]=\frac{1}{16}(q_{1}+\ldots+q_{8})$. Hence we are required to show

$q_{1}+\ldots+q_{8}\geq 3/2.$ (17)

The key lemma which lets us handle this case, is the following.

######  Lemma 4.1.

Let $\mathcal{A}$ be the family of the collections
$\mathbf{a}=(a_{1},\ldots,a_{n})$ with $n\geq 4$, $a_{1}\geq\ldots\geq
a_{n}>0$, $\sum_{i=1}^{n}a_{i}^{2}=1$, $a_{1}+a_{2}+a_{3}\leq 1$ and
$a_{3}\geq 0.325$. Then
$\mathcal{A}=\mathcal{A}_{1}\cup\mathcal{A}_{2}\cup\mathcal{A}_{3}$, where
$\mathcal{A}_{1},\mathcal{A}_{2},\mathcal{A}_{3}$ are the subsets of
$\mathcal{A}$ characterized by the following additional conditions:

  * •

$\mathcal{A}_{1}$: $a_{4}\leq 7/40$,

  * •

$\mathcal{A}_{2}$: $q_{1}\geq\frac{793}{1024}$,

  * •

$\mathcal{A}_{3}$: $q_{2},q_{3}\geq\frac{37}{128}$.

###### Proof.

Firstly, if we had $a_{1}+a_{2}+a_{3}=1$, then clearly $q_{1}=1$. So further
consider only the case $a_{1}+a_{2}+a_{3}<1$. Write
$a_{3}=\frac{1}{3}-\delta$, and assume that $a_{1}+a_{2}+a_{3}<1$ and
$0<\delta\leq\frac{1}{120}$ (which is equivalent to $a_{3}\geq 0.325$). Note
that

$1-a_{1}-a_{2}-a_{3}\leq 1-3a_{3}=3\delta,$ (18)

and that

$1-a_{1}-a_{2}+a_{3},1-a_{1}+a_{2}-a_{3}\leq 1-a_{3}=\frac{2}{3}+\delta.$ (19)

If $a_{4}\leq 21\delta\leq 7/40$, we have $\mathbf{a}\in\mathcal{A}_{1}$. So
further assume that $a_{4}\geq 21\delta$, in which case we have to show that
$\mathbf{a}\in\mathcal{A}_{2}\cup\mathcal{A}_{3}$.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}-a_{3}$ (if
$a_{n}\geq 1-a_{1}-a_{2}-a_{3}$, set $k=n+1$). Note that $k\geq 5$, since

$a_{4}\geq 21\delta>3\delta\geq 1-a_{1}-a_{2}-a_{3},$

where the last inequality follows by (18).

######  Claim 4.2.

If $\sum_{i=k}^{n}a_{i}^{2}\geq 450\delta^{2}$, then
$\mathbf{a}\in\mathcal{A}_{2}$.

###### Proof of Claim 4.2.

Note that $a_{k},\ldots,a_{n}<3\delta$. We can find disjoint subsets
$S,T_{1},\ldots,T_{4}$ of $\\{a_{k},\ldots,a_{n}\\}$ with the following
properties. We have

$234\delta^{2}\geq\sum_{i\in S}a_{i}^{2}\geq 225\delta^{2}$

and for $j=1,\ldots,4$, we have

$54\delta^{2}\geq\sum_{i\in T_{j}}a_{i}^{2}\geq 45\delta^{2}.$

Now consider the corresponding random processes $W(S;9\delta)$ and
$W(T_{j};3\delta)$ for $j=1,\ldots,4$.

We consider three events partitioning our probability space. The first event
is the event $C_{1}$ that $W(S;9\delta)$ is successful and also at least one
out of $W(T_{j};3\delta)$ for $j=1,\ldots,4$ is successful. The second event
is the event $C_{2}=C_{2}^{\prime}\cap C_{1}^{C}$, where $C_{2}^{\prime}$ is
the event that at least one out of

$W(S;9\delta),\ W(T_{1};3\delta),\ldots,\ W(T_{4};3\delta)$

is successful. And the last event is $C_{3}=C_{1}^{C}\cap C_{2}^{C}$.

By independence of the processes
$W(S;9\delta),W(T_{1};3\delta),\ldots,W(T_{4};3\delta)$ and Lemma 3.4, we have

$\Pr\big{[}C_{1}\big{]}\geq\frac{15}{32},\qquad\Pr\big{[}C_{3}\big{]}\leq\frac{1}{32}.$
(20)

We start by assessing the probability $\Pr\big{[}|Y|\geq
1-a_{1}-a_{2}-a_{3}\big{]}$ conditioned on $C_{1}$. We look at

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|<1-a_{1}-a_{2}-a_{3}|C_{1},x_{1},i_{1},j,x_{2},i_{2},r(T_{1};3\delta),\ldots,r(T_{j-1};3\delta)\big{]},$

for fixed
$x_{1},i_{1},j,x_{2},i_{2},r(T_{1};3\delta),\ldots,r(T_{j-1};3\delta)$, where
$x_{1},i_{1},j,x_{2},i_{2}$ are reals such that both
$|r(S;9\delta)|=x_{1}\in[9\delta,12\delta],$ and the processes
$W(T_{1};3\delta),\ldots,W(T_{j-1};3\delta)$ are not successful, but the
process $W(T_{j};3\delta)$ is successful for some fixed $j$, $1\leq j\leq 4$,
and

$|r(T_{j};3\delta)|=x_{2}\in[3\delta,6\delta].$

Moreover, for the process $W(S;9\delta)$ it took $i_{1}$ terms to be
successful, and for the process $W(T_{j};3\delta)$ it took $i_{2}$ terms to be
successful. Note that the value of $W(S;9\delta)$ is $\pm x_{1}$ with equal
probabilities, and the value of $W(T_{j};3\delta)$ is $\pm x_{2}$ with equal
probabilities, independently both of each other and of all the other
information.

Since $a_{4}\geq 21\delta$, we can apply Observation 3.3 with
$a_{4},x_{1},x_{2}$ to conclude that

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|<1-a_{1}-a_{2}-a_{3}|C_{1},x_{1},i_{1},j,x_{2},i_{2},r(T_{1};3\delta),\ldots,r(T_{j-1};3\delta)\big{]}\leq\frac{1}{8}.$
(21)

As $x_{1},i_{1},j,x_{2},i_{2},r(T_{1};3\delta),\ldots,r(T_{j-1};3\delta)$ were
arbitrary and we have finitely many possibilities for them, we conclude from
(21) that

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|<1-a_{1}-a_{2}-a_{3}|C_{1}\big{]}\leq\frac{1}{8}.$
(22)

We can furthermore estimate the probability $\Pr\big{[}|Y|\geq
1-a_{1}-a_{2}-a_{3}\big{]}$, conditioned on $C_{2}$, using Observation 3.2:

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|<1-a_{1}-a_{2}-a_{3}|C_{2}\big{]}\leq\frac{1}{4}.$
(23)

Analogously, the probability $\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}-a_{3}\big{]}$
conditioned on $C_{3}$, is significant, as shown by Observation 3.1:

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|<1-a_{1}-a_{2}-a_{3}|C_{3}\big{]}\leq\frac{1}{2}.$
(24)

Combining (20), (22), (23) and (24), we get
$q_{1}\geq\frac{205}{256}>\frac{793}{1024}$, and hence
$\mathbf{a}\in\mathcal{A}_{2}$. ∎

We turn to investigating the case $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$. We
record a property that will repeatedly be used in the sequel

$\begin{split}a_{1}^{2}+a_{2}^{2}+a_{3}^{2}&=(a_{1}+a_{2}+a_{3}-2a_{3})^{2}+2a_{3}^{2}-2(a_{1}-a_{3})(a_{2}-a_{3})\\\
&\leq(\frac{1}{3}+2\delta)^{2}+2(\frac{1}{3}-\delta)^{2}=\frac{1}{3}+6\delta^{2}.\end{split}$
(25)

######  Claim 4.3.

If $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$, then $k\geq 11$.

###### Proof of Claim 4.3.

Assume that we had $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$ and $k\leq 10$.
Then using (25), we get

$1=\sum_{i=1}^{n}a_{i}^{2}<(\frac{1}{3}+2\delta)^{2}+8(\frac{1}{3}-\delta)^{2}+450\delta^{2}=1+462\delta^{2}-4\delta,$

being a contradiction, as $1+462\delta^{2}-4\delta<1$ for
$\delta\in(0,1/120]$. ∎

######  Claim 4.4.

If $k\geq 11$ and $a_{8}+a_{9}+a_{10}\geq\frac{2}{3}+\delta$, then
$\mathbf{a}\in\mathcal{A}_{3}$.

###### Proof of Claim 4.4.

Assume that we had $a_{8}+a_{9}+a_{10}\geq\frac{2}{3}+\delta$ and $k\geq 11$.
Then by (19) and Observation 3.1 applied to $a_{4},\ldots,a_{10}$, we obtain
$q_{2},q_{3}\geq\frac{37}{128}$. ∎

######  Claim 4.5.

If $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$ and $a_{5}-a_{10}\geq 3\delta$,
then $\mathbf{a}\in\mathcal{A}_{2}$.

###### Proof of Claim 4.5.

Consider the events $D_{1}$, $D_{2}$, where

$D_{1}=\\{\varepsilon_{4}=\varepsilon_{6}=\varepsilon_{7}\\}$

and $D_{2}=D_{1}^{C}$. Note that

$\Pr\big{[}D_{1}\big{]}=\frac{1}{4}\qquad\Pr\big{[}D_{2}\big{]}=\frac{3}{4}.$
(26)

In the case when $D_{1}$ occurs, let $c_{1}=a_{4}+a_{6}+a_{7}$, $c_{2}=a_{5}$,
$c_{3}=a_{10}$. Since the conditions of Observation 3.3 hold for
$c_{1},c_{2},c_{3}$ (by Claim 4.3, $a_{10}\geq 1-a_{1}-a_{2}-a_{3}$), we
deduce that

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|\leq
1-a_{1}-a_{2}-a_{3}\,|\,D_{1}\big{]}\leq\frac{1}{8}.$ (27)

In the case when $D_{2}$ occurs, Observation 3.2 applied on $b_{1}=a_{5}$,
$b_{2}=a_{10}$ implies that

$\Pr\big{[}|\sum_{i=4}^{n}a_{i}\varepsilon_{i}|\leq
1-a_{1}-a_{2}-a_{3}\,|\,D_{2}\big{]}\leq\frac{1}{4}.$ (28)

Combining (26), (27) and (28), we get

$q_{1}\geq\frac{25}{32}\geq\frac{793}{1024}.$

∎

######  Claim 4.6.

If $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$, $a_{5}-a_{10}<3\delta$ and
$a_{8}+a_{9}+a_{10}<\frac{2}{3}+\delta$, then $k\geq 15$.

###### Proof of Claim 4.6.

Assume that all of the conditions above hold, yet $k\leq 14$. We clearly have

$a_{4}\leq a_{3}=\frac{1}{3}-\delta,$ (29)

and the combination of $a_{5}-a_{10}<3\delta$ and
$a_{8}+a_{9}+a_{10}<\frac{2}{3}+\delta$ gives

$a_{10},\ldots,a_{13}\leq\frac{2}{9}+\frac{\delta}{3}\qquad
a_{5},\ldots,a_{9}<\frac{2}{9}+\frac{10}{3}\delta.$ (30)

Using $\sum_{i=k}^{n}a_{i}^{2}<450\delta^{2}$, (25), (29) and (30), we get

$\displaystyle 1$ $\displaystyle=\sum_{i=1}^{n}a_{i}^{2}$
$\displaystyle=\sum_{i=1}^{3}a_{i}^{2}+a_{4}^{2}+\sum_{i=5}^{9}a_{i}^{2}+\sum_{i=10}^{k-1}a_{i}^{2}+\sum_{i=k}^{n}a_{i}^{2}$
$\displaystyle\leq\Big{(}\frac{1}{3}+6\delta^{2}\Big{)}+\Big{(}\frac{1}{3}-\delta\Big{)}^{2}+5\Big{(}\frac{2}{9}+\frac{10}{3}\delta\Big{)}^{2}+4\Big{(}\frac{2}{9}+\frac{\delta}{3}\Big{)}^{2}+450\delta^{2}$
$\displaystyle=\frac{8}{9}+513\delta^{2}+\frac{22}{3}\delta,$

being a contradiction, as the ultimate expression is strictly smaller than $1$
for any $\delta\in(0,1/120]$. Hence $k\geq 15$. ∎

######  Claim 4.7.

If $k\geq 15$, then $\mathbf{a}\in\mathcal{A}_{2}$.

###### Proof of Claim 4.7.

Applying Observation 3.1 with $a_{4},\ldots,a_{14}$ gives
$q_{1}\geq\frac{793}{1024}$, as required. ∎

The combination of the above claims concludes the proof of Lemma 4.1. ∎

We are now ready to complete the proof of (14) in the case $a_{3}\geq 0.325$
and $a_{1}+a_{2}+a_{3}\leq 1$; that is, we verify (17).

We note that combining $\delta\leq\frac{1}{120}$ with (25), we get

$a_{1}^{2}+a_{2}^{2}+a_{3}^{2}\leq\frac{801}{2400}.$ (31)

First, consider the family $\mathcal{A}_{1}$ with $a_{4}\leq\frac{7}{40}$. In
this case, (31) implies

$\frac{a_{4}}{\sqrt{\sum_{i=4}^{n}a_{i}^{2}}}\leq\frac{\frac{7}{40}}{\sqrt{\frac{1599}{2400}}}<0.216.$
(32)

Moreover, using (18):

$\frac{1-a_{1}-a_{2}-a_{3}}{\sqrt{\sum_{i=4}^{n}a_{i}^{2}}}\leq\frac{\frac{3}{120}}{\sqrt{\frac{1599}{2400}}}<0.032.$
(33)

Finally, (32) and (33) imply

$q_{1}\geq 2D(0.216,0.032).$ (34)

Analogously to (34), we have

$\begin{gathered}q_{2}\geq 2D(0.216,0.828),\qquad q_{3}\geq
2D(0.216,0.828),\\\ q_{4}\geq 2D(0.216,0.858),\qquad q_{5}\geq
2D(0.216,1.634),\\\ q_{6}\geq 2D(0.216,1.654),\qquad q_{7}\geq
2D(0.216,1.654),\\\ q_{8}\geq 2D(0.216,2.452).\end{gathered}$

Using the following estimate,

$\displaystyle
D(0.216,0.032)+D(0.216,0.828)+D(0.216,0.828)+D(0.216,0.858)+D(0.216,1.634)+$
$\displaystyle D(0.216,1.654)+D(0.216,1.654)+D(0.216,2.452)\geq\frac{3}{4}$

we deduce (17) for any $\mathbf{a}\in\mathcal{A}_{1}$.

Next, we consider an $\mathbf{a}$ in the families
$\mathcal{A}_{2},\mathcal{A}_{3}$. Using $a_{4}\leq\frac{1}{3}$ and (31), we
obtain

$\frac{a_{4}}{\sqrt{\sum_{i=4}^{n}a_{i}^{2}}}\leq\frac{\frac{1}{3}}{\sqrt{\frac{1599}{2400}}}<0.41,$
(35)

and we note that (33) still holds. Using (33) and (35), we obtain

$q_{1}\geq 2D(0.41,0.032).$ (36)

Analogously to (36), we derive

$\begin{gathered}q_{2}\geq 2D(0.41,0.828),\qquad q_{3}\geq 2D(0.41,0.828),\\\
q_{4}\geq 2D(0.41,0.858),\qquad q_{5}\geq 2D(0.41,1.634),\\\ q_{6}\geq
2D(0.41,1.654),\qquad q_{7}\geq 2D(0.41,1.654),\\\ q_{8}\geq
2D(0.41,2.452).\end{gathered}$

Note that we only mention the bound for $q_{8}$ above for the sake of
completeness, since we have $D(0.41,2.452)=0$.

When $\mathbf{a}\in\mathcal{A}_{2}$ we can easily verify that

$\displaystyle\frac{793}{2048}+D(0.41,0.828)+D(0.41,0.828)+D(0.41,0.858)+D(0.41,1.634)+$
$\displaystyle D(0.41,1.654)+D(0.41,1.654)+D(0.41,2.452)\geq\frac{3}{4}$

and hence (17) follows for all $\mathbf{a}\in\mathcal{A}_{2}$. For the family
$\mathcal{A}_{3}$ we can verify that

$\displaystyle
D(0.41,0.032)+\frac{37}{256}+\frac{37}{256}+D(0.41,0.858)+D(0.41,1.634)+$
$\displaystyle D(0.41,1.654)+D(0.41,1.654)+D(0.41,2.452)\geq\frac{3}{4}$

and hence (17) follows for all $\mathbf{a}\in\mathcal{A}_{3}$. Proof of this
subcase is thus finished.

###  4.2 Case $a_{1}+a_{2}+a_{3}>1$

####  4.2.1 Subcase $a_{1}+a_{2}\geq 1$

Using Observation 3.1, we have $\Pr[|X|\geq 1]\geq 1/4$.

####  4.2.2 Subcase $a_{1}\geq 0.7$ and not previous subcase

The proof is the same as in Section 4.1.2.

####  4.2.3 Setting for the rest of the subcases

Assume $a_{1}+a_{2}<1$ and $a_{1}+a_{2}+a_{3}>1$. The required inequality
(14), involves $\Pr[|X|\geq 1]$, and may be re-written using elimination in
terms of $Y=\sum_{i=4}^{n}a_{i}\varepsilon_{i}$ as

$\begin{gathered}\frac{2}{8}\Pr[|Y|\leq
a_{1}+a_{2}+a_{3}-1]+\frac{1}{8}\Pr[|Y|>a_{1}+a_{2}+a_{3}-1]+\frac{1}{8}\Pr[|Y|\geq
1-a_{1}-a_{2}+a_{3}]+\\\ \frac{1}{8}\Pr[|Y|\geq
1-a_{1}+a_{2}-a_{3}]+\frac{1}{8}\Pr[|Y|\geq
1+a_{1}-a_{2}-a_{3}]+\text{\small{$\frac{1}{8}\Pr[|Y|\geq
1-a_{1}+a_{2}+a_{3}]+$}}\\\ \text{\small{$\frac{1}{8}\Pr[|Y|\geq
1+a_{1}-a_{2}+a_{3}]+\frac{1}{8}\Pr[|Y|\geq
1+a_{1}+a_{2}-a_{3}]+\frac{1}{8}\Pr[|Y|\geq 1+a_{1}+a_{2}+a_{3}]$}}\geq
3/16.\end{gathered}$

Denote

$L_{1},L_{2},L_{3},L_{4}=a_{1}+a_{2}+a_{3}-1,1-a_{1}-a_{2}+a_{3},1-a_{1}+a_{2}-a_{3},1+a_{1}-a_{2}-a_{3}.$

The inequality we are proving follows by rearranging and multiplying the
following inequality by $1/8$:

$\begin{gathered}\Pr[|Y|\in(L_{1},L_{2})]\leq 1/2+\Pr[|Y|\geq
L_{3}]+\Pr[|Y|\geq L_{4}].\end{gathered}$ (37)

Write $\sigma_{j}^{2}=1-\sum_{i=1}^{j}a_{i}^{2}$. Recall the variance of $Y$
is $\sigma_{3}^{2}$ and its largest weight is $a_{4}$.

####  4.2.4 Subcase $a_{4}\geq 1-a_{1}-a_{3}$ and (either
$a_{4}\notin(L_{1},L_{2})$ or $\max(L_{2}-a_{4},a_{4}-L_{1})\leq
0.35\sigma_{4}$) and not previous subcases

Let us prove (37), i.e. $\Pr[|Y|\in(L_{1},L_{2})]\leq 1/2+\Pr[|Y|\geq
L_{3}]+\Pr[|Y|\geq L_{4}]$.

Since this inequality is symmetric with respect to $Y$, we may assume without
loss of generality that $\varepsilon_{4}=1$, in which case it is clearly
sufficient to prove

$\Pr[Y\in(L_{1},L_{2})|\varepsilon_{4}=1]+\Pr[Y\in(-L_{2},-L_{1})|\varepsilon_{4}=1]\leq
1/2+\Pr[Y>L_{3}|\varepsilon_{4}=1].$

To this end, note that
$\Pr[Y\in(-L_{2},-L_{1})|\varepsilon_{4}=1]\leq\Pr[Y>L_{3}|\varepsilon_{4}=1]$,
which follows by (recall $L_{3}-a_{4}\leq a_{4}+L_{1}$ by assumption):

$\Pr[Y^{\prime}+a_{4}<-L_{1}]=\Pr[Y^{\prime}>L_{1}+a_{4}]\leq\Pr[Y^{\prime}>L_{3}-a_{4}]$

with $Y^{\prime}=Y-a_{4}\varepsilon_{4}$.

Hence our task is to verify $\Pr[Y\in(L_{1},L_{2})|\varepsilon_{4}=1]\leq
1/2$. There are two subcases. If $a_{4}\leq L_{1}$ or $a_{4}\geq L_{2}$, then
we conclude with a general $\Pr[Y^{\prime}>0]\leq 1/2$ bound. If
$a_{4}\in[L_{1},L_{2}]$, we conclude with the inequality from Section 3.5,
recalling that $\max(L_{2}-a_{4},a_{4}-L_{1})\leq 0.35\sigma_{4}$.

####  4.2.5 Subcase not previous cases

Note that (37) follows from

$\Pr[|Y|>L_{1}]\leq 1/2+\Pr[|Y|\geq L_{2}]+\Pr[|Y|\geq L_{3}]+\Pr[|Y|\geq
L_{4}].$

As the left hand side is a probability, it is sufficient we show the right
hand side is at least $1$. This in turn follows from (see Appendix A.2)

$D(a_{4}/\sigma_{3},L_{2}/\sigma_{3})+D(a_{4}/\sigma_{3},L_{3}/\sigma_{3})+D(a_{4}/\sigma_{3},L_{4}/\sigma_{3})\geq
1/4.$ (38)

##  5 Proof of $\Pr[X>1]\geq 1/16$ unless $X=\varepsilon_{1}$

In this section, we prove Theorem 1.2 (which is the best possible). Note that
unlike for Theorem 1.1 where significant further work was required, most of
the work toward proving Theorem 1.2 was done when we developed our tools in
3.3 and now we can just conclude pretty easily.

###  5.1 Case $a_{1}+a_{2}+a_{3}>1$

Clearly,

$\Pr[X>1]\geq\Pr\left[\sum_{i=1}^{3}a_{i}\varepsilon_{i}>1\wedge\sum_{j=4}^{n}a_{j}\varepsilon_{j}\geq
0\right]\geq 1/8\cdot 1/2=1/16.$

###  5.2 Case $a_{1}+a_{2}+a_{3}\leq 1$

In this case we actually show $\Pr[X>1]\geq 1/12$, and the proof is analogous
to that of Section 4.1.1.

####  5.2.1 Subcase $a_{1}\leq 0.4$

We conclude using (12) and (13) with $D(0.4,1)>\frac{1}{12}$.

####  5.2.2 Subcase $a_{1}\geq 0.6$

Let $a=0.6$. We conclude using elimination, (12) and (13) with

$D\left(\frac{1-a}{\sqrt{1-a^{2}}},\frac{1-a}{\sqrt{1-a^{2}}}\right)=D(1/2,1/2)>1/6.$

Notice that in this case $a_{1}$ might be $1$, which forbids elimination by
$a_{1}$. This is where the assumption $X\neq\varepsilon_{1}$ is used.

####  5.2.3 Subcase $a_{1}\in[0.4,0.6]$

We write $\sigma_{2}=\sqrt{1-a_{1}^{2}-a_{2}^{2}}$ and recall that $a_{3}$ is
upper bounded by $a=\min(a_{2},1-a_{1}-a_{2})$, so that $\Pr[X>1]\geq 1/12$
follows from (see Appendix A.3):

$\operatorname*{\mathbb{E}}_{\varepsilon\in\left\\{-1,1\right\\}^{2}}\left[D\left(\frac{a}{\sigma_{2}},\frac{1+a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}}{\sigma_{2}}\right)\right]\geq
1/12.$ (39)

##  6 Toward the $7/64$ bound

We strongly believe that $C_{1}=7/64$. Further to the brief discussion in
subsection 1.4, we will comment in this section what the next steps would be
and what hurdles one would face if we try to continue further to this bound
using the methods of this paper, i.e. combining lower bounds of the type 3.3
with separate arguments for some difficult cases. While somewhat tedious, we
note that similar approach was recently used by Keller and the second author
to resolve the problem of Tomaszewski [9]. Nevertheless, the tools needed here
would be rather different than the ones used in the proof of Tomaszewski’s
conjecture, since we are now dealing with an anti concentration inequality
instead of a concentration one.

Continuing further to the $7/64$ bound using our methods (or similar ones),
there are two particular classes of the collections $\\{a_{i}\\}$ one has to
be very careful about.

First such class are the collections $\\{a_{i}\\}$ for which we have precisely
$\Pr\big{[}X\geq 1\big{]}=\frac{7}{64}$ and thus we can not afford to obtain
any suboptimal bound. As an example of the collection in the first class, one
can consider $a_{1}=\ldots=a_{6}=\frac{1}{\sqrt{6}}$. For this particular
collection, the bound follows trivially from Observation 3.1, since
$a_{3}+a_{4}+a_{5}\geq 1$. We suspect that in fact all the collections in this
class satisfy $a_{3}+a_{4}+a_{5}\geq 1$, making it not too difficult to
handle.

Second such class are the collections $\\{a_{i}\\}$ with

$\Pr\big{[}X>1\big{]}<\frac{7}{64},$

since for these one can’t verify the conjecture by only assuming that the few
largest weights lie in some, however narrow, ranges. Five examples of the
collections in the second class are mentioned in the subsection 1.4 and we
believe these are only such examples.

The collections ‘close to’ $a_{1}=1$ are not a big problem for us, since Lemma
3.4 allows us to show that the bound of $7/64$ holds for collections with
$a_{1}$ large.

######  Proposition 6.1.

If $a_{1}\geq\frac{14}{15}$, then $\Pr\big{[}X\geq 1\big{]}\geq\frac{7}{64}$.

###### Proof.

Note that it is enough to argue that
$p(a_{2},\ldots,a_{n};1-a_{1})\geq\frac{7}{8}$. For that, by Lemma 3.4 we know
that it suffices if $1-a_{1}^{2}\geq 29(1-a_{1})^{2}$. We can easily check
that this is satisfied whenever $a_{1}\geq\frac{14}{15}$. ∎

‘Neighbourhoods’ of the remaining problematic collections are more difficult
(though luckily note that the family $F_{1}(\delta)$ below covers the
‘neighbourhood’ of both the second and the fifth collection). For fixed
$\delta>0$, consider the families

$F_{1}(\delta)=\\{a_{1}+a_{2}<1;a_{2}\geq\frac{1}{2}-\delta\\},$
$F_{2}(\delta)=\\{a_{1}+a_{2}<1;|a_{1}-\frac{2}{3}|,|a_{2}-\frac{1}{3}|\leq\delta\\},$
$F_{3}(\delta)=\\{a_{1}+a_{2}+a_{3}<1;a_{3}\geq\frac{1}{3}-\delta\\}.$

If we want to verify that $C_{1}=7/64$ with the help of computational methods
similar to the ones used in this paper, we must be able to find some
$\delta>0$ for which we can verify by different means that the conjecture
holds for all the collections in $F_{1}(\delta),F_{2}(\delta),F_{3}(\delta)$.
Hope is this could be done in somewhat similar way as the proof of $6/64$
bound within $F_{3}(\frac{1}{120})$ in 4.1.4 when proving Theorem 1.1.

We make a progress in that direction by using stopped random walks and chain
arguments to prove the following.

######  Proposition 6.2.

For $\delta_{0}=10^{-9}$, we have $\Pr\big{[}X\geq 1\big{]}\geq\frac{7}{64}$
for all collections $\\{a_{i}\\}$ in $F_{1}(\delta_{0}),F_{2}(\delta_{0})$.

Our value $\delta_{0}$ is extremely small, but that is because we have not
tried to optimize it at all (as that would result in an even more tedious
argument). We believe with some effort, our solution could be improved to work
for much larger value of $\delta$ which could actually be used in practice.

The arguments for $F_{1}(\delta_{0})$ and $F_{2}(\delta_{0})$ are rather
similar in style and are somewhat tedious. Hence in this section, we only
include the argument for the family $F_{1}(\delta_{0})$ and the argument for
the family $F_{2}(\delta_{0})$ is placed in Appendix B.

Surprisingly, while we were able to improve the bound closer to $\frac{7}{64}$
in that case too, we were not able to prove the bound of $7/64$ for the family
$F_{3}(\delta)$ for any $\delta>0$, so we pose this as an open problem to the
reader. We believe even verifying the conjecture just in this narrow range of
parameters would be of interest.

In subsection 6.1 and in Appendix B, we sometimes sketch the proofs instead of
going through all the details of the calculations. That is because the
calculations would otherwise be very long and it is easy to see that the
sketch could indeed be turned into a rigorous proof.

###  6.1 Family $F_{1}(\delta_{0})$

In this subsection, we prove the following result.

######  Proposition 6.3.

For $\delta_{0}=10^{-9}$, we have $\Pr\big{[}X\geq 1\big{]}\geq\frac{7}{64}$
for all collections $\\{a_{i}\\}$ in $F_{1}(\delta_{0})$.

Together with Proposition B.1, this implies Proposition 6.2.

Assume $a_{1}+a_{2}<1$ and $a_{2}=\frac{1}{2}-\delta$ for some $\delta\leq
10^{-9}$. Also assume our collection $\\{a_{1},\ldots,a_{n}\\}$ has
$\Pr\big{[}|X|\geq 1\big{]}<\frac{7}{32}$. We will derive a contradiction.

Note that $1-a_{1}-a_{2}\leq 2\delta$. Denote
$Y=\sum_{i=3}^{n}a_{i}\varepsilon_{i}$ and

$\begin{gathered}p_{1}=\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]},\qquad
p_{2}=\Pr\big{[}|Y|\geq 1-a_{1}+a_{2}\big{]},\qquad p_{3}=\Pr\big{[}|Y|\geq
1+a_{1}-a_{2}\big{]}.\end{gathered}$

Then, in particular, we have

$\Pr\big{[}|X|\geq 1\big{]}\geq\frac{1}{4}(p_{1}+p_{2}+p_{3}).$

So, it is enough to show

$p_{1}+p_{2}+p_{3}\geq\frac{7}{8}.$ (40)

We can also assume that

$a_{3}+a_{4}+a_{5}<1,$ (41)

else we would be done by Observation 3.1. We will make consecutive claims
about $\\{a_{1},\ldots,a_{n}\\}$, characterizing it more and more precisely
until we are ready to obtain a contradiction.

Call $a_{i}$ big if $a_{i}\geq 1-a_{1}-a_{2}$, and small otherwise. So in
particular if $a_{i}\geq 2\delta$, it must be big. Let $k$ be the smallest
integer such that $a_{k}<1-a_{1}-a_{2}$ (if $a_{n}\geq 1-a_{1}-a_{2}$, set
$k=n+1$).

######  Claim 6.4.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$\sum_{i=k}^{n}a_{i}^{2}\leq 240000\delta^{2}<\frac{\delta}{1000}$.

###### Proof.

Assume for contradiction that this is not true. Then we can take disjoint
subsets $S_{1},\ldots,S_{10000}$ of $\\{a_{k},\ldots,a_{n}\\}$ with

$24\delta^{2}\geq\sum_{i\in S_{j}}a_{i}^{2}\geq 20\delta^{2}$

for $j=1,\ldots 10000$. Now considering the random processes
$W(S_{i};2\delta)$ for $i=1,\ldots,10000$, with probability at least
$\frac{99}{100}$, at least $1000$ of these are successful, and conditional on
that, we obtain $\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]}\geq\frac{19}{20}$ by
Observation 3.1. Hence we overall get

$p_{1}\geq\frac{1881}{2000}>\frac{7}{8},$

and (40) holds. ∎

######  Claim 6.5.

$a_{5}$ and $a_{6}$ are big terms, that is, $a_{6}\geq 1-a_{1}-a_{2}$.

###### Proof.

Assume for contradiction that $a_{6}$ is a small term (i.e. that $k\leq 6$).
Combining Claim 6.4 with (41), we arrive at a contradiction for all
sufficiently small $\delta>0$:

$1=\sum_{i=1}^{5}a_{i}^{2}+\sum_{i=6}^{n}a_{i}^{2}\leq
a_{1}^{2}+a_{2}\sum_{i=2}^{5}a_{i}+\frac{\delta}{1000}\leq(1/2+\delta)^{2}+(1/2-\delta)(3/2-\delta)+\frac{\delta}{1000}=1-\frac{999}{1000}\delta+2\delta^{2}.$

∎

At this point, we split our proof into two cases, the uniform and the non-
uniform one, both of which we handle separately.

####  6.1.1 The uniform case - $a_{3}-a_{k-1}\leq 20\delta$

######  Claim 6.6.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$k\leq 11$.

###### Proof.

Assume we had $k\geq 12$. Note that $a_{3}-a_{k-1}\leq 20\delta$ would then in
particular imply

$a_{3}\leq\sqrt{0.5/9}+O(\delta)<0.24,$ (42)

and we also know

$\sum_{i=3}^{n}a_{i}^{2}\geq 0.4999$ (43)

and

$1+a_{1}-a_{2}\leq 1.00001.$ (44)

Using Observation 3.1 for $a_{3},\ldots,a_{11}$, we get

$p_{1}\geq\frac{386}{512}>\frac{3}{4}.$

Combining (42), (43) and (44), and using (13), we get

$p_{2},p_{3}\geq 2D(0.34,1.42)>0.08>\frac{1}{16}$

and hence (40) holds. ∎

The next corollary follows by combining Chebyshev inequality with Claim 6.4,
using that $\delta$ is small.

######  Corollary 6.7.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$\Pr\big{[}|\sum_{i=k}^{n}a_{i}\varepsilon_{i}|\geq
0.0001\big{]}<\frac{1}{1000}$.

We now sketch how we finish our argument in the subcase $a_{3}-a_{k-1}\leq
20\delta$, using Corollary 6.7. We consider five separate cases depending on
the particular value of $k$ which we know is at least $7$ and at most $11$
(and in fact, we can rule out the case $k=7$ as then we would have
$a_{3}+a_{4}+a_{5}\geq 1$). Due to our restrictions on the value of $\delta$
and Corollary 6.7, we know that $\sum_{i=3}^{n}a_{i}\varepsilon_{i}$ behaves
‘essentially’ like $\sum_{i=3}^{k-1}\varepsilon_{i}\frac{1}{\sqrt{2k-6}}$. So
for instance in the case $k=8$, we argue that $p_{1}\geq\frac{999}{1000}$, as
due to our restrictions on $a_{3},\ldots,a_{7}$, we know we can only have
$|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|<2\delta$ if
$|\sum_{i=8}^{n}a_{i}\varepsilon_{i}|\geq 0.0001$; further, in this case
$k=8$, we analogously argue that
$p_{2},p_{3}\geq\frac{999}{1000}\cdot\frac{1}{32}$.

Similarly, in the case $k=9$, we argue that $p_{1}\geq\frac{11}{16}$,
$p_{2},p_{3}\geq\frac{999}{1000}\cdot\frac{7}{32}$.

The reader can easily verify that such arguments indeed work in all the cases
considered. $\square$

####  6.1.2 The non-uniform case - $a_{3}-a_{k-1}>20\delta$

In this case, we first notice that Observation 3.2 applied to $a_{3},a_{k-1}$
immediately implies the following.

######  Claim 6.8.

We have $p_{1}\geq\frac{3}{4}$.

Next we obtain.

######  Claim 6.9.

We have $a_{3}+a_{4}+a_{5}+a_{6}<1+2\delta$.

###### Proof.

Assume not. Then by Observation 3.1, we have $p_{2},p_{3}\geq\frac{1}{16}$,
and combining this with Claim 6.8 gives (40). ∎

######  Claim 6.10.

$a_{7}$ is a big term.

###### Proof.

Assume for contradiction that $a_{7}$ is a small term (i.e. that $k\leq 7$),
and recall that $a_{3}+a_{4}+a_{5}+a_{6}<1+2\delta$ and
$\sum_{i=7}^{n}a_{i}^{2}<240000\delta^{2}<\frac{\delta}{1000}$. Write
$A=a_{3}+a_{4}$, and arrive at a contradiction for all sufficiently small
$\delta>0$:

$\displaystyle 1$
$\displaystyle=\sum_{i=1}^{6}a_{i}^{2}+\sum_{i=7}^{n}a_{i}^{2}\leq
a_{1}^{2}+a_{2}^{2}+a_{2}(a_{3}+a_{4})+a_{5}(a_{5}+a_{6})+\frac{\delta}{1000}$
$\displaystyle\leq\Big{(}\frac{1}{2}+\delta\Big{)}^{2}+\Big{(}\frac{1}{2}-\delta\Big{)}^{2}+\Big{(}\frac{1}{2}-\delta\Big{)}A+\frac{1+2\delta}{3}(1+2\delta-A)+\frac{\delta}{1000}$
$\displaystyle=\frac{1}{2}+2\delta^{2}+A\Big{(}\frac{1}{6}-\frac{5}{3}\delta\Big{)}+\frac{1}{3}(1+2\delta)^{2}+\frac{\delta}{1000}$
$\displaystyle\leq\frac{1}{2}+2\delta^{2}+(1-2\delta)\Big{(}\frac{1}{6}-\frac{5}{3}\delta\Big{)}+\frac{1}{3}(1+2\delta)^{2}+\frac{\delta}{1000}$
$\displaystyle=1-\frac{2}{3}\delta+\frac{20}{3}\delta^{2}+\frac{\delta}{1000}<1.$

where we used the estimates $a_{5}+a_{6}\leq 1+2\delta-A$, and
$a_{5}\leq(1+2\delta)/3$ and $A\leq 2a_{2}\leq 1-2\delta$.

∎

######  Claim 6.11.

We have $a_{4}\geq 0.07$.

###### Proof.

If not, we can use Claim 6.4 to argue that we have at least $44$ big terms,
otherwise we would have

$\sum_{i=3}^{k-1}a_{i}^{2}<0.49.$

But Observation 3.1 then implies $p_{1}\geq\frac{7}{8}$, and (40) follows. ∎

######  Claim 6.12.

We have $p_{2},p_{3}\geq\frac{3}{64}$.

###### Proof.

We consider two cases. If $a_{3}\leq 0.3$, the result follows using the bounds
(43) and (44) as well as (13) by

$p_{2},p_{3}\geq 2D(0.43,1.42)>0.06>\frac{3}{64}.$

If on the other hand $a_{3}>0.3$, we may argue (using Claim 6.11 and argument
much along the same lines as the proofs of Claim 6.5 and Claim 6.10) that

$a_{3}+a_{4}+\sqrt{\sum_{i=5}^{n}a_{i}^{2}}\geq 1+a_{1}-a_{2}.$

But then let $\varepsilon^{\prime}$ be a sign of
$\sum_{i=5}^{n}a_{i}\varepsilon_{i}$, and consider the events

$A=\\{\varepsilon\colon\varepsilon_{3}=\varepsilon_{4}=\varepsilon^{\prime}\\},\qquad
B=\bigg{\\{}\varepsilon\colon|\sum_{i=5}^{n}a_{i}\varepsilon_{i}|\geq\Big{(}\sum_{i=5}^{n}a_{i}^{2}\Big{)}^{1/2}\bigg{\\}}.$

We have $\Pr\big{[}A\cap B\big{]}\geq\frac{3}{64}$ (using our bound from the
previous sections), and clearly

$|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq 1+a_{1}-a_{2}$

whenever event $A\cap B$ occurs. The result follows. ∎

######  Claim 6.13.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$a_{4}-a_{k-1}\leq 2\delta$.

###### Proof.

Assume for contradiction that $a_{4}-a_{k-1}\geq 2\delta$. Then
$a_{3}+a_{5}+a_{6}$ is not within $2\delta$ neither from $a_{4}$ nor from
$a_{4}+a_{k-1}$. Using Observation 3.2 for $a_{4},a_{k-1}$ in the case when we
do not have $\varepsilon_{3}=\varepsilon_{5}=\varepsilon_{6}$, and Observation
3.3 for $a_{4},a_{k-1},a_{3}+a_{5}+a_{6}$ in the case when we have
$\varepsilon_{3}=\varepsilon_{5}=\varepsilon_{6}$ (which happens with
probability $\frac{1}{4}$) gives

$p_{1}\geq\frac{3}{4}\cdot\frac{3}{4}+\frac{1}{4}\cdot\frac{7}{8}=\frac{25}{32}.$
(45)

Combining Claim 6.12 with (45) gives (40). ∎

Now we are ready to reach the contradiction. First, if
$a_{3}\notin(2a_{k-1}-8\delta,2a_{k-1}+8\delta)$, let $f_{1}=a_{3}+a_{k-1}$
and $f_{2}=a_{4}+a_{5}$. Let $A_{1}=\\{\varepsilon_{3}=\varepsilon_{k-1}\\}$
and $A_{2}=\\{\varepsilon_{4}=\varepsilon_{5}\\}$. Then conditional on
$A_{1}\cap A_{2}$, we have $\Pr\big{[}|Y|\geq
1-a_{1}-a_{2}\big{]}\geq\frac{7}{8}$ by Observation 3.3 for
$f_{1},f_{2},a_{6}$; conditional on $A_{1}\cap A_{2}^{C}$, we have
$\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]}\geq\frac{3}{4}$ by Observation 3.2 for
$a_{3}+a_{k-1},a_{6}$; and conditional on $A_{1}^{C}$, we have
$\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]}\geq\frac{3}{4}$ by Observation 3.2 for
$a_{3}-a_{k-1},a_{6}$. So we conclude $p_{1}\geq\frac{25}{32}$, and hence (40)
holds.

So next assume $a_{3}\in(2a_{k-1}-8\delta,2a_{k-1}+8\delta)$. Here, we observe
that we can assume $k\leq 15$, else we could conclude $p_{1}\geq\frac{25}{32}$
from Observation 3.1. But now, we proceed analogously to how we did at the end
of the argument for the uniform case, again using Corollary 6.7 and detailed
analysis of each of the several cases we have depending on the value of $k$.
Carrying out such analysis is made possible by Claim 6.13.

So the proof of Proposition 6.3 is complete. $\square$

##  7 The high-dimensional version of the problem

The following (non-tight) result constitutes a high-dimensional variant of
Tomaszewski’s problem as well as of the problem studied in this paper. The
result is merely a consequence of the combination of [16, Proposition 2.2] and
[8, Theorem 2]. Nevertheless, for the sake of completeness, we prove it here.

######  Proposition 7.1.

Let $v_{1},\ldots,v_{n}\in\mathbb{R}^{d}$ be vectors with
$\sum_{i}\left\|{v_{i}}\right\|_{2}^{2}=1$. The random variable $X=\sum
v_{i}\varepsilon_{i}$ with $\varepsilon_{i}\sim\left\\{-1,1\right\\}$
uniformly and independently distributed, satisfies

$\Pr[\left\|{X}\right\|_{2}\geq
1]\geq\frac{1-\sqrt{1-1/e^{2}}}{2}>0.035,\qquad\qquad\Pr[\left\|{X}\right\|_{2}\leq
1]\geq\frac{1-\sqrt{1-1/e^{2}}}{2}.$

###### Proof.

The function
$f(\varepsilon)=\left\|{X(\varepsilon)}\right\|_{2}^{2}-1=\sum_{i,j}\varepsilon_{i}\varepsilon_{j}\left\langle
v_{i},v_{j}\right\rangle$ is a _homogenuous_ polynomial of degree $2$ in the
$\varepsilon_{i}$’s. We wish to lower bound the probabilities
$\Pr[f(\varepsilon)\geq 0]$ and $\Pr[f(\varepsilon)\leq 0]$. Recall [8,
Theorem 2]:

$\left\|{f}\right\|_{2}\leq e\left\|{f}\right\|_{1}.$ (46)

Since $\operatorname*{\mathbb{E}}[f]=0$, we can derive (see below)

$\left\|{f}\right\|_{1}^{2}\leq 4\Pr[f>0]\Pr[f\leq
0]\left\|{f}\right\|_{2}^{2}.$ (47)

Plugging (46) into (47) we get

$\left\|{f}\right\|_{1}^{2}\leq 4e^{2}\Pr[f>0]\Pr[f\leq
0]\left\|{f}\right\|_{1}^{2}.$

When $f\equiv 0$, we have $\Pr[f=0]=1$. Otherwise, dividing by
$\left\|{f}\right\|_{1}^{2}$ we obtain

$\Pr[f>0]\Pr[f\leq 0]\geq e^{-2}/4,$

which means both $\Pr[f>0]$ and $\Pr[f\leq 0]$ are at least
$\frac{1-\sqrt{1-1/e^{2}}}{2}$, through $\Pr[f>0]+\Pr[f\leq 0]=1$.

To see (47), notice that by the Cauchy-Schwarz inequality,

$\left\|{f}\right\|_{2}^{2}=\operatorname*{\mathbb{E}}[f^{2}\cdot\mathbbm{1}\\{f>0\\}]+\operatorname*{\mathbb{E}}[f^{2}\cdot\mathbbm{1}\\{f\leq
0\\}]\geq\Pr[f>0]\operatorname*{\mathbb{E}}\left[f\,\middle|\,f>0\right]^{2}+\Pr[f\leq
0]\operatorname*{\mathbb{E}}\left[f\,\middle|\,f\leq 0\right]^{2}.$ (48)

As $\operatorname*{\mathbb{E}}[f]=0$, we have

$\operatorname*{\mathbb{E}}[f\cdot\mathbbm{1}\\{f>0\\}]=-\operatorname*{\mathbb{E}}[f\cdot\mathbbm{1}\\{f\leq
0\\}]=\frac{1}{2}\left\|{f}\right\|_{1}.$

Likewise, we may assume $\Pr[f>0]$ and $\Pr[f\leq 0]$ are both positive as
otherwise (47) trivially holds. Under this assumption, (48) yields

$\left\|{f}\right\|_{2}^{2}\geq\frac{1}{4}\left\|{f}\right\|_{1}^{2}\left(\frac{1}{\Pr[f>0]}+\frac{1}{\Pr[f\leq
0]}\right),$

being (47), using again $\Pr[f>0]+\Pr[f\leq 0]=1$. ∎

Denote by $T_{d}$ the maximum constant for which
$\Pr[\left\|{X}\right\|_{2}\leq 1]\geq T_{d}$ for all $X$ of dimension $d$ as
in Proposition 7.1, and denote by $O_{d}$ the maximum constant for which
$\Pr[\left\|{X}\right\|_{2}\geq 1]\geq O_{d}$ for all $X$ of dimension $d$ as
in Proposition 7.1. Clearly, $T_{d}$ and $O_{d}$ are non-increasing in $d$. We
know $T_{1}=\frac{1}{2}$ [9], while this paper proves that $\frac{6}{32}\leq
O_{1}\leq\frac{7}{32}$. Proposition 7.1 establishes that $T_{d},O_{d}\geq
0.035$ for any $d$. There are two directions for further research here.

The first is to find tighter bounds for $T_{d},O_{d}$ for small values of
$d>1$. We know that $T_{2}\leq\frac{1}{4}$, as demonstrated by

${}_{1}=(\frac{1}{\sqrt{3}},0),\qquad
v_{2}=(-\frac{1}{2\sqrt{3}},\frac{1}{2}),\qquad
v_{3}=(-\frac{1}{2\sqrt{3}},-\frac{1}{2}),$

and $T_{3}\leq\frac{3}{16}$, as demonstrated by

$v_{1}=(\sqrt{\frac{7}{30}},\frac{1}{3},\frac{1}{5}),\ \quad
v_{2}=(\sqrt{\frac{7}{30}},-\frac{1}{3},-\frac{1}{5}),\ \quad
v_{3}=(0,\frac{1}{3},-\frac{1}{5}),\ \quad v_{4}=(0,0,\frac{1}{5}),\ \quad
v_{5}=(0,0,\frac{1}{5}).$

Interestingly, we have not been able to find any examples demonstrating that
$O_{2}<\frac{7}{32}$ (or even that $O_{d_{0}}<\frac{7}{32}$ for any
$d_{0}\in\mathbb{N}$), and hence we pose this as a problem to a reader.

The second possible direction is to investigate how $T_{d},O_{d}$ behave for
large $d$, and in particular to find better bounds for $\inf_{d}T_{d}$ and
$\inf_{d}O_{d}$. It appears that Proposition 7.1 is far from being tight.
Also, as just mentioned, it does not seem completely unthinkable that
$O_{d}=\frac{7}{32}$ for every $d\in\mathbb{N}$ could hold.

##  8 Conclusion

As mentioned previously, we would hope that mixed with some new ideas, the
methods developed in this paper could be used to prove the conjectured optimal
bound of $7/64$ in Theorem 1.1. That is the main open problem left, and even
some progress toward that (like improving Theorem 1.1 to hold for some
constant between $6/64$ and $7/64$) would be of interest.

Another, perhaps easier step one could take in this direction would be to
prove the bound of $7/64$ for the ‘difficult’ family $F_{3}(\delta_{0})$ for
some $\delta_{0}>0$. The significance of this is discussed in more detail in
Section 6.

In a bit different direction, it is likely that one could improve the
multiplicative factor in front of $\sqrt{\operatorname*{\mathrm{Var}}(X)}$ in
Theorem 1.3 from $0.35$ to the optimal conjectured [10] value of $1/\sqrt{7}$.
That would not only be of interest on its own, but as demonstrated by this
paper and our use of Theorem 1.3 when deriving Theorem 1.1, also a useful tool
when attacking similar problems.

Finally, let us mention two interesting generalizations of our main problem
that one can consider.

Firstly, same as Keller and the second author [9], we ask what is the
behaviour of the function

$F(x)=\sup_{X}\Pr[X>x],$

where the supremum is taken over all the Rademacher sums with variance $1$.
Theorem 1.1 establishes that $F(-1)\leq\frac{58}{64}$. We know some asymptotic
results about the behaviour of $F(x)$ [14] and we also know the precise value
of $F(x)$ for some $x$ [2, 9, 14], but much remains to be understood. It would
be tempting to conjecture that $F(x)=F^{=}(x)$, where for $F^{=}(x)$, we take
the supremum over all the the Rademacher sums with variance $1$ and all the
weights equal. Nevertheless, this conjecture turns out not to be true, see
[13].

Further, one can also study the various multi-dimensional questions that
arise, as discussed in Section 7. We find it especially intriguing that we
have not managed to find any $d_{0}\in\mathbb{N}$ for which we could show that
$O_{d_{0}}<7/32$. If there is no such $d_{0}$, that would be a beautiful
generalization of the result of the one dimensional version of the problem.

## Acknowledgements

We profoundly thank Béla Bollobás, Nathan Keller, Peter van Hintum, Marius
Tiba and the anonymous referees for fruitful discussions and suggestions.

The first author was supported by EPSRC (grant no. 2260624). The second author
was supported by the Clore Scholarship Programme, and by the Israel Science
Foundation (grant no. 1612/17).

## References

  * [1] A. Ben-Tal, A. Nemirovski, and C. Roos.  Robust solutions of uncertain quadratic and conic-quadratic problems.  SIAM Journal on Optimization, 13(2):535–560, 2002.
  * [2] V. K. Bentkus, D. Dzindzalieta, et al.  A tight Gaussian bound for weighted sums of Rademacher random variables.  Bernoulli, 21(2):1231–1237, 2015.
  * [3] D. Burkholder.  Independent sequences with the Stein property.  The Annals of Mathematical Statistics, 39(4):1282–1288, 1968.
  * [4] V. Dvořák and O. Klein.  https://github.com/IamPoosha/oleszkiewicz-problem/blob/main/verification.py.
  * [5] P. Erdös.  On a lemma of Littlewood and Offord.  Bulletin of the American Mathematical Society, 51(12):898–902, 1945\.
  * [6] R. K. Guy.  Any answers anent these analytical enigmas?  The American Mathematical Monthly, 93(4):279–281, 1986.
  * [7] P. Hitczenko and S. Kwapień.  On the Rademacher series.  In Probability in Banach Spaces, 9, pages 31–36. Springer, 1994\.
  * [8] P. Ivanisvili and T. Tkocz.  Comparison of moments of Rademacher chaoses.  Arkiv för Matematik, 57(1):121–128, 2019.
  * [9] N. Keller and O. Klein.  Proof of Tomaszewski’s conjecture on randomly signed sums.  arXiv preprint arXiv:2006.16834, 2020.
  * [10] G. Lowther.  https://mathoverflow.net/questions/366894/a-rademacher-root-7-anti-concentration-inequality.
  * [11] S. J. Montgomery-Smith.  The distribution of Rademacher sums.  Proceedings of the American Mathematical Society, 109(2):517–522, 1990.
  * [12] K. Oleszkiewicz.  On the Stein property of Rademacher sequences.  Probability and Mathematical Statistics-PWN, 16(1):127–130, 1995\.
  * [13] I. Pinelis.  On the supremum of the tails of normalized sums of independent Rademacher random variables.  Statistics & Probability Letters, 99:131–134, 2015.
  * [14] I. Pinelis et al.  An asymptotically Gaussian bound on the Rademacher tails.  Electronic Journal of Probability, 17, 2012.
  * [15] H. Prawitz.  Limits for a distribution, if the characteristic function is given in a finite domain.  Scandinavian Actuarial Journal, 1972(2):138–154, 1972.
  * [16] M. Veraar.  A note on optimal probability lower bounds for centered random variables.  In Colloquium Mathematicum, volume 113(2), pages 231–240. Institute of Mathematics Polish Academy of Sciences, 2008.

##  Appendix A Proofs of real numbers inequalities

###  A.1 Proof of (16)

We consider only these $a_{1},a_{2}$ with $a_{1}+a_{2}\leq 1$ and $a_{2}\leq
a_{1}\in[0.3,0.7]$. We denote $a=\min(1-a_{1}-a_{2},a_{2},0.325)$ (being an
upper bound on $a_{3}$), and $\sigma_{2}=\sqrt{1-a_{1}^{2}-a_{2}^{2}}$. We
note that both $a/\sigma_{2}$ and
$(1+a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2})/\sigma_{2}$ for any choice of
$\varepsilon_{1},\varepsilon_{2}\in\left\\{-1,1\right\\}^{n}$ are
$10$-Lipschitz in our domain (e.g., by checking that all partial derivatives
$<\sqrt{50}$ in absolute value), so it suffices we check

$\operatorname*{\mathbb{E}}_{\varepsilon\in\left\\{-1,1\right\\}^{2}}\left[D\left(\frac{a}{\sigma_{2}}+\delta,\frac{1+a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}}{\sigma_{2}}+\delta\right)\right]\geq
3/32$ (49)

on a mesh of $\left\\{(a_{1},a_{2})\,\middle|\,a_{1}+a_{2}\leq 1,a_{2}\leq
a_{1}\in[0.3,0.7]\right\\}$ of granularity $\delta/10$ in both axes.
Inequality (49) can easily be verified [4] for $\delta=0.005$ on such a mesh.

###  A.2 Proof of (38)

In order to verify (38) for all relevant $a_{1},a_{2},a_{4},a_{4}$, we confirm

$D(a_{4}/\sigma_{3}+\delta,L_{2}/\sigma_{3}+\delta)+D(a_{4}/\sigma_{3}+\delta,L_{3}/\sigma_{3}+\delta)+D(a_{4}/\sigma_{3}+\delta,L_{4}/\sigma_{3}+\delta)\geq
1/4,$ (50)

on a fine enough mesh of $a_{1},a_{2},a_{3}$ (which induce an upper bound on
$a_{4}$). Notice the other subcases in the proof handle cases in which
$a_{4}\geq 1-a_{1}-a_{3}$ and

$L_{2}-L_{1}\leq 0.35\sqrt{1-a_{1}^{2}-a_{2}^{2}-2a_{3}^{2}}.$ (51)

All expressions $L_{i}/\sigma_{3}$ and $a_{3}/\sigma_{3}$ and
$(1-a_{1}-a_{3})/\sigma_{3}$ have partial derivatives $<10$, hence considering
a mesh of $\left\\{(a_{1},a_{2},a_{3})\,\middle|\,a_{3}\leq a_{2}\leq
a_{1}\leq 0.7,a_{1}+a_{2}+a_{3}\geq 1,a_{1}+a_{2}\leq 1\right\\}$, with
granularity $\delta/15$ in every axis, we may verify (38) by checking (50) on
the mesh points. One detail is that on the mesh points we bound $a_{4}$ by
$1-a_{1}-a_{3}$ (instead of $\min(a_{3},\sigma_{3})$) only if
$L_{2}-L_{1}+\delta/2<0.35\sqrt{1-a_{1}^{2}-a_{2}^{2}-2a_{3}^{2}}$, ensuring
that if (51) is not satisfied for a point, then its nearest mesh point will
not use the improved bound $a_{4}\leq 1-a_{1}-a_{3}$ (introducing
‘discontinuity’); this behavior is overridden to the points
$(a_{1},a_{2},a_{3})=(0.5\pm 0.02,0.5\pm 0.02,0.5\pm 0.02)$, since there (51)
is always satisfied. Choosing $\delta=0.03$, (50) can be verified [4] to all
the described mesh points.

###  A.3 Proof of $\eqref{eq:16}$

Instead of checking (39), we will check that

$\operatorname*{\mathbb{E}}_{\varepsilon\in\left\\{-1,1\right\\}^{2}}\left[D\left(\frac{\min(a_{2},1-a_{1}-a_{2})}{\sigma_{2}}+\delta,\frac{1+a_{1}\varepsilon_{1}+a_{2}\varepsilon_{2}}{\sigma_{2}}+\delta\right)\right]\geq
1/12$ (52)

with $\sigma_{2}=\sqrt{1-a_{1}^{2}-a_{2}^{2}}$ is satisfied on a mesh of
points in $\left\\{(a_{1},a_{2})\,\middle|\,a_{1}+a_{2}\leq 1,a_{2}\leq
a_{1}\in[0.4,0.6]\right\\}$. Since all the involved arguments fed to $D$ are
$10$-Lipschitz, it suffices we verify (52) on a mesh with $\delta/10$
granularity in every axis. Verification [4] can be done with $\delta=0.01$.

##  Appendix B Family $F_{2}(\delta_{0})$

In this appendix, we prove the following result, which together with
Proposition 6.3, implies Proposition 6.2.

######  Proposition B.1.

For $\delta_{0}=10^{-9}$, we have $\Pr\big{[}X\geq 1\big{]}\geq\frac{7}{64}$
for all collections $\\{a_{i}\\}$ in $F_{2}(\delta_{0})$.

To prove Proposition B.1, take smallest possible $\delta>0$ such that
$a_{1}\in\left[\frac{2}{3}-\delta,\frac{2}{3}+\delta\right]$ and
$a_{2}\in\left[\frac{1}{3}-\delta,\frac{1}{3}+\delta\right]$. Assume
$\delta\leq 10^{-9}$. Assume our collection $\\{a_{1},\ldots,a_{n}\\}$ has
$\Pr\big{[}|X|\geq 1\big{]}<\frac{7}{32}$. We will derive a contradiction.

Note that

$1-a_{1}-a_{2}\leq 2\delta.$ (53)

Denote

$p_{1}=\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
1-a_{1}-a_{2}\big{]},\quad
p_{2}=\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
1-a_{1}+a_{2}\big{]},\quad
p_{3}=\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
1+a_{1}-a_{2}\big{]}.$

Note that $\Pr\big{[}|X|\geq 1\big{]}\geq\frac{1}{4}(p_{1}+p_{2}+p_{3})$, so
it is enough to show that

$p_{1}+p_{2}+p_{3}\geq\frac{7}{8}.$ (54)

We can assume

$a_{3}+a_{4}+a_{5}<1,$ (55)

else we would be done by Observation 3.1. We will make consecutive claims
about the collection $\\{a_{1},\ldots,a_{n}\\}$, characterizing it more and
more precisely until we are ready to obtain a contradiction.

Note that for $\eta=10^{-5}$, the following two lemmas hold.

######  Lemma B.2.

Assume $b_{1}\geq\ldots\geq b_{m}>0$, $\sum_{i=1}^{m}b_{i}^{2}=1$ and
$b_{1}\leq\frac{1}{2}+\eta$. Then

$\Pr\big{[}|\sum_{i=1}^{m}b_{i}\varepsilon_{i}|\geq
4\delta\big{]}\geq\frac{5}{8}.$

###### Proof.

Note that if $b_{3}\geq 4\delta$, we are done by Observation 3.1. So we only
need to consider the case when $b_{3}<4\delta$. First, we argue that we have

$\sum_{i=3}^{m}b_{i}^{2}\geq 960\delta^{2}.$ (56)

Since we know that

$\sum_{i=3}^{m}b_{i}^{2}\geq
1-2(\frac{1}{2}+\eta)^{2}=\frac{1}{2}-2\eta-2\eta^{2},$

to prove (56) holds, it is enough to show

$960\delta^{2}\leq\frac{1}{2}-2\eta-2\eta^{2}.$ (57)

But (57) trivially holds as $\delta\leq 10^{-9},\eta=10^{-5}$.

Now using $4\delta>b_{3},\ldots,b_{m}>0$ and (56), we know that we can choose
$10$ disjoint subsets $S_{1},\ldots,S_{10}$ of $\\{b_{3},\ldots,b_{m}\\}$ such
that for $1\leq i\leq 10$, we have

$96\delta^{2}\geq\sum_{b_{j}\in S_{i}}b_{j}^{2}\geq 80\delta^{2}.$

Then for each of these sets $S_{i}$, we consider the random process
$W(S_{i};4\delta)$. By Lemma 3.4, each of these is successful with probability
at least $\frac{1}{2}$ and independently of the other ones. If for some $t$,
$1\leq t\leq 10$, we condition on the event $E_{t}$ that precisely $t$ of
these processes are successful, Observation 3.1 ensures that

$\Pr\big{[}|\sum_{i=1}^{m}b_{i}\varepsilon_{i}|<4\delta|E_{t}\big{]}\leq\binom{t}{\lfloor
t/2\rfloor}{2^{-t}}.$

So we can bound

$\Pr\big{[}|\sum_{i=1}^{m}b_{i}\varepsilon_{i}|<4\delta\big{]}\leq
2^{-10}+2^{-10}\sum_{t=1}^{10}\binom{10}{t}\binom{t}{\lfloor
t/2\rfloor}{2^{-t}}\leq\frac{3}{8}.$

This now finishes the proof of Lemma B.2. ∎

######  Lemma B.3.

Assume $b_{1}\geq\ldots\geq b_{m}>0$, $\sum_{i=1}^{m}b_{i}^{2}=1$ and
$b_{1}\leq\frac{1}{2}+\eta$. Then

$\Pr\big{[}|\sum_{i=1}^{m}b_{i}\varepsilon_{i}|\geq
1+4\delta\big{]}\geq\frac{1}{8}.$

###### Proof.

This follows directly using (13) by $D(0.51,1.01)=\frac{1}{16}$. ∎

Now we can use these lemmas to prove the following corollary.

######  Corollary B.4.

We have $p_{1}\geq\frac{5}{8}$ and $p_{2}\geq\frac{1}{8}$.

###### Proof.

Note that $a_{3}\leq a_{2}\leq\frac{1}{3}+\delta$ and

$\sum_{i=3}^{n}a_{i}^{2}\geq
1-(\frac{2}{3}+\delta)^{2}-(\frac{1}{3}-\delta)^{2}=\frac{4}{9}-\frac{2}{3}\delta-2\delta^{2}.$

So for $\delta\leq 10^{-9},\eta=10^{-5}$, we see that we have

$a_{3}\leq(\frac{1}{2}+\eta)\sqrt{\sum_{i=3}^{n}a_{i}^{2}}.$

Thus we conclude from Lemma B.2 that

$\displaystyle p_{1}$
$\displaystyle=\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
1-a_{1}-a_{2}\big{]}$
$\displaystyle\geq\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
2\delta\big{]}$
$\displaystyle\geq\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
4\delta\sqrt{\sum_{i=3}^{n}a_{i}^{2}}\big{]}$ $\displaystyle\geq\frac{5}{8}.$

Analogously, we conclude from Lemma B.3 that

$\displaystyle p_{2}$
$\displaystyle=\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq
1-a_{1}+a_{2}\big{]}$
$\displaystyle\geq\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq\frac{2}{3}+2\delta\big{]}$
$\displaystyle\geq\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|\geq(1+4\delta)\sqrt{\sum_{i=3}^{n}a_{i}^{2}}\big{]}$
$\displaystyle\geq\frac{1}{8}.$

∎

######  Claim B.5.

We have $a_{3}>14\delta$.

###### Proof.

Assume we had $a_{3}\leq 14\delta$. By our choice of $\delta$, we can
trivially check that

$\sum_{i=3}^{n}a_{i}^{2}\geq
1-(\frac{2}{3}+\delta)^{2}-(\frac{1}{3}-\delta)^{2}\geq 3920\delta^{2}.$ (58)

Using (58), we can choose $20$ disjoint subsets (possibly containing a single
element) $S_{1},\ldots,S_{20}$ of $\\{a_{3},\ldots,a_{n}\\}$ such that for
$1\leq i\leq 20$, either $S_{i}$ contains a single element $a_{i}\geq
2\delta$, or all its elements are smaller than $2\delta$ and we have

$24\delta^{2}\geq\sum_{b_{j}\in S_{i}}b_{j}^{2}\geq 20\delta^{2}.$

Then for each of these sets $S_{i}$, consider the random process
$W(S_{i};2\delta)$. By Lemma 3.4, each of these is successful with probability
at least $\frac{1}{2}$ and independently of the other ones. If for some $t$,
$1\leq t\leq 20$, we condition on the event $F_{t}$ that precisely $t$ of
these processes are successful, Observation 3.1 ensures that

$\Pr\big{[}|\sum_{i=3}^{n}a_{i}\varepsilon_{i}|<2\delta|F_{t}\big{]}\leq\binom{t}{\lfloor
t/2\rfloor}{2^{-t}}.$

So we can bound

$1-p_{1}\leq\Pr\big{[}|\sum_{i=3}^{n}a_{i}|<2\delta\big{]}\leq
2^{-20}+2^{-20}\sum_{t=1}^{20}\binom{20}{t}\binom{t}{\lfloor
t/2\rfloor}{2^{-t}}\leq\frac{1}{4}.$

Combining $p_{1}\geq\frac{3}{4}$ with $p_{2}\geq\frac{1}{8}$ that we have
proven before, this verifies (54). ∎

Let $k$ be an integer such that $a_{k-1}\geq 1-a_{1}-a_{2}$, but
$a_{k}<1-a_{1}-a_{2}$ (if $a_{n}\geq 1-a_{1}-a_{2}$, set $k=n+1$).

######  Claim B.6.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$\sum_{i=k}^{n}a_{i}^{2}<328\delta^{2}$.

###### Proof.

Assume that we had $\sum_{i=k}^{n}a_{i}^{2}\geq 328\delta^{2}$. Then we can
find disjoint subsets $S_{1},S_{2},T_{1},\ldots,T_{5}$ of
$\\{a_{k},\ldots,a_{n}\\}$ such that the following holds. For $x=1,2$ we have

$104\delta^{2}\geq\sum_{i\in S_{x}}a_{i}^{2}\geq 100\delta^{2}$

and for $y=1,\ldots,5$, we have

$24\delta^{2}\geq\sum_{i\in T_{y}}a_{i}^{2}\geq 20\delta^{2}.$

Now consider the random processes

$W(S_{1};6\delta),W(S_{2};6\delta),W(T_{1};2\delta),\ldots,W(T_{5};2\delta).$

By Lemma 3.4, each of these is successful with probability at least
$\frac{1}{2}$ and independently of the other ones. We apply Observations 3.2
and 3.3, using $a_{3}$ and $r(S_{1};6\delta),\ldots,r(T_{5};2\delta)$, to
bound $p_{1}$. With probability at least $\frac{93}{128}$, both some process
corresponding to $S_{x}$ and some process corresponding to $T_{y}$ are
successful, and conditional on that we get the lower bound of $\frac{7}{8}$ on
$\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]}$. Further, we get the lower bound of
$\frac{3}{4}$ on $\Pr\big{[}|Y|\geq 1-a_{1}-a_{2}\big{]}$ if either some
process corresponding to $S_{x}$ or some process corresponding to $T_{y}$ are
successful, and the lower bound of $\frac{1}{2}$ otherwise (this last case
happens at most with probability $\frac{1}{128}$). So overall, we obtain
$p_{1}>\frac{3}{4}$. Combining that with $p_{2}\geq\frac{1}{8}$ that we have
proven in Corollary B.4, we verify that (54) holds. ∎

######  Claim B.7.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$a_{3}-a_{k-1}<1-a_{1}-a_{2}<2\delta$.

###### Proof.

If we had two terms $a_{s},a_{t}>1-a_{1}-a_{2}$ such that $|a_{s}-a_{t}|\geq
1-a_{1}-a_{2}$, Observation 3.2 for $a_{s},a_{t}$ gives
$p_{1}\geq\frac{3}{4}$. Combining that with $p_{2}\geq\frac{1}{8}$ verifies
(54). ∎

######  Claim B.8.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$k<12$.

###### Proof.

If we had $k\geq 12$, by Observation 3.1, we have
$p_{1}\geq\frac{193}{256}>\frac{3}{4}$, and combining that with
$p_{2}\geq\frac{1}{8}$ verifies (54). ∎

######  Claim B.9.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$k<8$.

###### Proof.

We have already shown that $k\leq 11$. If $11\geq k\geq 8$, note that using
our choice of $\delta$, Claim B.6 and Claim B.7, we get

$a_{5}+a_{6}+a_{7}\geq\frac{2}{3}+2\delta\geq 1-a_{1}+a_{2}.$

That gives $p_{2}\geq\frac{7}{32}$.

Since $k\geq 8$, we also have $p_{1}\geq\frac{11}{16}$ by Observation 3.1.
Hence we verify (54). ∎

######  Claim B.10.

Let $k$ be the smallest integer such that $a_{k}<1-a_{1}-a_{2}$. Then we have
$k\geq 7$ (and hence as also $k\leq 7$, we have $k=7$).

###### Proof.

By our choice of $\delta$, we have $\sum_{i=6}^{n}a_{i}^{2}\geq
328\delta^{2}$, and result thus follows by Claim B.6. ∎

We will now show that $\sum_{i=7}^{n}a_{i}^{2}\geq 328\delta^{2}$ (which
together with Claim B.6 gives a desired contradiction). By our definition of
$\delta$ and assumption that $a_{1}+a_{2}<1$, we either have
$a_{1}=\frac{2}{3}-\delta$ or $a_{2}=\frac{1}{3}-\delta$.

First consider the case $a_{2}=\frac{1}{3}-\delta$. Then

$\sum_{i=1}^{6}a_{i}^{2}\leq(\frac{2}{3}+\delta)^{2}+5(\frac{1}{3}-\delta)^{2}=1-2\delta+6\delta^{2},$

and hence

$\sum_{i=7}^{n}a_{i}^{2}\geq 2\delta-6\delta^{2}>328\delta^{2}$

for every $0<\delta<\frac{1}{167}$.

So we can assume that instead $a_{1}=\frac{2}{3}-\delta$. But now we use (55)
to bound

$\sum_{i=1}^{6}a_{i}^{2}\leq(\frac{2}{3}-\delta)^{2}+(\frac{1}{3}+\delta)^{2}+4(\frac{1}{3})^{2}\leq
1-\frac{2}{3}\delta+2\delta^{2},$

and hence

$\sum_{i=7}^{n}a_{i}^{2}\geq\frac{2}{3}\delta+2\delta^{2}>328\delta^{2}$

for every $0<\delta<\frac{1}{489}$.

Thus we reached a desired contradiction, and the proof of Proposition B.1 is
complete. $\square$