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

• I edited the question. I'm interested in a sub-exponential type bound
– user823777
Mar 17, 2021 at 14:59
• @Surb Not sure how you got $1/2$. Shouldn't it be 2 if you apply Markov?
– user823777
Mar 17, 2021 at 15:03
• @Jane: Sorry indeed...
– Surb
Mar 17, 2021 at 15:03

## 2 Answers

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

• Thanks . It seems that $P(Z \geq \frac{\lambda}{2})$ is at least something like $1/2$ for large $\lambda$?. Maybe that's why it is not in the large deviation regime.
– user823777
Mar 17, 2021 at 19:52
• @Jane $P(Z \geq \frac{\lambda}{2})\ge \frac12$ for $\lambda \ge \log_e(2) \approx 0.69315$. Whether you call that large is a matter for you Mar 17, 2021 at 20:53

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

• Thanks. But, in Thomas's post, he has stated the lower bound holds for $k \geq np$. If so, then can the result be applied with $k = \frac{\lambda}{2}?$. I would appreciate if you could clarify this.
– user823777
Mar 22, 2021 at 14:15
• @Jane Mmh, I'll check that when I have a chance. This is not specified in his answer, just the question, correct? At first glance I don't see any mention of it in the answer, nor in the proof of the inequality (but maybe I missed it). Also, note that the last part (the lower bound) of my question doesn't use Thomas' post. Mar 22, 2021 at 20:03
• I checked the reference provided there ( R.B Ash, Information Theory, p 115 ). The condition $k/n >p$ is required to make it work for the Chernoff bound but it seems Thomas's argument is not based on that. That means this bound works for all $p, k/n <1$. That's interesting!
– user823777
Mar 23, 2021 at 5:16
• One more thing. I guess $\lambda/2$ should necessarily be a positive integer. So, a slight modification must be done using $\lfloor \lambda/2 \rfloor$ or $\lceil \lambda/2 \rceil$ perhaps.
– user823777
Mar 23, 2021 at 13:43
• @Jane Yes, this should be taken care of. But that shouldn't change anything by more than a o(1) in the exponent (the probability of a single point, so far from the mean). Mar 23, 2021 at 16:11