Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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)$.
Thanks in advance!
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
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.
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.
