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

<p><i>Proof Sketch.</i> 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. <i>Q.E.D.</i> (Sorry the proof sketch is so brief. I can elaborate if you want.)</p>

<p>This appears as Prob. 3.8 p. 52 in <i>Pseudorandomness</i> by S. Vadhan.</p>

CC BY-SA 3.0
2013-05-02T03:26:09.557Z
2013-05-02T03:26:09.557Z
Thomas Steinke
<p>This is the first link on Google for the search "chernoff limited independence":</p>

<p><a href="http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf" rel="nofollow">"Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.</a></p>

CC BY-SA 3.0
2013-05-02T03:36:26.820Z
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
CC BY-SA 3.0
2013-05-02T02:13:44.863Z
2013-05-02T02:13:44.863Z
jbapple
<p>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. </p>

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

<p>If needed the corelation between variables belonging to a set could be better characterized. </p>

<p>Thanks</p>

CC BY-SA 3.0
2013-05-02T02:33:06.103Z
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
CC BY-SA 3.0
2013-05-02T02:47:23.323Z
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
CC BY-SA 3.0
2013-05-02T03:40:01.563Z
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 Steinke
CC BY-SA 3.0
2013-05-02T03:42:57.763Z
yes indeed .. I hope I have stated it clear enough
NAg
CC BY-SA 3.0
2013-05-02T03:50:21.683Z
why not still treat each subset as a random variable and use the correlation information to bound its variance?
Sasho Nikolov
CC BY-SA 3.0
2013-05-02T04:01:58.830Z
Unfortunately I am unaware of a form of Chernoff bound that uses the variance of the involved variables and not the lower and upper bounds of the variables. I think I have an idea for deriving something like that but it would be nice if there is existing work on it and you could point me to it. Thanks
NAg
CC BY-SA 3.0
2013-05-02T06:06:03.037Z
See Theorem 2 in these notes: http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/. 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
CC BY-SA 4.0
2020-06-29T13:05:51.440Z
You might be able to leverage the [Lovasz Local Lemma](https://en.wikipedia.org/wiki/Lovász_local_lemma).  It applies to a collection of "bad" events, such that each event is independent of all but a few other events, and upper-bounds the probability that at least one bad event happens.
Neal Young
CC BY-SA 4.0
2020-11-18T14:04:43.023Z
Old question, but there's kind of an obvious answer: Chernoff bounds + union bound.  This is easiest to see when all sets have size exactly k.  Then the variables form a \(n\times k\) matrix where each row is a sequence of independent Bernoulli variables.  Apply Chernoff to each row and multiply the resulting probability by k (the overall sum can only be far from its mean if at least one of the row sums is far from its mean).
Pat Morin
<reference-request><pr.probability><randomized-algorithms><chernoff-bound>
Chernoff Bounds for settings with limited dependence
NAg
# Chernoff Bounds for settings with limited dependence

(Asked by: username_0 on 2013-05-02)

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

**Tags:** reference-request, pr.probability, randomized-algorithms, chernoff-bound
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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 :)  
> **username_2**: 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.  
> **username_0**: yes indeed .. I hope I have stated it clear enough  
> **username_3**: why not still treat each subset as a random variable and use the correlation information to bound its variance?  
> **username_0**: Unfortunately I am unaware of a form of Chernoff bound that uses the variance of the involved variables and not the lower and upper bounds of the variables. I think I have an idea for deriving something like that but it would be nice if there is existing work on it and you could point me to it. Thanks  
> **username_3**: See Theorem 2 in these notes: http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/. 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.  
> **username_4**: You might be able to leverage the [Lovasz Local Lemma](https://en.wikipedia.org/wiki/Lovász_local_lemma).  It applies to a collection of "bad" events, such that each event is independent of all but a few other events, and upper-bounds the probability that at least one bad event happens.  
> **username_5**: Old question, but there's kind of an obvious answer: Chernoff bounds + union bound.  This is easiest to see when all sets have size exactly k.  Then the variables form a \(n\times k\) matrix where each row is a sequence of independent Bernoulli variables.  Apply Chernoff to each row and multiply the resulting probability by k (the overall sum can only be far from its mean if at least one of the row sums is far from its mean).  

---

## 2 answers

### Answer by username_2 on 2013-05-02. Score: 9

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.


---

### Answer by username_6 on 2013-05-02. Score: 4

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.](http://www.cs.umd.edu/~srin/PDF/ch-bounds.pdf)

> **Comments:**
> **username_0**: 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.  

---

