4
$\begingroup$

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?

$\endgroup$
6
  • $\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$ Apr 28, 2014 at 22:09
  • $\begingroup$ @DouglasZare As a general rule, sentences that start with "Clearly" are at high risk of being wrong. Thanks. $\endgroup$
    – Simd
    Apr 29, 2014 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$ Apr 29, 2014 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$
    – Simd
    Apr 29, 2014 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$ Apr 29, 2014 at 6:17

1 Answer 1

7
$\begingroup$

This has been treated in the literature:

http://arxiv.org/pdf/0801.0059v3.pdf

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

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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