# What upper bound can we get under 3-wise independence? (comparable edition)

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?

• what is the question exactly? Jun 18 '13 at 16:17
• I updated it. Hope it is clear now.
– Amos
Jun 19 '13 at 1:45
• 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. Jun 19 '13 at 7:44
• @SashoNikolov sounds like you're reviewing this for a conference :). Jun 20 '13 at 12:51
• @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. Jun 20 '13 at 19:55