# Tail bound for Poisson random variable

Is the following fact about Poisson random variables true?

For any $\lambda \in (0,1)$ and integer $k > 0$, if $X$ is a Poisson random variable with mean $k \lambda$, then $\Pr(X < k) \geq e^{-\lambda}$.

It clearly holds for $k=1$, and for any fixed $\lambda$ it's easy to see that it holds for all sufficiently large $k$, but for intermediate values of $k$ it's not obvious to me.

-
Any chance there's a typo in the question? What you wrote does not look like a tail bound to me. E.g., if $\lambda$ is $1/2$, you're asking about the probability a Poisson(k/2) is less than k (i.e., that it's less than twice its mean)? The probability a Poisson equals its mode should already be inverse-square-root, much bigger than inverse-exponential. – Ryan O'Donnell Aug 10 '12 at 15:05
Maybe "tail bound" was a poor choice of words. I'm thinking of $\lambda$ as a fixed constant in (0,1), and I think the difficult case is actually when $\lambda$ is very close to 1, so $e^{-\lambda}$ should not be interpreted as inverse-exponential. The probability a Poisson equals its mode is inverse-square-root, this would enable a lower bound of $\Theta(1/\sqrt{k})$, but that doesn't exceed $e^{-\lambda}$ when $k$ is larger than $e^{c \lambda}$ for some $c$. – Bobby Kleinberg Aug 10 '12 at 16:18

The argument below is a bit weird because it is a mixture of an explicit computation and a general handwaving (rigorous handwaving, of course), but, when figuring it out at 70 mph under medium strength rain, I could use neither pen and paper, nor the full power of my imagination, so I just took whatever came easily from both worlds and made this crazy hybrid.

Step 1. Since the gaps between Poisson are governed by independent exponential distributions, you are asking to prove that $P(Z_k=\sum_1^k Y_k>k)\ge e^{-\lambda}$ where $Y_k\in\exp(\lambda)$ are independent.

Step 2. The density of $Z_k$ is proportional to $t^ke^{-\lambda t}$. Thus, it is always skewed to the right around $k$ in the sense that if the probability to be on the right of $k$ is $a$, and the excess $Z_k-k$ conditioned upon $Z_k>k$ is $V$, then $Z_k$ can be coupled with the random variable $W_k$ that is the mixture of $V$ and $-V$ with probabilities $a$ and $1-a$ correspondingly so that $Z_k\ge W_k$. To see it, it suffices to show that the density of $V$ and the density of $k-Z_k$ conditioned upon $Z_k<k$ cross at only one point (then the crossing is of the right type because the density of $V$ survives at infinity but that of $k-Z_k$ dies beyond $k$). This is equivalent to showing that $(k+s)^k e^{-\lambda s}=c(k-s)^k e^{\lambda s}$ can have at most one solution on $(0,k)$, i.e., $\log(1+t)-\log(1-t)-2\lambda t$ is one-to-one on $(0,1)$. But it is a Taylor series with positive coefficients over odd powers of $t$ as long as the coefficient $2-2\lambda$ at $t$ is non-negative, i.e., exactly in the range of $\lambda$ you need.

Step 3. Induction on $k$. Suppose that we have two independent random variables $Z,Z'$ with continuous densities skewed to the right about $k,k'$ in the above sense. Let $a=P(Z>k)$, $a'=P(Z'>k')$. We want to show that we then have $P(Z+Z'>k+k')\ge\min(a,a')$. WLOG, $a\le a'$. Clearly, we are worse off with $W$ and $W'$. But then the probability is \begin{aligned} &aa'+a(1-a')P(V>V')+a'(1-a)P(V'>V) \cr &\ge aa'+a(1-a')[P(V>V')+P(V'>V)]=a\,. \end{aligned}

-

A classical inequality of Teicher (1955) asserts

Proposition (Teicher). Let $X \sim \mathrm{Pois}(\lambda)$. Then, $\mathbb P(X \leq [\lambda]) > e^{-1}$.

A modification of his argument will allow us to prove the following.

Proposition. For $\lambda \in (0,1)$, let $X_{n\lambda} \sim \mathrm{Pois}(n\lambda)$. Then the sequence $b_n := b_{n,n\lambda} = \mathbb P(X_{n\lambda} < n)$ is monotonically increasing. In particular, $b_n \geq e^{-\lambda}$ for all $n$.

Proof. First, note that, by considering a Poisson process with rate 1, we have, $$b_{n+1,\mu} = \sum_{x=0}^n \frac{e^{-\mu} \mu^x}{x!} = \int_\mu^\infty \frac{x^n e^{-x}}{n!} \,\mathrm{d}x \,,$$ for all $n$ and $\mu$. Now, $$b_{n+1,n\lambda} - b_{n+1,(n+1)\lambda} = \int_{n\lambda}^{(n+1)\lambda} \frac{x^n e^{-x}}{n!} \,\mathrm{d}x = \int_0^1 (\lambda(y+n))^n \frac{e^{-\lambda(y+n)}}{n!} \lambda \,\mathrm{d}y \,,$$ where the last equality follows from the substitution $y = (x-n\lambda)/\lambda$.

We can rewrite the last integral as $$\frac{e^{-\lambda n}(\lambda n)^n}{n!} \lambda \int_0^1 (1+y/n)^n e^{-\lambda y} \,\mathrm{dy} < \frac{e^{-\lambda n}(\lambda n)^n}{n!} = b_{n+1,n\lambda} - b_{n,n\lambda} \,$$ where the inequality follows from facts that $(1+y/n)^n < e^y$ and (upon integrating) $e^{1-\lambda} < \lambda^{-1}$, true for any $\lambda \in (0,1)$.

But, then $b_{n,n\lambda} < b_{n+1,(n+1)\lambda}$ which is what was to be shown. Since $b_{1,\lambda} = e^{-\lambda}$, the second part of the proposition statement holds.

-

This is not a full answer, but according to this explanation I think the question asks whether $\Gamma(k, k \lambda) \geq e^{-\lambda} \Gamma(k)$ when $k \in Z^+$, and $\lambda \in (0, 1)$.

Edit: Some answers to this math.se question have lower bounds for the upper incomplete gamma function.

-
Numerically, this appears to be true. – Anthony Leverrier Aug 10 '12 at 19:31

Try $k = 2$ and $\lambda=2$. Then

$P(X < k) = P(X = 0 ) + P(X = 1 ) = \exp(-4) + 4 \exp(-4) \approx 0.0915782$

and

$\exp(-\lambda) = \exp(-2) \approx 0.135335.$

The hypothesis fails.

-
@irchans: $\lambda$ is supposed to be in $(0,1)$. – tergi Aug 10 '12 at 18:21
oops. Next time I will read the question :) – irchans Aug 10 '12 at 18:52