1
$\begingroup$

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?

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

2 Answers 2

0
$\begingroup$

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

bounds

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

logs

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user823777
    Mar 17, 2021 at 19:52
  • $\begingroup$ @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 $\endgroup$
    – Henry
    Mar 17, 2021 at 20:53
0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – user823777
    Mar 22, 2021 at 14:15
  • $\begingroup$ @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. $\endgroup$
    – Clement C.
    Mar 22, 2021 at 20:03
  • 1
    $\begingroup$ 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! $\endgroup$
    – user823777
    Mar 23, 2021 at 5:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – user823777
    Mar 23, 2021 at 13:43
  • 1
    $\begingroup$ @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). $\endgroup$
    – Clement C.
    Mar 23, 2021 at 16:11

You must log in to answer this question.