[proofplan] We first compute the moment generating function of the Poisson [random variable](/page/Random%20Variable) directly from its probability mass function. Then we prove the exponential Markov estimate in the two forms needed for the upper and lower tails. Choosing the exponential parameter that minimizes the resulting bound gives the upper-tail estimate with $\lambda=\log(1+\delta)$ and the lower-tail estimate with $\lambda=\log(1-\delta)$. [/proofplan]

[step:Compute the moment generating function of the Poisson variable] For each $k \in \mathbb{N}\cup\{0\}$, the Poisson distribution assumption gives \begin{align*} \mathbb{P}(X=k)=e^{-\mu}\frac{\mu^k}{k!}. \end{align*} Define the moment generating function $M_X$ as the map \begin{align*} M_X:\mathbb{R}\to (0,\infty). \end{align*} For $\lambda\in\mathbb{R}$, its value is \begin{align*} M_X(\lambda)=\mathbb{E}[e^{\lambda X}]. \end{align*} For every $\lambda \in \mathbb{R}$, since $e^{\lambda X}$ is non-negative, its expectation is computed from the probability mass function as follows. First, \begin{align*} M_X(\lambda)=\sum_{k=0}^{\infty} e^{\lambda k}\mathbb{P}(X=k). \end{align*} Substituting the Poisson mass function gives \begin{align*} M_X(\lambda)=\sum_{k=0}^{\infty} e^{\lambda k}e^{-\mu}\frac{\mu^k}{k!}. \end{align*} Factoring out $e^{-\mu}$ and combining powers gives \begin{align*} M_X(\lambda)=e^{-\mu}\sum_{k=0}^{\infty}\frac{(\mu e^\lambda)^k}{k!}. \end{align*} Using the exponential [power series](/page/Power%20Series) at $\mu e^\lambda$ gives \begin{align*} M_X(\lambda)=e^{-\mu}e^{\mu e^\lambda}. \end{align*} Therefore \begin{align*} M_X(\lambda)=\exp\{\mu(e^\lambda-1)\}. \end{align*} [/step]

[step:Convert tail events into exponential moment bounds]Let $a>0$ and let $\lambda>0$. On the event $\{X\geq a\}$, the monotonicity of $t\mapsto e^{\lambda t}$ gives $e^{\lambda X}\geq e^{\lambda a}$, hence \begin{align*} \mathbb{1}_{\{X\geq a\}} \leq e^{\lambda(X-a)}. \end{align*} Taking expectations gives \begin{align*} \mathbb{P}(X\geq a) = \mathbb{E}[\mathbb{1}_{\{X\geq a\}}] \leq e^{-\lambda a}\mathbb{E}[e^{\lambda X}] = \exp\{-\lambda a+\mu(e^\lambda-1)\}. \end{align*} Similarly, let $b>0$ and let $\lambda<0$. On the event $\{X\leq b\}$, the map $t\mapsto e^{\lambda t}$ is decreasing, so $e^{\lambda X}\geq e^{\lambda b}$. Therefore \begin{align*} \mathbb{1}_{\{X\leq b\}} \leq e^{\lambda(X-b)}. \end{align*} Taking expectations gives \begin{align*} \mathbb{P}(X\leq b) \leq e^{-\lambda b}\mathbb{E}[e^{\lambda X}] = \exp\{-\lambda b+\mu(e^\lambda-1)\}. \end{align*}[/step]

[guided]The basic idea is to replace the tail event by an exponential random variable, because exponential functions turn sums and Poisson probabilities into expressions that can be optimized. First fix $a>0$ and $\lambda>0$. Since $t\mapsto e^{\lambda t}$ is increasing, whenever $X\geq a$ we have $e^{\lambda X}\geq e^{\lambda a}$. Equivalently, \begin{align*} e^{\lambda(X-a)}\geq 1 \end{align*} on the event $\{X\geq a\}$. Outside that event, the indicator $\mathbb{1}_{\{X\geq a\}}$ is $0$, while $e^{\lambda(X-a)}$ remains non-negative. Thus the pointwise inequality \begin{align*} \mathbb{1}_{\{X\geq a\}} \leq e^{\lambda(X-a)} \end{align*} holds on all of $\Omega$. Taking expectations with respect to $\mathbb{P}$ yields \begin{align*} \mathbb{P}(X\geq a) = \mathbb{E}[\mathbb{1}_{\{X\geq a\}}] \leq \mathbb{E}[e^{\lambda(X-a)}] = e^{-\lambda a}\mathbb{E}[e^{\lambda X}]. \end{align*} Using the moment generating function computed above, \begin{align*} \mathbb{E}[e^{\lambda X}] = \exp\{\mu(e^\lambda-1)\}, \end{align*} so \begin{align*} \mathbb{P}(X\geq a) \leq \exp\{-\lambda a+\mu(e^\lambda-1)\}. \end{align*} For the lower tail, the sign of $\lambda$ must be reversed. Fix $b>0$ and $\lambda<0$. Now $t\mapsto e^{\lambda t}$ is decreasing, so on the event $\{X\leq b\}$ we have $e^{\lambda X}\geq e^{\lambda b}$. Hence \begin{align*} e^{\lambda(X-b)}\geq 1 \end{align*} on $\{X\leq b\}$, and the same indicator comparison gives \begin{align*} \mathbb{1}_{\{X\leq b\}} \leq e^{\lambda(X-b)}. \end{align*} Taking expectations and substituting the moment generating function gives \begin{align*} \mathbb{P}(X\leq b) \leq e^{-\lambda b}\mathbb{E}[e^{\lambda X}] = \exp\{-\lambda b+\mu(e^\lambda-1)\}. \end{align*} The only difference between the two tails is the sign restriction on $\lambda$: positive $\lambda$ emphasizes large values of $X$, while negative $\lambda$ emphasizes small values of $X$.[/guided]

[step:Choose the optimizing parameter for the upper tail] Let $\delta>0$ and set \begin{align*} a=(1+\delta)\mu, \qquad \lambda=\log(1+\delta). \end{align*} Since $\delta>0$, we have $\lambda>0$, so the upper-tail exponential bound applies. Substituting $e^\lambda=1+\delta$ gives \begin{align*} \mathbb{P}\bigl(X\geq (1+\delta)\mu\bigr)\leq \exp\{-\lambda(1+\delta)\mu+\mu(e^\lambda-1)\}. \end{align*} Since $\lambda=\log(1+\delta)$ and $e^\lambda=1+\delta$, this becomes \begin{align*} \mathbb{P}\bigl(X\geq (1+\delta)\mu\bigr)\leq \exp\{-(1+\delta)\mu\log(1+\delta)+\mu\delta\}. \end{align*} Factoring out $\mu$ from the exponent gives \begin{align*} \mathbb{P}\bigl(X\geq (1+\delta)\mu\bigr)\leq \exp\{\mu(\delta-(1+\delta)\log(1+\delta))\}. \end{align*} Rewriting the exponential as a power gives \begin{align*} \mathbb{P}\bigl(X\geq (1+\delta)\mu\bigr)\leq \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu. \end{align*} This proves the upper-tail bound. [/step]

[step:Choose the optimizing parameter for the lower tail] Let $\delta\in(0,1)$ and set \begin{align*} b=(1-\delta)\mu, \qquad \lambda=\log(1-\delta). \end{align*} Since $\delta\in(0,1)$, we have $1-\delta\in(0,1)$ and therefore $\lambda<0$, so the lower-tail exponential bound applies. Substituting $e^\lambda=1-\delta$ gives \begin{align*} \mathbb{P}\bigl(X\leq (1-\delta)\mu\bigr)\leq \exp\{-\lambda(1-\delta)\mu+\mu(e^\lambda-1)\}. \end{align*} Since $\lambda=\log(1-\delta)$ and $e^\lambda=1-\delta$, this becomes \begin{align*} \mathbb{P}\bigl(X\leq (1-\delta)\mu\bigr)\leq \exp\{-(1-\delta)\mu\log(1-\delta)-\mu\delta\}. \end{align*} Factoring out $\mu$ from the exponent gives \begin{align*} \mathbb{P}\bigl(X\leq (1-\delta)\mu\bigr)\leq \exp\{\mu(-\delta-(1-\delta)\log(1-\delta))\}. \end{align*} Rewriting the exponential as a power gives \begin{align*} \mathbb{P}\bigl(X\leq (1-\delta)\mu\bigr)\leq \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu. \end{align*} This proves the lower-tail bound and completes the proof. [/step]