# 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. – Or Meir 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. – Thomas 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. – Sasho Nikolov 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.)