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?

  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Apr 28 '14 at 22:09
  • $\begingroup$ @DouglasZare As a general rule, sentences that start with "Clearly" are at high risk of being wrong. Thanks. $\endgroup$ – Lembik Apr 29 '14 at 5:30
  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Apr 29 '14 at 5:56
  • $\begingroup$ @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$)? $\endgroup$ – Lembik Apr 29 '14 at 6:06
  • $\begingroup$ It can't be more than $p^4$. I think it can be independent of $n$, although I haven't done the calculations. $\endgroup$ – Douglas Zare Apr 29 '14 at 6:17

This has been treated in the literature:


also see http://arxiv.org/pdf/1201.3261.pdf

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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