# Let $X$ be Poisson distributed and $\tau \in (0, 1)$. Are there upper bounds of $\min \{n \in \mathbb N : \mathbb P [X \ge n] \le \tau\}$?

Let $$X$$ be a random variable whose distribution is Poisson with parameter $$\lambda>0$$. Let $$A_\tau := \{n \in \mathbb N : \mathbb P [X \ge n] \le \tau\} \quad \forall \tau \in (0, 1).$$

Are there some upper bounds of $$\min A_\tau$$ in terms of $$\tau$$ and $$\lambda$$? Thank you so much for your elaboration!

• Perhaps you could try something like a one-tailed version of Chebyshev's inequality to give loose bounds Commented Dec 12, 2022 at 1:24

A somewhat more complicated upper bound than @Adtiya Dhawan's answer. But the technique is standard, it is the Cramer-Chernoff technique.

We have that $$P(X \ge n) \le \inf_{\eta > 0} \exp(-n \eta) E[\exp(\eta X)] = \inf_{\eta > 0} \exp(-n \eta + \lambda(\exp(\eta)-1)) = e^{-\lambda}\left(\frac{e \lambda}{n}\right)^n.$$

Hence, $$\min A_{\tau} \le \inf\left\{n : \left(\frac{e \lambda}{n}\right)^n \le \tau e^{\lambda}\right\}.$$ This would be better than $$\lambda / \tau$$.

• Using Stirling's approximation, your bound is equivalent to $e^{-\lambda}\frac{\lambda^n}{n!}\cdot \sqrt{2\pi n}=P(X=n)\cdot \sqrt{2\pi n}$. This leaves open the possibility that $\limsup P(X\ge n)/P(X=n)=+\infty$. In actuality, you can prove $\lim_n P(X\ge n)/P(X=n)=1$. Commented Dec 12, 2022 at 17:08
• \begin{align} P[X\ge n] &=\frac{e^{-\lambda}\lambda^n}{n!}\sum_{k\ge 0}\frac{\lambda^k}{(n+1)(n+2)\cdots (n+k)} \\&\le \frac{e^{-\lambda}\lambda^n}{n!}\sum_{k\ge 0}\frac{\lambda^k}{n^k} \\&=P[X=n]\cdot \frac1{1-\lambda/n} \end{align} Commented Dec 12, 2022 at 17:10

A very simple upper bound is given by Markov's inequality :

$$\mathbb{P}(X \geq n) \leq \frac{\mathbb{E}(X)}{n} = \frac{\lambda}{n} \leq \tau \ \ \text{if} \ n \geq \frac{\lambda}{\tau} \ \text{so that} \ A_{\tau} \leq \frac{\lambda}{\tau}$$

• While correct I feel like it's important to note that Markov's inequality often yields a trivial upper bound (for example, there are cases when it simply guarantees the probability is less than or equal to some constant $a\ge1$ which is always the case.. Commented Dec 12, 2022 at 2:56