Proof of Series Formula, Exponential Moments, and Chernoff Tail Bounds for the Poisson Distribution

Write $P_\mu$ for the Poisson distribution with parameter $\mu$, so that $P_\mu(\{k\})=\exp(-\mu)\mu^{k}/k!$ for $k\in\mathbb{N}_0$ and $P_\mu(\mathbb{R}\setminus\mathbb{N}_0)=0$, and put $w_k=\exp(-\mu)\mu^{k}/k!$.

Claim 1. Since $g$ is measurable and $K$ is a random variable, $g(K)$ is a random variable (preimages compose), nonnegative, and by claim 1 of Change of Variables for Expectations, $\mathbb{E}[g(K)]=\int_{\mathbb{R}}g\,dP_\mu$. Put $Z=\mathbb{R}\setminus\mathbb{N}_0$, a Borel set ($\mathbb{N}_0$ being a countable union of singletons). By additivity of the integral for nonnegative measurable functions, $\int g\,dP_\mu=\int g\mathbf{1}_{\mathbb{N}_0}\,dP_\mu+\int g\mathbf{1}_{Z}\,dP_\mu$, where $\mathbf{1}_{E}$ denotes the indicator of $E$ (a measurable function by claim 1 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions, products being measurable by claim 3 there). The second integral vanishes: by Lebesgue Integral of a Nonnegative Measurable Function it is the least upper bound of the integrals of simple functions $0\le s\le g\mathbf{1}_{Z}$, and any such $s$ vanishes off $Z$, so that in its standard representation $s=\sum_i c_i\mathbf{1}_{A_i}$ (over the distinct values $c_i$ of $s$) every $A_i$ with $c_i>0$ is contained in $Z$, and $\int s\,dP_\mu=\sum_ic_iP_\mu(A_i)=0$ by monotonicity of the measure (claim 2 of Basic Properties of a Measure). For the first integral let $g_n=\sum_{k=0}^{n}g(k)\mathbf{1}_{\{k\}}$ for $n\in\mathbb{N}_0$; each $g_n$ is a simple function whose distinct values are $0$ and the distinct nonzero values $v$ of $g_n$, the level set of such a $v$ being $A_v=\bigcup\{\{k\}:k\le n,\ g(k)=v\}$; the $0$-term of the standard representation contributes nothing to the integral, so by Simple Function and Its Integral and finite additivity (claim 1 of Basic Properties of a Measure) $\int g_n\,dP_\mu=\sum_v v\,P_\mu(A_v)=\sum_v\sum_{k\le n:\,g(k)=v}v\,w_k=\sum_{k=0}^{n}g(k)w_k$ (the terms with $g(k)=0$ contributing nothing), and $g_n\le g_{n+1}$ with $g_n\to g\mathbf{1}_{\mathbb{N}_0}$ pointwise on $\mathbb{R}$ (at a point $k\in\mathbb{N}_0$ the sequence equals $g(k)$ from $n=k$ on; off $\mathbb{N}_0$ it is $0$). By Monotone Convergence Theorem, $\int g\mathbf{1}_{\mathbb{N}_0}\,dP_\mu=\lim_n\sum_{k=0}^{n}g(k)w_k$, and this nondecreasing limit is the least upper bound of the partial sums, which is the value of the sum $\sum_{k\in\mathbb{N}_0}w_kg(k)$ of the nonnegative function $k\mapsto w_kg(k)$ over $\mathbb{N}_0$ (every finite subset of $\mathbb{N}_0$ is contained in an initial segment, exactly as in Poisson Distribution). This proves claim 1.

Claim 2. Fix $\theta\in\mathbb{R}$. The map $g(u)=\exp(\theta u)$ is sequentially continuous on $\mathbb{R}$: if $u_n\to u$ then $\theta u_n\to\theta u$ by limit arithmetic, and $\exp(\theta u_n)\to\exp(\theta u)$ because $\exp$ is differentiable everywhere (claim 3 of Basic Properties of the Exponential Function), hence continuous, hence sequentially continuous; so it is Borel measurable by Sequentially Continuous Functions of Measurable Euclidean Maps are Measurable applied with the measurable space $(\mathbb{R},\mathcal{B}(\mathbb{R}))$, $E=\mathbb{R}$ and the identity map; and it is positive. By claim 1 of the present lemma,

$$\mathbb{E}[\exp(\theta K)]=\sum_{k\in\mathbb{N}_0}\exp(-\mu)\frac{\mu^{k}}{k!}\exp(\theta k)=\exp(-\mu)\sum_{k\in\mathbb{N}_0}\frac{(\mu\exp(\theta))^{k}}{k!},$$

because $\exp(\theta k)=\exp(\theta)^{k}$ by the functional equation (claim 1 of Basic Properties of the Exponential Function, by induction on $k$, with $\exp(0)=1$) and because a nonnegative constant factor may be taken out of a sum of nonnegative terms (the least upper bound of the scaled partial sums being the scaled least upper bound). The last sum has nonnegative terms, so it equals the limit of the partial sums of the series $\sum_{k=0}^{\infty}(\mu\exp(\theta))^{k}/k!$, which is $\exp(\mu\exp(\theta))$ by The Real Exponential Function. Hence $\mathbb{E}[\exp(\theta K)]=\exp(-\mu)\exp(\mu\exp(\theta))=\exp(\mu(\exp(\theta)-1))$ by the functional equation, a finite number; a nonnegative random variable with finite expectation is integrable.

Claim 3. Two elementary inequalities. For real $\theta$ with $|\theta|\le1$,

$$\exp(\theta)-1-\theta\le\theta^{2}.\tag{3.1}$$

Indeed, by The Real Exponential Function and limit arithmetic, $\exp(\theta)-1-\theta=\lim_n\sum_{k=2}^{n}\theta^{k}/k!$, and $|\theta^{k}|/k!\le\theta^{2}/k!\le\theta^{2}\,2^{1-k}$ for $k\ge2$ (since $|\theta|\le1$ and $k!\ge2^{k-1}$, the latter by induction: $(k+1)!=(k+1)k!\ge2\cdot2^{k-1}$), so every partial sum is at most $\theta^{2}\sum_{k=2}^{n}2^{1-k}\le\theta^{2}$, and the bound passes to the limit by the comparison claim 1 of Order Properties of Limits of Real Sequences (against the constant sequence $\theta^{2}$). Second, for $\mu>0$ and $x>0$ there is $\theta\in[0,1]$ with

$$\mu\theta^{2}-\theta x\le-\varpi_\mu(x):\tag{3.2}$$

if $x\le2\mu$ take $\theta=x/(2\mu)\in(0,1]$, giving $\mu\theta^{2}-\theta x=x^{2}/(4\mu)-x^{2}/(2\mu)=-x^{2}/(4\mu)$, and here $x^{2}/(4\mu)\le x/2$, so $\varpi_\mu(x)=x^{2}/(4\mu)$; if $x>2\mu$ take $\theta=1$, giving $\mu-x<x/2-x=-x/2$, and here $x^{2}/(4\mu)>x/2$, so $\varpi_\mu(x)=x/2$.

Upper tail. Let $x>0$ and $\theta\in[0,1]$. Since $\exp$ is nondecreasing (claim 4 of Basic Properties of the Exponential Function) and $\theta\ge0$, the event $\{K\ge\mu+x\}$ is contained in $\{\exp(\theta K)\ge\exp(\theta(\mu+x))\}$, so by monotonicity of $P$ (claim 2 of Basic Properties of a Measure) and Markov's inequality applied to the nonnegative random variable $\exp(\theta K)$ and claim 2,

$$P(K\ge\mu+x)\le\frac{\exp(\mu(\exp(\theta)-1))}{\exp(\theta(\mu+x))}=\exp\bigl(\mu(\exp(\theta)-1-\theta)-\theta x\bigr)\le\exp\bigl(\mu\theta^{2}-\theta x\bigr),$$

using the functional equation, claim 2 of Basic Properties of the Exponential Function for the quotient, monotonicity of $\exp$, and (3.1). If $\mu>0$, choosing $\theta$ as in (3.2) and using monotonicity of $\exp$ gives $P(K\ge\mu+x)\le\exp(-\varpi_\mu(x))$. If $\mu=0$, then $P(K\ge x)=P_0([x,\infty))=0$ because $0\notin[x,\infty)$ (Poisson Distribution), and the bound holds trivially.

Lower tail. Let $x>0$ and $\eta\in[0,1]$. Since $u\mapsto\exp(-\eta u)$ is nonincreasing, $\{K\le\mu-x\}\subseteq\{\exp(-\eta K)\ge\exp(-\eta(\mu-x))\}$, and Markov's inequality with claim 2 (at $\theta=-\eta$) gives

$$P(K\le\mu-x)\le\exp\bigl(\mu(\exp(-\eta)-1)+\eta(\mu-x)\bigr)=\exp\bigl(\mu(\exp(-\eta)-1+\eta)-\eta x\bigr)\le\exp\bigl(\mu\eta^{2}-\eta x\bigr)$$

by (3.1) at $\theta=-\eta$. Choosing $\eta\in[0,1]$ as $\theta$ in (3.2) gives $P(K\le\mu-x)\le\exp(-\varpi_\mu(x))$ when $\mu>0$ (the containment of events again giving the inequality of probabilities by monotonicity of $P$); when $\mu=0$, $P(K\le-x)=P_0((-\infty,-x])=0$.

Two-sided bound and monotonicity. $\{|K-\mu|\ge x\}=\{K\ge\mu+x\}\cup\{K\le\mu-x\}$, so the two-sided bound follows from countable subadditivity of $P$ (claim 4 of Basic Properties of a Measure, applied to the sequence $\{K\ge\mu+x\},\{K\le\mu-x\},\emptyset,\emptyset,\dots$). Finally, if $0<\mu\le\bar\mu$ then $x^{2}/(4\mu)\ge x^{2}/(4\bar\mu)$, so $\varpi_\mu(x)\ge\varpi_{\bar\mu}(x)$; if $\mu=0<\bar\mu$ then $\varpi_0(x)=x/2\ge\varpi_{\bar\mu}(x)$; if $\mu=\bar\mu=0$ there is nothing to prove; and $\exp$ being nondecreasing, $\exp(-\varpi_\mu(x))\le\exp(-\varpi_{\bar\mu}(x))$.