Chernoff style bounds for Poisson distribution

Question

I read today that

for a Poisson distributed random variable $Z$ with expectation $\mathbb E(Z) = \lambda$,
$$P (Z \ge \lambda +t) \le \exp\left( -\frac {t^2}{2(\lambda + t/3)} \right). $$

This is true if $Z$ is binomial $(\lambda, 1)$. In fact, the author cited a reference for binomial distributions. But I do not see how this could transfer to Poisson distribution.

As far as I remember, it seems all these Chernoff type inequalities require the random variable under consideration being a sum of bounded random variables. So I am a bit suspicious of this inequality. Do you think it is still true for Poisson distribution?

Answer 1

You may enjoy reading this short note on Poisson tail bounds (and references within).

Let $h\colon[-1,\infty) \to \mathbb{R}$ be the function defined by $h(u)\stackrel{\rm def}{=} 2\frac{(1+u)\ln(1+u)-u}{u^2}$.

Theorem. Let $X\sim\operatorname{Poisson}(\lambda)$, for some parameter $\lambda > 0$. Then, for any $x>0$, we have $$ \mathbb{P}\left\{ X \geq \lambda + x \right\} \leq e^{-\frac{x^2}{2\lambda}h(\frac{x}{\lambda})} $$ and, for any $0<x< \lambda$, \begin{equation}\label{eq:poisson:lower:tail} \mathbb{P}\left\{ X \leq \lambda - x \right\} \leq e^{-\frac{x^2}{2\lambda}h({-\frac{x}{\lambda}})}. \end{equation} In particular, this implies that $ \mathbb{P}\{ X \geq \lambda + x\},\mathbb{P}\{ X \leq \lambda - x\} \leq e^{-\frac{x^2}{\lambda+x}}$, for $x>0$; from which \begin{equation}\label{eq:poisson:both:tail} \mathbb{P}\{ \lvert{X -\lambda }\rvert \geq x \} \leq 2e^{-\frac{x^2}{2(\lambda+x)}}, \qquad x>0. \end{equation}

A proof (among others) can be found in the above document (also available on GitHub (with $\LaTeX$ source) here).

The relevant reference is

[Pol15] David Pollard. MiniEmpirical. http://www.stat.yale.edu/~pollard/Books/Mini/, 2015. Manuscript (accessed 02-23-2017). 1, 1, 2, 0