Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

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$.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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