# poisson-binomial mixture tail bound

Let $X \sim \operatorname{Binom}[(n,p)]$ and $Y \sim \operatorname{Poisson}[f(X)]$, where f is a convex function. Are there any good tail bounds for $Y$? For instance, are there any Chernoff-style bounds for $Y$?

-
The article "The moment bound is tighter than Chernoff's bound for positive tail probabilities", referenced at this post may be of interest. – Sasha Nov 7 '11 at 21:27

## 1 Answer

The Cheroff's bound, for positive random variable, and arbitrary $\theta$ such that the moment generating function $\mathcal{M}_Y(\theta)$ exists: $$\mathbb{P}(Y \ge t) \le \mathrm{e}^{-\theta t} \mathcal{M}_Y(\theta) = \mathbb{E} \left( \mathrm{e}^{-\theta t + f(X) \left( \mathrm{e}^\theta - 1 \right))} \right)$$

If $g_\theta(X) = \mathrm{e}^{-\theta t + f(X) \left( \mathrm{e}^\theta - 1 \right))}$ happens to be concave, then by Jensen's inequality we would have: $$\mathbb{P}(Y \ge t) \le \mathrm{e}^{-\theta t + f( \mathbb{E} \left(X\right)) \left( \mathrm{e}^\theta - 1 \right))} = \mathrm{e}^{-\theta t + f( n p ) \left( \mathrm{e}^\theta - 1 \right))}$$

The inequality above would be true for any such $\theta$ that $g_\theta^{\prime\prime}(X) \le 0$ for all $X \ge 0$: $$0 \ge g_\theta^{\prime\prime}(x) = g(x) \left\{ \left( f^\prime(x) ( \mathrm{e}^{\theta} - 1) \right)^2 + f^{\prime\prime}(x) ( \mathrm{e}^{\theta} - 1) \right\}$$

Alternatively one could look at the moment bound:

$$\mathbb{P}(Y > t) \le \frac{1}{t} \mathbb{E}(Y) = \frac{1}{t} \mathbb{E}(f(X))$$

Again, if $f(x)$ is concave, by Jensen's inequality we would have $$\mathbb{P}(Y > t) \le \frac{f(n p)}{t}$$

-