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?

$\endgroup$
  • $\begingroup$ what is the question exactly? $\endgroup$ – Sasho Nikolov Jun 18 '13 at 16:17
  • $\begingroup$ I updated it. Hope it is clear now. $\endgroup$ – Amos Jun 19 '13 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 '13 at 7:44
  • 2
    $\begingroup$ @SashoNikolov sounds like you're reviewing this for a conference :). $\endgroup$ – Suresh Venkat Jun 20 '13 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 '13 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.