# Sum of boolean random variables with small correlations.

Suppose $X_1,\dots,X_N$ are $0/1$-random variables and the following information is known: $$\Pr[X_i=1]\geq 1/n, ~ \Pr[X_iX_j=1]\leq 100/n^2.$$ Let $X=\sum_{i=1}^N X_i$. Assume $N=n^{100}$ for example. As $N\gg n$, if $X_i$'s were pairwise independent then we have $\Pr[X>0]\approx 1$ using e.g. Chebyshev's inequality.

Here $X_i$'s are not pairwise independent, but the correlation of each two of them is $O(1/n)$. I am wondering if $\Pr[X>0]\approx 1$ still holds, and if so, how can one show it? I've tried Chebyshev's inequality: $$\Pr\left[X=0\right]\leq \frac{\mathbf{Var}[X]}{\mathbf{E}[X]^2}$$ but it does not yield any non-trivial bound as $\mathbf{Var}[X]\geq \mathbf{E}[X]^2$. One can use Cauchy-Schwarz inequality to show $$\Pr[X>0]=\mathbf{E}\left[\mathbf{1}^2_{X>0}\right]\geq \frac{\left(\mathbf{E}[\mathbf{1}^2_{X>0}\cdot X]\right)^2}{\mathbf{E}\left[X^2\right]}=\frac{\mathbf{E}[X]^2}{\mathbf{E}\left[X^2\right]}\geq 1/100-o(1)$$ which is still not satisfying (here $\mathbf{1}_{X>0}$ is the indicator random variable for the event $X>0$). Is there any inequalities in probability theory that can be applied here to show $\Pr[X>0]\approx 1$? Thanks!

-

Here is a counterexample.

Assume that $(Y_i)_i$ is i.i.d. Bernoulli 0-1 with $\mathbb E(Y_i)=y/n$, and that $Z$ is Bernoulli 0-1 and independent of $(Y_i)_i$ with $\mathbb E(Z)=z$. Let $$X_i=ZY_i.$$ Then $\mathbb E(X_i)=\mathbb E(Z)\mathbb E(Y_i)=zy/n$ and $\mathbb E(X_iX_j)=\mathbb E(Z)\mathbb E(Y_i)\mathbb E(Y_j)=zy^2/n^2$ hence the hypothesis on the moments hold if $zy\geqslant1$ and $zy^2\leqslant100$ (say, $z=1/2$ and $y=3$ for $n\geqslant3$) but $\mathbb P(X=0)\geqslant\mathbb P(Z=0)=1-z\gt0$ if $z\lt1$, irrespectively of the value of $N$.

-

This is a comment too long to fit in the usual format.

Note that

$$1 \leq Pr(X_1=0)+Pr(X_2=0)+Pr(X_1=X_2=1) \leq \frac{1}{n}+\frac{1}{n}+\frac{100}{n^2}=\frac{2n+100}{n^2},$$

we deduce that $n^2-2n-100 \leq 0$, so $n \leq 11$.

So you cannot make $n$ as large as you want.

-
I don't see why the sum of the three is at least 1 in your inequalities, and I have the condition $\Pr[X_iX_j]\leq 100/n^2$. So $X_i$'s cannot be identical. However I have realized an example showing that the bound given by Cauchy-Schwarz is tight. Namely all $X_i=0$ w.p. about 1-1/100 and all $X_i$'s independent with w.p. about 1/100. – Zeyu Feb 7 '13 at 8:30
@Zeyu : I just deleted the part of my comment that seems wrong. The sum of the three is at least 1 because the union of the three events $X_1=0,X_2=0$ and $X_1=X_2=1$ is the whole probabilistic universe. – Ewan Delanoy Feb 7 '13 at 8:54