7
$\begingroup$

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<j<k<l}\mathbb{E}(Y_iY_jY_kY_l).$$ I don't know how to deal with the summation.

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

$\endgroup$
11
$\begingroup$

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}.$$

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Amos Jun 13 '13 at 1:45
4
$\begingroup$

Mihai Pătraşcu explained on his blog how to strengthen the variance bound of Chebyshev by looking at higher moments.

He references "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al. You also might be interested in "Concentration of Measure for the Analysis of Randomized Algorithms" by Dubhashi and Panconesi.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Amos Jun 12 '13 at 15:20
  • $\begingroup$ It might help if you added some details about what you tried on the 4th moment and how it didn't work. $\endgroup$ – jbapple Jun 12 '13 at 15:23
  • $\begingroup$ Okay. I wrote some thoughts down. $\endgroup$ – Amos Jun 12 '13 at 16:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.