<p>The closest things I'm aware of in the literature are extensions of Chernoff bounds to negatively correlated random variables, e.g. see <a href="http://www.brics.dk/RS/96/25/BRICS-RS-96-25.pdf" rel="noreferrer">this</a> or <a href="http://www.dsi.uniroma1.it/~ale/Papers/master.pdf" rel="noreferrer">this</a>.  Formally, your condition could be satisfied without the negative correlation, but the idea is similar.</p>

<p>Because your generalization isn't difficult to prove, it might be that nobody bothered writing it up.</p>

CC BY-SA 3.0
2011-08-08T17:42:25.003Z
You are right, that was also the closest I found (in "Concentration ... for the Analysis of ... Algorithms"). The thing is that my manuscript is getting too long, I would love to avoid yet another spin-off, if possible. If not, I'll have no choice...
curious
CC BY-SA 3.0
2011-08-08T19:01:19.537Z
this is what Appendixes are for :)
Lev Reyzin
CC BY-SA 3.0
2011-08-08T22:22:35.880Z
Hey, guys, it was proved before, and I gave a reference in my answer (to where you can also find all other relevant reference).
Dana Moshkovitz
CC BY-SA 3.0
2011-08-08T23:41:05.963Z
Oops - awesome. I somehow didn't notice your answer!
Lev Reyzin
CC BY-SA 3.0
2011-08-08T17:22:01.153Z
2011-08-08T19:37:09.557Z
2011-08-08T19:37:09.557Z
Lev Reyzin
<p>An alternative reference could be Lemma 1.19 in B. Doerr, Analyzing randomized search heuristics: Tools from probability theory, Theory of Randomized Search Heuristics (A. Auger and B. Doerr, eds.), World Scientific Publishing, 2011, pp. 1-20. </p>

<p>In simple words, it shows that when $X_i=1$ with probability $p_i$ no matter what you condition $X_1, \dots, X_{i-1}$ on, then $X_1, \ldots, X_n$ satisfy all Chernoff-Hoeffding bounds that are valid for independent binary random variables $Y_1, \ldots, Y_n$ with success probability $p_1, \ldots, p_n$, respectively. The proof is elementary and the result is natural, so I guess no-one felt the need to write it up.</p>

CC BY-SA 3.0
2013-06-25T14:45:40.307Z
2013-06-25T16:54:14.540Z
2013-06-25T16:54:14.540Z
Benjamin Doerr
<p>What you want is the generalized Chernoff bound, which only assumes $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ for any subset S of variable indices. The latter follows from your assumption, since for $S=\{i_1,\ldots,i_{|S|}\}$, $$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq p^{|S|}$$
Impagliazzo and Kabanets recently gave an alternative proof of the Chernoff bound, including the generalized one. In their paper you can find all the appropriate references to previous work:
<a href="http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf">http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf</a></p>

CC BY-SA 3.0
2011-08-08T22:27:25.777Z
Thanks for the clarification! In fact, their condition is implied both by what I have and by negative correlations. So, it is indeed qualitatively stronger (I somehow missed that point when I heard Valentine's talk). Now the proof of what I need becomes so short, that I gladly mark my question as answered, thanks a lot!!
curious
CC BY-SA 3.0
2013-06-25T16:38:08.023Z
In your case, you can simply create a sub-martingale out of your variables and use the classical Azuma's inequality to the same effect. For this to work you only need that $Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$ which is implied by your assumption.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-08T18:19:36.110Z
2011-08-08T22:25:44.413Z
2011-08-08T22:25:44.413Z
Dana Moshkovitz
<p>I am looking for a <strong>reference</strong> (not a proof, that I can do) to the following extension of Chernoff.</p>

<p>Let $X_1,..,X_n$ be Boolean random variables, <em>not necessarily independent</em>.
Instead, it is guaranteed that $Pr(X_i=1|C)&lt;p$ for each $i$ and every event $C$ that only depends on $\{X_j|j\neq i\}$.</p>

<p>Naturally, I want an upper bound on $\Pr\left(\sum_{i\in[n]}X_i&gt;(1+\lambda)np\right)$.</p>

<p>Thanks in advance!</p>

<reference-request><pr.probability><chernoff-bound>
An extension of Chernoff bound
curious
# An extension of Chernoff bound

(Asked by: username_0 on 2011-08-08)

I am looking for a **reference** (not a proof, that I can do) to the following extension of Chernoff.

Let $X\_1,..,X\_n$ be Boolean random variables, *not necessarily independent*.
Instead, it is guaranteed that $Pr(X\_i=1|C)

Naturally, I want an upper bound on $\Pr\left(\sum\_{i\in[n]}X\_i>(1+\lambda)np\right)$.

Thanks in advance!

**Tags:** reference-request, pr.probability, chernoff-bound

---

## 3 answers

### Answer by username_2 on 2011-08-08. Score: 28 | Accepted answer

What you want is the generalized Chernoff bound, which only assumes $P(\bigwedge\_{i\in S} X\_{i}) \leq p^{|S|}$ for any subset S of variable indices. The latter follows from your assumption, since for $S=\{i\_1,\ldots,i\_{|S|}\}$, $$P(\bigwedge\_{i\in S} X\_{i}) = P(X\_{i\_1} = 1)P(X\_{i\_2}=1|X\_{i\_1}=1)\cdots P(X\_{i\_{|S|}}=1|X\_{i\_1},...,X\_{i\_{|S|-1}}=1)\leq p^{|S|}$$
Impagliazzo and Kabanets recently gave an alternative proof of the Chernoff bound, including the generalized one. In their paper you can find all the appropriate references to previous work:
<http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf>

> **Comments:**
> **username_0**: Thanks for the clarification! In fact, their condition is implied both by what I have and by negative correlations. So, it is indeed qualitatively stronger (I somehow missed that point when I heard Valentine's talk). Now the proof of what I need becomes so short, that I gladly mark my question as answered, thanks a lot!!  
> **username_4**: In your case, you can simply create a sub-martingale out of your variables and use the classical Azuma's inequality to the same effect. For this to work you only need that $Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$ which is implied by your assumption.  

---

### Answer by username_1 on 2011-08-08. Score: 8

The closest things I'm aware of in the literature are extensions of Chernoff bounds to negatively correlated random variables, e.g. see [this](http://www.brics.dk/RS/96/25/BRICS-RS-96-25.pdf) or [this](http://www.dsi.uniroma1.it/~ale/Papers/master.pdf). Formally, your condition could be satisfied without the negative correlation, but the idea is similar.

Because your generalization isn't difficult to prove, it might be that nobody bothered writing it up.

> **Comments:**
> **username_0**: You are right, that was also the closest I found (in "Concentration ... for the Analysis of ... Algorithms"). The thing is that my manuscript is getting too long, I would love to avoid yet another spin-off, if possible. If not, I'll have no choice...  
> **username_1**: this is what Appendixes are for :)  
> **username_2**: Hey, guys, it was proved before, and I gave a reference in my answer (to where you can also find all other relevant reference).  
> **username_1**: Oops - awesome. I somehow didn't notice your answer!  

---

### Answer by username_3 on 2013-06-25. Score: 3

An alternative reference could be Lemma 1.19 in B. Doerr, Analyzing randomized search heuristics: Tools from probability theory, Theory of Randomized Search Heuristics (A. Auger and B. Doerr, eds.), World Scientific Publishing, 2011, pp. 1-20.

In simple words, it shows that when $X\_i=1$ with probability $p\_i$ no matter what you condition $X\_1, \dots, X\_{i-1}$ on, then $X\_1, \ldots, X\_n$ satisfy all Chernoff-Hoeffding bounds that are valid for independent binary random variables $Y\_1, \ldots, Y\_n$ with success probability $p\_1, \ldots, p\_n$, respectively. The proof is elementary and the result is natural, so I guess no-one felt the need to write it up.


---

