Let $X:=\sum_{i=1}^n X_i$ with $X_i \sim \text{Be}(p_i)$ independent for $p_i \in [0,1]$ such that $\sum_{i=1}^n p_i \leq \frac{1}{C}$ for some sufficiently large constant $C$. In other words, the $X_i$ are mutually independent $p_i$-Bernoulli Random Variables and $X$ is a Poisson Binomial Random Variable.

I would like to show that $P(X \geq 2)=O(1/C^2)$. In the simple case that $p_i\leq \frac{1}{Cn}$ are equal (or at least have a uniform upper bound), it is not hard to see that

$$P(X\geq 2)\leq \sum_{k=2}^{n} {n \choose k} \left(\frac{1}{Cn}\right)^k \leq \sum_{k=2}^{\infty} \left(\frac{n e}{k C n}\right)^k =O(1/C^2).$$

Now, I am missing an idea for the proof in the case that the $p_i$ are not equal.


1 Answer 1


From the derivation of the Chernoff bound, for any $\gamma>0$ we have, setting $P\stackrel{\rm def}{=} \mathbb{E}[X]$, $$ \mathbb{P}\{X > (1+\gamma)P\} \leq \left(\frac{e^\gamma}{(1+\gamma)^{1+\gamma}}\right)^P \tag{1} $$ which implies, setting $\gamma = \frac{2}{P}-1 \geq 2C-1$, that $$ \mathbb{P}\{X \geq 2\} \leq \left(\frac{e^\gamma}{(1+\gamma)^{1+\gamma}}\right)^{\frac{2}{1+\gamma}} = \left(\frac{e^{\frac{\gamma}{1+\gamma}}}{1+\gamma}\right)^{2} = \Theta\!\left(\frac{1}{\gamma^2}\right) = O\!\left(\frac{1}{C^2}\right) $$ as $C\to \infty$.

(Indeed, as $C\to\infty$, so does $\gamma$, and $\frac{e^{\frac{\gamma}{1+\gamma}}}{1+\gamma} = \frac{e}{\gamma} + o\!\left(\frac{1}{\gamma}\right)$.)

In general: when you want concentration for a sum of independent bounded random variables, think Hoeffding or Chernoff (and if it fails, maybe consider Bennett or Bernstein's inequalities, but in most cases it will not be necessary.)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .