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?

Improve this question
$\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$
    – Douglas Zare
    Commented 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
    Commented 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$
    – Douglas Zare
    Commented 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
    Commented 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$
    – Douglas Zare
    Commented Apr 29, 2014 at 6:17

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .