Poisson Tail Estimate using the Poisson Limit Theorem

Question

This is Exercise $2.3.3$ in Vershynin's book.

Let $X\sim \operatorname{Pois}(\lambda)$. Show that for any $t > \lambda$, we have $$P(X\ge t) \le e^{-\lambda}\left(\frac{e\lambda}{t}\right)^t.$$ Hint: Combine Chernoff’s inequality with the Poisson limit theorem.

My work: $$P(X\ge t) = P(e^{sX}\ge e^{st}) \le e^{-st}\, \mathbb E (e^{sX}) = e^{-st} \sum_{k=0}^\infty e^{sk} e^{-\lambda} \frac{\lambda^k}{k!} = e^{-st} e^{-\lambda} \sum_{k=0}^\infty \frac{(e^s\lambda)^k}{k!} = e^{-st-\lambda} e^{e^s\lambda}.$$ The right-side is minimized for $s_0 = \log(t/\lambda)$. This yields $$P(X\ge t) \le e^{-s_0 t-\lambda} e^{e^s_0\lambda} = e^{-\lambda}\left(\frac{e\lambda}{t}\right)^t,$$ as required.

Why does the author suggest using the Poisson limit theorem? I do not understand how it is applicable/useful in this situation, especially when Chernoff's trick and basic optimization yields the inequality. Thanks!

Answer 1

The point of the book is not to claim there is no other way to prove this inequality (as you point out... there is, and that's also a good exercise to do it), but to provide some insight about how things can be related. Now, the book proves (using the MGF method, i.e., this very same "Chernoff trick") the result on Binomial sums:

Theorem 2.3.1 (Chernoff’s inequality). Let $X_i$ be independent Bernoulli random variables with parameters $p_i$. Consider their sum $S_N = \sum_{i=1}^N X_i$ and denote its mean by $\mu = \mathbb{E} S_N$ . Then, for any $t > \mu$, we have $$ \mathbb{P}\{S_N \geq t\} \leq e^{-\mu} \left(\frac{e\mu}{t}\right)^t $$

So sure, you could start from scratch and use Chernoff's trick to derive the result for Poisson random variables, as you did. Or you you leverage what was already proven, and see that you can get it "for free" by using this Theorem 2.3.1 by considering a Binomial sum with $N$ Bernoullis having the same parameter $p_1=\dots=p_N = \frac{\lambda}{N}$, leading to $$ \mathbb{P}\{S_N \geq t\} \leq e^{-\lambda} \left(\frac{e\lambda}{t}\right)^t $$ and then using the Poisson limit theorem (also already available: Theorem 1.3.4) to take the limit $N\to\infty$ in the LHS (the RHS doesn't change! And convergence in distribution means pointwise convergence of the CDF, which is exactly what you want for concentration inequalities as you have here) to get the desired statement.

tl;dr: you can use the Chernoff trick again, yes. But it makes sense to use what you know, connect things, and build on them, instead of repeating the same computations over and over again.