# Probability all Bernoulli random variables take value $1$ with limited independence

Let $S_1,\dots, S_n$ be Bernoulli random variables which are $4$-wise independent. We have that for each $i$, $P(S_i = 1) = p$ for some fixed probability $0 < p < 1$. What can we say about $P(\forall i\; S_i= 1)$ in terms of upper and lower bounds?

Clearly $P(\forall i\; S_i= 1) \geq p^n$ but what is the largest it can be?

• What do you mean, clearly the chance that they are all $1$ is at least $p^n$? That's false in general. For example, let $n = 5, p= 1/2$. Then it could be that $S_5 \equiv S_1+S_2+S_3+S_4 \mod 2$, but any $4$ of these are independent. Apr 28, 2014 at 22:09
• @DouglasZare As a general rule, sentences that start with "Clearly" are at high risk of being wrong. Thanks.
– Simd
Apr 29, 2014 at 5:30
• Well, you can say that the maximal probability that all are $1$ is at least $p^n$ by the example of independent variables. Anyway, I think you can reduce to the case where you first choose the number of $1$s $X$ from some distribution, and then uniformly choose a subset of size $X$. $4$-way independence is a family of linear equations on the simplex of distributions for $X$, so you can view this as a linear programming problem. Apr 29, 2014 at 5:56
• @DouglasZare Thank you. My main interest is really in an upper bound. Is there some way of making the probability very large (or even something like $p$)?
– Simd
Apr 29, 2014 at 6:06
• It can't be more than $p^4$. I think it can be independent of $n$, although I haven't done the calculations. Apr 29, 2014 at 6:17

In particular, the upper bound goes to 0, but only polynomialy in $n$.