Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. By partially I mean the variables could be divided into subsets of size atmost k such that any variable from two different sets are independent.

Of course one possible technique is that we sum the variables in a set and treat the sums as my new random variables but now the bound of the value we would have on these variables would be k and that's unreasonable in the setting that we have. So could something better be said ?

If needed the corelation between variables belonging to a set could be better characterized.

Thanks

• I guess that under the assumptions you mentioned, treating each subset as a single random variable is tight. To see it, just take each subset to be k copies of the same variable. Some more assumptions are needed if you'd like to prove a better bound. May 2 '13 at 2:33
• Yes that makes sense and hence I had put the last comment in the question. I ll exactly figure out what the dependence is and get back in case its not resolved then. Thanks :)
– NAg
May 2 '13 at 2:47
• The term "limited independence" is usually interpreted as k-wise independence i.e. every subset of of the variables of size at most k is independent. The two answers have interpreted your question like this, which is not quite what you want. May 2 '13 at 3:40
• yes indeed .. I hope I have stated it clear enough
– NAg
May 2 '13 at 3:42
• See Theorem 2 in these notes: terrytao.wordpress.com/2010/01/03/…. If the total variance over all variables is $\sigma$, since each subset random variable is bounded by $k$ in absolute value, you get $\Pr[|S| >= t \sigma] \leq C \max\{\exp(-c t^2), \exp(-c t \sigma/k)\}$, where $S$ is the sum and $C,c$ are constants. Provided you have a significant number of subsets, this is still very good. May 2 '13 at 6:06

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$ Note that this bound does not necessarily improve with greater $k$. So you may want to choose a smaller $k$ to get the best results.

Proof Sketch. W.L.O.G. $k$ is even. Consider the $k^\text{th}$ moment: $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] = \sum_{S \in [n]^k} \text{Ex} \left[ \prod_{i \in S} X_i - \text{Ex}[X_i] \right].$$ Each summand on the RHS is nonzero only if every $i$ appears at least twice in $S$. (Otherwise, since $\text{Ex}[X_i-\text{Ex}[X_i]]=0$ and the other terms are independent, the product is zero.) So each nonzero summand has at most $k/2$ different values of $i$. So there are at most ${n \choose k/2} (k/2)^k$ nonzero summands. Each summand is bounded by $1$. Thus $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] \leq {n \choose k/2} (k/2)^k \leq (n \cdot k^2 /4)^{k/2}.$$ Now apply Markov's inequality to obtain the result. Q.E.D. (Sorry the proof sketch is so brief. I can elaborate if you want.)

This appears as Prob. 3.8 p. 52 in Pseudorandomness by S. Vadhan.

This is the first link on Google for the search "chernoff limited independence":

"Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.

• Thanks a lot for the pointer but I just read the first few pages and it seems like their method works for k-wise independence but the case I presented here was not k-wise independence (if I understood the definition of k-wise independence correctly). This was more like a variable being mutually independent with most except a few variables. Sorry if I am missing something very elementary here.
– NAg
May 2 '13 at 3:36