25
$\begingroup$

Suppose that $\epsilon_1,\epsilon_2,\ldots$ are IID random variables with the Bernoulli distribution $\mathbb{P}(\epsilon_n=\pm1)=1/2$, and $a_1,a_2,\ldots$ is a real sequence with $\sum_na_n^2=1$. Letting $S=\sum_n\epsilon_na_n$, the question is whether there exists a constant $c > 0$, independent of the choice of $a$, with $$ \mathbb{P}(\vert S\vert\ge1)\ge c.\qquad\qquad{\rm(1)} $$ That is, I am interested in finding a bound on the probability of the sum being within one standard deviation of its mean. If true, this represents a particularly sharp version of the $L^0$ Khintchine inequality. Considering the example with $a_1=1$ and all other $a_i$ set to zero, for which $\mathbb{P}(\vert S\vert > 1)=0$, it is necessary that the inequality inside the probability in (1) is not strict. Also, considering the example with $(a_1,a_2,a_3)=(1/\sqrt2,1/2,1/2)$, it can be seen that $c\le1/4$. I wonder if it is possible to construct further examples showing that $c$ must, in fact, be zero?

For any $0 < u < 1$, it is easy to find a bound $$ \mathbb{P}(\vert S\vert > u)\ge c_u $$ for $c_u > 0$ a constant independent of $a$. Considering the case with $a_1=a_2=1/\sqrt{2}$ and all other $a_i$ set to zero, it is clear that $c_u \le 1/2$. In fact, it can be shown that $c_u=(1-u^2)^2/3$ will suffice (see my answer to this other MO question), but $c_u$ decreases to zero as $u$ goes to $1$, so this does not help with (1). Combining the Paley-Zygmund inequality with the optimal constants in the $L^p$-versions of the Khintchine inequality for $p > 0$ (see ref. 1 or 2) it is possible to give improved values for $c_u$, but it still tends to zero as $u$ goes to 1.

My apologies if this is either obvious or some well-known fact that I have missed, but I could not find any reference for it. This question is something that I originally thought about while writing up some notes on stochastic integration (posted on my blog), as the $L^0$-version of the Khintchine inequality can be used to prove the existence of the stochastic integral. However, it is not necessary to have something as strong as (1) in that case. More recently, it came up again while answering this MO question.

[Update: Its been some time since this question was posted and answered. Many thanks to Anthony, Iosif and Ravi. There is ongoing research on this problem, and it seems likely that the optimal value of $c$ is 7/32 as conjectured by Oleszkiewicz in the paper linked in Ravi's answer. See Some explorations on two conjectures about Rademacher sequences by Hu, Lan and Sun, where the optimal value of 7/32 is shown for sequences of length at most 7, but it is still open in general. Also, the preprint Proof of Tomaszewski's Conjecture on Randomly Signed Sums by Keller and Klein also includes the claim that their methods improve the best known value for $c$ to 1/8.]

Refs:

  1. Haagerup, The best constants in the Khintchine inequality, Studia Math., 70 (3) (1982), 231-283.
  2. Nazarov & Podkorytov, Ball, Haagerup, and distribution functions, Preprint (1997). Available from Fedja Nazarov's homepage.
$\endgroup$
2
  • 1
    $\begingroup$ ${\rm P}(|S| \geq 1) = 2[1-{\rm P}(S \lt 1)]$; ${\bf Problem 10} \star$ in math.leidenuniv.nl/~naw/home/ps/pdf/2008-2.pdf (perhaps open) asks for the probability ${\rm P}(S \lt 1)$. $\endgroup$
    – Shai Covo
    Jan 31, 2011 at 11:08
  • $\begingroup$ Considering $a=(1,1,1,1,1,1)/\sqrt{6}$ gives a probability of $7/2^5=0.21875$. Wonder how close that is to optimal? $\endgroup$ Jan 31, 2011 at 12:52

3 Answers 3

23
$\begingroup$

OK. Here's a proof that $c > 0.002$. No doubt it can be substantially improved. We can assume the $a_i$ are arranged in decreasing order. Write $a$ for $a_1$.

If $a\ge 1/2$, let $X=a_1\epsilon_1$ and $Y=(1-a^2)^{-1/2}(a_2\epsilon_2+\ldots+a_n\epsilon_n)$ so that $S=X+\sqrt{1-a^2}Y$. Notice that $Y$ is of the form so that the inequality in the question applies.

Now $\mathbb P(|\sqrt{1-a^2}Y|\ge 1-a)=\mathbb P(|Y|\ge \sqrt{\frac{1-a}{1+a}})\ge \left(1-\frac{1-a}{1+a}\right)^2/3=4a^2/(3(1+a)^2)$. Since $a\ge 1/2$, this exceeds 4/27, so that provided $\epsilon_1$ has the same sign as $Y$, the sum is at least 1. This occurs with probability at least 2/27.

If on the other hand $a<1/2$ then we have $a_i^2<1/4$ for each $i$. In particular there exists a partition of $\{1,\ldots,n\}$ into two sets $A$ and $B$ such that $3/8\le \sum_{i\in A}a_i^2\le \sum_{i\in B}a_i^2\le 5/8$. Let $\alpha^2=\sum_{i\in A}a_i^2$ and $\beta^2=\sum_{i\in B}a_i^2$. Let $X=\sum_{i\in A}(a_i/\alpha)\epsilon_i$ and $Y=\sum_{i\in B}(a_i/\beta)\epsilon_i$. Then $\mathbb P(|X|\ge 3/4)\ge 49/768$ by the given inequality. Similarly $\mathbb P(|Y|\ge 3/4)\ge 49/768$. The probability that they both exceed $3/4$ and have the same sign is at least $1/2(49/768)^2$. If this is the case $|S|=\alpha |X|+\beta |Y|\ge (3/4)(\alpha+\beta)$. In the worst case $\alpha=\sqrt{3/8}$ and $\beta=\sqrt{5/8}$, but even in this case the right side exceeds 1.

$\endgroup$
1
  • $\begingroup$ That's fantastic, thanks! Worked out easier than I expected. $\endgroup$ Jan 31, 2011 at 12:20
12
$\begingroup$

I would like indeed to improve the lower bound on $c$, to about $0.032$. I'll be using the same notations as in Anthony Quas's answer. As he showed using the result by George Lowther, $$(*)\qquad P(|S|\ge1)\ge\frac{2a^2}{3(1+a)^2},$$ which actually holds for all possible values of $a$ (in $[0,1]$).

The main new ingredient is the following lower bound on $ES^4$:
$$(**)\qquad ES^4=3\Big(\sum_i a_i^2\Big)^2-2\sum_i a_i^4\ge3-2a^2, $$ which suggests that $|S|^2$ must be "large enough with a large enough probability" (as compared with $E|S|^2=1$). On the other hand, $$ ES^4=ES^4\,\mathrm{I}\{|S|<1\}+ES^4\,\mathrm{I}\{|S|\ge1\}\le1 +\sqrt{ES^8\,P(|S|\ge1)}, $$ by the Cauchy--Schwarz inequality; here $\mathrm{I}\{\cdot\}$ is the indicator function. Therefore and in view of $(**)$, $$(***)\qquad P(|S|\ge1)\ge\frac{(2-2a^2)^2}{ES^8}. $$ By the Whittle inequality Whittle, $ES^8\le EZ^8=105$, where $Z$ is a standard normal random variable. So, combining $(*)$ and $(***)$, one has $$ P(|S|\ge1)\ge\min_{a\in[0,1]}\Big(\frac{2a^2}{3(1+a)^2}\bigvee\frac{(2-2a^2)^2}{105}\Big)>0.032. $$

Addendum: As shown in Rademacher-lower, the lower bound $\frac{(2-2a^2)^2}{105}$ on $P(|S|\ge1)$ can be improved to $$\frac{2(1-a^2)^3}{(6+a^2)(5+2 a^2)}.$$ Thus, the lower bound $0.032$ gets improved to $0.043$.

Addendum 2: Instead of the Paley--Zygmund inequality, used by George Lowther to show that $P(|S|>u)\ge(1-u^2)^2/3$ for $u\in(0,1)$, one can use the Cantelli inequality to get $$P(|S|>u)=1-P(1-S^2\ge1-u^2)\ge\frac{(1-u^2)^2}{(1-u^2)^2+E(1-S^2)^2} \ge\frac{(1-u^2)^2}{(1-u^2)^2+2}, $$ since $E(1-S^2)^2=ES^4-1\le2$. Now proceeding as before, one has the lower bound $$\frac{a^2}{(1+a)^2+2a^2} $$ in place of $\frac{2a^2}{3(1+a)^2}$, which results in the improvement of the lower bound on $P(|S|\ge1)$ from $0.043$ to $0.04789$.

$\endgroup$
6
  • $\begingroup$ Thanks! I'm still interested in how high the lower bound can be. So we've narrowed to between 0.032 and 0.22 $\endgroup$ Jun 4, 2015 at 13:25
  • $\begingroup$ I don't have other ideas at the moment, except maybe to try the better bound instead of your $c_u=(1−u^2)^2/3$ that you mentioned. I suspect, though, that that won't help much, since the worst offender is the number $105$ in the denominator, which is mainly responsible for such a low bound as $0.032$. $\endgroup$ Jun 4, 2015 at 20:58
  • $\begingroup$ Got $0.032$ improved to $0.043$. The gap between this and $0.22$ is still large, though. $\endgroup$ Jun 5, 2015 at 20:11
  • 1
    $\begingroup$ Got 0.043 improved to 0.047. $\endgroup$ Jun 7, 2015 at 15:03
  • 1
    $\begingroup$ @GeorgeLowther : I have updated the link. $\endgroup$ Nov 8, 2018 at 12:35
9
$\begingroup$

In 1996, Krzysztof Oleszkiewicz proved that $c = 1/10$ works. Here is the reference: K. Oleszkiewicz (1996), "On the Stein property of Rademacher sequences", Probability and Mathematical Statistics 16:1, 127-130. The paper is currently available on this page: http://www.math.uni.wroc.pl/~pms/publications.php?nr=16.1

$\endgroup$
1
  • $\begingroup$ Fantastic! Thanks, I didn’t know that there were published results for this. After 7 years or so, we are within a factor of 2.2 of the upper bound for $c$. $\endgroup$ Nov 8, 2018 at 22:52

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.