2
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ what is the question exactly? $\endgroup$
    – Sasho Nikolov
    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$
    – Suresh Venkat
    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$
    – Sasho Nikolov
    Jun 20, 2013 at 19:55

0

Reset to default

Your Answer

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