<p><a href="http://infoweekly.blogspot.com/2010/01/moments.html" rel="nofollow">Mihai Pătraşcu explained on his blog how to strengthen the variance bound of Chebyshev by looking at higher moments.</a></p>

<p>He references <a href="http://www.cs.nyu.edu/faculty/siegel/Limited.ps" rel="nofollow">"Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.</a> You also might be interested in "Concentration of Measure for the Analysis of Randomized Algorithms" by Dubhashi and Panconesi.</p>

CC BY-SA 3.0
2013-06-12T15:20:22.567Z
I've already read that blog and that paper too. But I'm curious about the moment methods under this 3-wise independent circumstance. 3rd moment seems untrackable. Maybe 4th moment by using some tricks?
Amos
CC BY-SA 3.0
2013-06-12T15:23:23.250Z
It might help if you added some details about what you tried on the 4th moment and how it didn't work.
jbapple
CC BY-SA 3.0
2013-06-12T16:13:22.447Z
Okay. I wrote some thoughts down.
Amos
CC BY-SA 3.0
2013-06-12T14:02:56.463Z
2013-06-12T14:02:56.463Z
jbapple
<p>I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$.</p>

<p>Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ where each $c_i$ is either equal to $a_i$ or $b_i$ (e.g., one of random variables $W_i$ equals $a_1b_2b_3a_4b_5  \dots a_k$). We defined $n$ random variables $W_i$; note that they are $3$-wise independent. </p>

<p>Let $X_i = (W_i+1)/2$.
Then $X_i\in\{0,1\}$ and ${\mathbb E}[X_i] = 1/2$. Let $t=n/2$. We have, 
$$\Pr(|\sum X_i - n/2| \geq t) = \Pr(|\sum W_i| \geq n) = \Pr(|\prod_{i=1}^k(a_i+b_i)| \geq n) = \Pr(a_i+b_i\neq 0 \text{ for every }i) = \frac{1}{2^k} = \frac{1}{2t}.$$
Here, we used that $\prod_{i=1}^k(a_i+b_i)$ equals $0$ if $a_i+b_i=0$ for some $i$, and equals $-n$ or $n$, otherwise.</p>

<p><strong>Answer:</strong> in general, we cannot obtain a stronger upper bound than $O(1/t)$.</p>

<p><strong>Update:</strong> here is an explanation why $W_1,\dots, W_n$ and consequently $X_1,\dots, X_n$ are 3-wise independent. Each of the words $W_i$ is encoded by a word of length $k$: the $r$-th letter in the word is $a$ if $c_r=a_r$ in the definition of $W_i$, and $b$, if $c_r=b_r$. Consider three random variables $W_i$, $W_j$ and $W_k$. Consider the corresponding words; denote them by $I$, $J$ and $K$. Let $r_1$ be the first position where they differ. Without loss of generality $I_{r_1} = a$, $J_{r_1} = b$, and $K_{r_1} = b$. Then let $r_2$ be the first position where $J$ and $K$ differ. WLOG, $J_{r_2} = a$ and $K_{r_2} = b$. Write $W_i = a_{r_1} \cdot W'_i$, $W_j = a_{r_2}\cdot W_j'$ and $W_k = b_{r_2}\cdot W_k'$. Note that $W_j$ and $W_k$ are independent since for $x,y\in\{\pm 1\}$, we have
$$\Pr(W_j = x, W_k = y) = \Pr(a_{r_2} = (x/W_j'), b_{r_2} = (y/W_k')) = 1/4.$$
Now we prove that $W_i$, $W_j$, and $W_k$ are independent. For  $x,y,z\in\{\pm 1\}$, we have
$$\Pr(W_i = x, W_j = y, W_k = z) = \frac{1}{4}\Pr(W_i = x| W_j = y, W_k = z) = 
\frac{1}{4}\cdot \Pr(a_{r_1} = (x/W'_i)| W_j = y, W_k = z) =  \frac{1}{4}\cdot \frac{1}{2} = \frac{1}{8}.$$</p>

CC BY-SA 3.0
2013-06-13T01:45:35.517Z
The threshold was supposed to be $\mu$. Thanks,Yury. It is an interesting and tricky method of implicitly using 3-wise independent information by construction. But I don't really get it. This construction seems totally new to me. By using Chebyshev, we can get a bound via every even moment. What happens when moving to odd moments?
Amos
CC BY-SA 3.0
2013-06-12T17:14:54.313Z
2013-06-16T15:46:46.500Z
2013-06-16T15:46:46.500Z
Yury
<p>Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)$ derived by Chebyshev's inequality?</p>

<p>If we get a little more information, say $4$-wise independence, then we can use the $4$-th moment to get a $\Theta\left(\frac{1}{t^2}\right)$ bound. Let $Y_i = X_i - \mu$ , $Y = \Sigma_iY_i$, 
$$\Pr(|Y|\geq t) = \Pr(Y^4\geq t^4) \leq\frac{\mathbb{E}(Y^4)}{t^4}=\frac{t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)}{t^4}=\Theta\left(\frac{1}{t^2}\right).$$</p>

<p>If we only have $3$-wise independence, the numerator in the RHS will be $$t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)+24\cdot\sum_{i&lt;j&lt;k&lt;l}\mathbb{E}(Y_iY_jY_kY_l).$$ I don't know how to deal with the summation.</p>

<p>I guess the answer may lie around $\Theta\left(\frac{1}{t^{1.5}}\right)$?</p>

<randomized-algorithms><upper-bounds><pseudorandomness>
What bound can we get using $k$-th moment inequality under 3-wise independence?
Amos
# What bound can we get using $k$-th moment inequality under 3-wise independence?

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

Let $X\_1,\dots, X\_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma\_iX\_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)$ derived by Chebyshev's inequality?

If we get a little more information, say $4$-wise independence, then we can use the $4$-th moment to get a $\Theta\left(\frac{1}{t^2}\right)$ bound. Let $Y\_i = X\_i - \mu$ , $Y = \Sigma\_iY\_i$,
$$\Pr(|Y|\geq t) = \Pr(Y^4\geq t^4) \leq\frac{\mathbb{E}(Y^4)}{t^4}=\frac{t\mathbb{E}(Y\_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y\_1^2)}{t^4}=\Theta\left(\frac{1}{t^2}\right).$$

If we only have $3$-wise independence, the numerator in the RHS will be $$t\mathbb{E}(Y\_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y\_1^2)+24\cdot\sum\_{i

I guess the answer may lie around $\Theta\left(\frac{1}{t^{1.5}}\right)$?

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

---

## 2 answers

### Answer by username_2 on 2013-06-12. Score: 11 | Accepted answer

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$.

Let $a\_1, \dots, a\_k, b\_1, \dots, b\_k\in\_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W\_1,\dots, W\_n$ of the form $c\_1 \cdot c\_2\cdot \dots \cdot c\_k$ where each $c\_i$ is either equal to $a\_i$ or $b\_i$ (e.g., one of random variables $W\_i$ equals $a\_1b\_2b\_3a\_4b\_5 \dots a\_k$). We defined $n$ random variables $W\_i$; note that they are $3$-wise independent.

Let $X\_i = (W\_i+1)/2$.
Then $X\_i\in\{0,1\}$ and ${\mathbb E}[X\_i] = 1/2$. Let $t=n/2$. We have,
$$\Pr(|\sum X\_i - n/2| \geq t) = \Pr(|\sum W\_i| \geq n) = \Pr(|\prod\_{i=1}^k(a\_i+b\_i)| \geq n) = \Pr(a\_i+b\_i\neq 0 \text{ for every }i) = \frac{1}{2^k} = \frac{1}{2t}.$$
Here, we used that $\prod\_{i=1}^k(a\_i+b\_i)$ equals $0$ if $a\_i+b\_i=0$ for some $i$, and equals $-n$ or $n$, otherwise.

**Answer:** in general, we cannot obtain a stronger upper bound than $O(1/t)$.

**Update:** here is an explanation why $W\_1,\dots, W\_n$ and consequently $X\_1,\dots, X\_n$ are 3-wise independent. Each of the words $W\_i$ is encoded by a word of length $k$: the $r$-th letter in the word is $a$ if $c\_r=a\_r$ in the definition of $W\_i$, and $b$, if $c\_r=b\_r$. Consider three random variables $W\_i$, $W\_j$ and $W\_k$. Consider the corresponding words; denote them by $I$, $J$ and $K$. Let $r\_1$ be the first position where they differ. Without loss of generality $I\_{r\_1} = a$, $J\_{r\_1} = b$, and $K\_{r\_1} = b$. Then let $r\_2$ be the first position where $J$ and $K$ differ. WLOG, $J\_{r\_2} = a$ and $K\_{r\_2} = b$. Write $W\_i = a\_{r\_1} \cdot W'\_i$, $W\_j = a\_{r\_2}\cdot W\_j'$ and $W\_k = b\_{r\_2}\cdot W\_k'$. Note that $W\_j$ and $W\_k$ are independent since for $x,y\in\{\pm 1\}$, we have
$$\Pr(W\_j = x, W\_k = y) = \Pr(a\_{r\_2} = (x/W\_j'), b\_{r\_2} = (y/W\_k')) = 1/4.$$
Now we prove that $W\_i$, $W\_j$, and $W\_k$ are independent. For $x,y,z\in\{\pm 1\}$, we have
$$\Pr(W\_i = x, W\_j = y, W\_k = z) = \frac{1}{4}\Pr(W\_i = x| W\_j = y, W\_k = z) =
\frac{1}{4}\cdot \Pr(a\_{r\_1} = (x/W'\_i)| W\_j = y, W\_k = z) = \frac{1}{4}\cdot \frac{1}{2} = \frac{1}{8}.$$

> **Comments:**
> **username_0**: The threshold was supposed to be $\mu$. Thanks,Yury. It is an interesting and tricky method of implicitly using 3-wise independent information by construction. But I don't really get it. This construction seems totally new to me. By using Chebyshev, we can get a bound via every even moment. What happens when moving to odd moments?  

---

### Answer by username_1 on 2013-06-12. Score: 4

[Mihai Pătraşcu explained on his blog how to strengthen the variance bound of Chebyshev by looking at higher moments.](http://infoweekly.blogspot.com/2010/01/moments.html)

He references ["Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.](http://www.cs.nyu.edu/faculty/siegel/Limited.ps) You also might be interested in "Concentration of Measure for the Analysis of Randomized Algorithms" by Dubhashi and Panconesi.

> **Comments:**
> **username_0**: I've already read that blog and that paper too. But I'm curious about the moment methods under this 3-wise independent circumstance. 3rd moment seems untrackable. Maybe 4th moment by using some tricks?  
> **username_1**: It might help if you added some details about what you tried on the 4th moment and how it didn't work.  
> **username_0**: Okay. I wrote some thoughts down.  

---

