Upper bound for Poisson distribution 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?
 A: $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$

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