# An extension of Chernoff bound

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)<p$ for each $i$ and every event $C$ that only depends on $\{X_j|j\neq i\}$.

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

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

• 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 Aug 8 '11 at 22:27
• 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. – MCH Jun 25 '13 at 16:38

The closest things I'm aware of in the literature are extensions of Chernoff bounds to negatively correlated random variables, e.g. see this or this. 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.

• 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 Aug 8 '11 at 17:42
• this is what Appendixes are for :) – Lev Reyzin Aug 8 '11 at 19:01
• 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 Aug 8 '11 at 22:22
• Oops - awesome. I somehow didn't notice your answer! – Lev Reyzin Aug 8 '11 at 23:41

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.