Upper bound for $P(X \geq x)$, where $X \sim \operatorname{Pois}(\lambda)$

Question

I posted the following question in a comment on CDF of a log-concave discrete random variable. Since it is not related to my main question, I thought of reposting it as separate post.

Question:

Let $X \sim \operatorname{Pois}(\lambda)$. I'm interested in a large deviation bound for $X$; more specifically a sub-exponential type bound for $P(X \geq x)$ for all $x\geq 0$. While it's known that such a bound exists for $x \geq \lambda$ (Chernoff bound), it's not clear whether there exists one for $x< \lambda$. Is it possible to obtain a bound (or extend the bound obtained for $x \geq \lambda$) for these $x$ values using standard large-deviation techniques? If not, why not?

Answer 1

$\newcommand\Ga\Gamma\newcommand\Z{\mathbb Z}\DeclareMathOperator\Pois{Pois}$Let $t\mathrel{:=}\lambda$ and $k\mathrel{:=}x\in\Z\cap[0,t)$. Then for $X_t\sim \Pois(t)$ we have $$P(X_t\ge k)=1-\frac{\Ga(k,t)}{\Ga(k)};$$ this can be shown e.g. by integrating $$\Ga(k,t)=\int_t^\infty u^{k-1}e^{-u}\,du$$ $k-1$ times by parts.

It follows now by Corollary 3 of this paper or its arXiv preprint version that $P(X_t\ge k)>1/2$. Therefore (as was noted by user J.), standard large-deviation techniques are not applicable here.

However, using Theorem 1.1 and Proposition 2.7 of this paper or its arXiv preprint version, we have $$P(X_t\ge k)\le B_1(k,t)\mathrel{:=}1-e^{-t} \Big(1+\frac{(t+2)^k-t^k-2^k}{2 k!}\Big)$$ for $k\ge3$ and $$P(X_t\ge k)\le B_2(k,t)\mathrel{:=}1-\frac{e^{-t} t^{k-1}}{(k-1)!}$$ for $k\ge1$.

Both upper bounds, $B_1(k,t)$ and $B_2(k,t)$, on $P(X_t\ge k)$ are nontrivial, in the sense that they both are strictly less than $1$. Both bounds are rather accurate. The bound $B_2(k,t)$ on $P(X_t\ge k)$ is simpler but less accurate than $B_1(k,t)$. What has been said in this paragraph is illustrated by the following graphs $\Big\{\Big(k,\dfrac{P(X_{2k}\ge k)}{B_1(k,2k)}\Big)\colon k\in\{3,\dots,20\}\Big\}$ (red) and $\Big\{\Big(k,\dfrac{P(X_{2k}\ge k)}{B_2(k,2k)}\Big)\colon k\in\{3,\dots,20\}\Big\}$ (blue):

Here the maximum relative error of the bound $B_1(k,2k)$ on $P(X_{2k}\ge k)$ is $\approx0.001$ and the maximum relative error of the bound $B_2(k,2k)$ on $P(X_{2k}\ge k)$ is $\approx0.050$.