Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than $O(1/t)$.

There is another way to constructing 3-wise independent variables (see more details in http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l03.ps). Are they essentially equal to each other, particularly on deriving the upper bound of $\Pr(|\sum_i(X_i)-\mu|\geq t)$?

Here is the main idea of the construction: We sample 3 random variables ${r_1,r_2,r_3}$ from $[m]$ uniformly and independently ($m$ is a prime). Then we construct a set $\Omega = \{r_1+r_2*i+r_3*i^2\mod m:i \in [m]\}$. The elements are 3-wise independent. Does the sum of these variables get a similar upper bound?

  • $\begingroup$ what is the question exactly? $\endgroup$ Jun 18, 2013 at 16:17
  • $\begingroup$ I updated it. Hope it is clear now. $\endgroup$
    – Amos
    Jun 19, 2013 at 1:45
  • $\begingroup$ So is the question whether this particular construction of 3-wise independent bits has good concentration? i.e. better concentration bounds than 2-wise independence. Rather general 3-wise independent distributions, as asked in the original question. $\endgroup$
    – Thomas
    Jun 19, 2013 at 7:44
  • 2
    $\begingroup$ @SashoNikolov sounds like you're reviewing this for a conference :). $\endgroup$ Jun 20, 2013 at 12:51
  • 1
    $\begingroup$ @Suresh lol it does..no more commenting late at night. in a less snappy tone: it feels like OP has some other goal in mind and if he does, it will be more productive if he articulates it. $\endgroup$ Jun 20, 2013 at 19:55


Your Answer

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