3
$\begingroup$

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$?

  • 0
    The article "The moment bound is tighter than Chernoff's bound for positive tail probabilities", referenced at [this post](http://math.stackexchange.com/questions/66403/about-bound-based-on-r-th-central-moment) may be of interest.2011-11-07

1 Answers 1

1

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} $