Upper bound for Poisson distribution

Question

For a Poisson random variable $Z$ with the parameter $\lambda,\,$ what would be a good upper bound (sub-exponential type perhaps?) for $P(Z \geq \frac{\lambda}{2})?$

The issue here is that I can't use the large deviation bound for Poisson. What would be an alternative argument?

Answer 1

$P(Z \ge \frac \lambda 2) \to 1$ as $\lambda$ increases, with jumps every time $\lambda$ is an even integer.

So $1$ is a trivial upper bound.

$1-e^{-\lambda}$ is slightly better, but is $P(Z \gt 0)$, so exact when $\lambda \le 2$ but not so brilliant for larger $\lambda$.

Empirically something like $1-0.1e^{-0.16 \lambda}$ looks better as an upper bound for $\lambda>2$.

For an empirical lower bound at least for $\lambda>1$, it seems $1-0.6e^{-0.15 \lambda}$ also seems to work reasonably.

This chart compares these bounds:

and the following chart shows the same bounds for the logarithm of the complementary probability with larger $\lambda$

Answer 2

Note: definitely worth checking the computations, and trivial things like the base of the logarithm. It's late here.

If you can show a sufficiently good bound of that sort for a Binomial random variables with parameters $n$ and $p$, then you will get what you want by applying it to $X^{(n)}\sim \mathrm{Bin}(n,\lambda/n)$ and taking the limit as $n\to \infty$: $$ \mathbb{P}\{X^{(n)} \geq \lambda/2\} \xrightarrow[n\to\infty]{} \mathbb{P}\{Z \geq \lambda/2\} $$ where $Z\sim \mathrm{Poisson}(\lambda)$. Now, using the computations by Thomas Ahle here, for $k := \frac{np_n}{2} = \frac{\lambda}{2}$, we get $$ \mathbb{P}\{X^{(n)} > \lambda/2\} \leq 1- \frac{1}{\sqrt{4\lambda(1-\lambda/(2n))}}e^{-n D\left(\frac{p_n}{2} \,\big\|\, p_n\right)} $$ where, again, $p_n := \frac{\lambda}{n}$. From the definition of the relative entropy and our $p_n$ $$ n D\left(\frac{p_n}{2} \,\big\|\, p_n\right) = \frac{1-\log 2}{2}\cdot \lambda + o(1) $$ and so $$ \boxed{\mathbb{P}\{Z > \lambda/2\} \leq 1- \frac{1}{2\sqrt{\lambda}}e^{-\frac{1-\log 2}{2}\cdot \lambda} } $$ Note that $\frac{1-\log 2}{2} \approx 0.153$, so this appears to be consistent with the empirical upper bound provided by Henry.

---

Why this behaviour is nearly tight (up to the low-order term in the exponent). We also have, by standard bounds on Binomial r.v.'s, that $$ \mathbb{P}\{X^{(n)} \leq \lambda/2\} \leq e^{-n D\left(\frac{p_n}{2} \,\big\|\, p_n\right)} \xrightarrow[n\to\infty]{} e^{-\frac{1-\log 2}{2}\cdot \lambda} $$ and so $$ \boxed{\mathbb{P}\{Z > \lambda/2\} \geq 1-e^{-\frac{1-\log 2}{2}\cdot \lambda} } $$