An $L^0$ Khintchine inequality - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T04:27:46Z http://mathoverflow.net/feeds/question/53855 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53855/an-l0-khintchine-inequality An $L^0$ Khintchine inequality George Lowther 2011-01-31T03:36:42Z 2011-01-31T20:17:16Z <p>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$ <a href="http://en.wikipedia.org/w/index.php?title=Khintchine_inequality&amp;oldid=295124090" rel="nofollow">Khintchine inequality</a>. 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?</p> <p>For any $0 &lt; u &lt; 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 (<a href="http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/53683#53683" rel="nofollow">see my answer to this other MO question</a>), but $c_u$ decreases to zero as $u$ goes to $1$, so this does not help with (1). Combining the <a href="http://en.wikipedia.org/w/index.php?title=Paley%2525E2%252580%252593Zygmund_inequality&amp;oldid=366994687" rel="nofollow">Paley-Zygmund</a> 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.</p> <p>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 <a href="http://almostsure.wordpress.com/2010/03/03/existence-of-the-stochastic-integral/" rel="nofollow">on my blog</a>), 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 <a href="http://mathoverflow.net/questions/53669/anti-concentration-of-bernoulli-sums/53683#53683" rel="nofollow">this MO question</a>.</p> <p>Refs:</p> <ol> <li>Haagerup, <em>The best constants in the Khintchine inequality</em>, Studia Math., 70 (3) (1982), 231-283.</li> <li>Nazarov &amp; Podkorytov, <em>Ball, Haagerup, and distribution functions</em>, Preprint (1997). Available from Fedja Nazarov's <a href="http://www.math.msu.edu/~fedja/prepr.html" rel="nofollow">homepage</a>.</li> </ol> http://mathoverflow.net/questions/53855/an-l0-khintchine-inequality/53869#53869 Answer by Anthony Quas for An $L^0$ Khintchine inequality Anthony Quas 2011-01-31T08:46:09Z 2011-01-31T08:46:09Z <p>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$. <p> 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. <p> 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. <p> If on the other hand $a&lt;1/2$ then we have $a_i^2&lt;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. </p>