<p>Here is the original question: <a href="https://cstheory.stackexchange.com/questions/17985/what-bound-can-we-get-using-kth-moment-inequality-under-3-wise-independent">What bound can we get using $k$-th moment inequality under 3-wise independence?</a> .Yury has given a 3-wise independent example that shows the upper bound is no better than $O(1/t)$.</p>

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

<p>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?</p>

CC BY-SA 3.0
2013-06-18T16:17:30.537Z
what is the question exactly?
Sasho Nikolov
CC BY-SA 3.0
2013-06-19T01:45:25.463Z
I updated it. Hope it is clear now.
Amos
CC BY-SA 3.0
2013-06-19T07:44:59.710Z
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.
Thomas Steinke
CC BY-SA 3.0
2013-06-19T08:27:44.223Z
In fact I'm asking what the essential information can we get from 3-wise independence. Comparing the bounds derived from these two constructions may be enlightening.
Amos
CC BY-SA 3.0
2013-06-19T16:04:47.120Z
What is $m$? Do your random variables take values in $\{0,1\}$ or in $[m]$? Is $\Omega$ the probability space or the set of random variables indexed by $i$?
Yury
CC BY-SA 3.0
2013-06-20T01:04:36.240Z
Random variables take values in $[m]$. $\Omega$ is the set of random variables.
Amos
CC BY-SA 3.0
2013-06-20T09:28:20.600Z
But Yury's previous answer already tells you that for the purposes of tail bounds, 3-wise independence itself doesn't tell you anything beyond 2-wise independence. Why do you want to go into a specific construction? Why do you care so much about 3-wise independence in particular. This question seems unmotivated to me.
Sasho Nikolov
CC BY-SA 3.0
2013-06-20T12:51:16.867Z
@SashoNikolov sounds like you're reviewing this for a conference :).
Suresh Venkat
CC BY-SA 3.0
2013-06-20T19:55:11.577Z
@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.
Sasho Nikolov
<randomized-algorithms><upper-bounds><pseudorandomness><pseudorandom-generators>
What upper bound can we get under 3-wise independence? (comparable edition)
Amos
# What upper bound can we get under 3-wise independence? (comparable edition)

(Asked by: username_0 on 2013-06-18)

Here is the original question: [What bound can we get using $k$-th moment inequality under 3-wise independence?](https://cstheory.stackexchange.com/questions/17985/what-bound-can-we-get-using-kth-moment-inequality-under-3-wise-independent) .username_3 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?

**Tags:** randomized-algorithms, upper-bounds, pseudorandomness, pseudorandom-generators

> **Comments:**
> **username_1**: what is the question exactly?  
> **username_0**: I updated it. Hope it is clear now.  
> **username_2**: 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.  
> **username_0**: In fact I'm asking what the essential information can we get from 3-wise independence. Comparing the bounds derived from these two constructions may be enlightening.  
> **username_3**: What is $m$? Do your random variables take values in $\{0,1\}$ or in $[m]$? Is $\Omega$ the probability space or the set of random variables indexed by $i$?  
> **username_0**: Random variables take values in $[m]$. $\Omega$ is the set of random variables.  
> **username_1**: But username_3's previous answer already tells you that for the purposes of tail bounds, 3-wise independence itself doesn't tell you anything beyond 2-wise independence. Why do you want to go into a specific construction? Why do you care so much about 3-wise independence in particular. This question seems unmotivated to me.  
> **username_4**: @SashoNikolov sounds like you're reviewing this for a conference :).  
> **username_1**: @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.  

---

## 0 answers

