2
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.)

$\endgroup$

You must log in to answer this question.

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