= Solution
Let $S=\sum_iY_i$ and $V_H=\sum_i(b_i-a_i)^2$. To prove the <Hoeffding lemma>, take a centered <random variable> $Y\in[a,b]$ and its <cumulant-generating function> $\psi(t)=\log\mathbb E e^{tY}$. Under <exponential tilting>, $\psi''(t)$ is the <variance> of $Y$. The <Popoviciu inequality on variances> gives
$$
\psi''(t)\leq\frac{(b-a)^2}{4},
$$
since under any such tilt the support remains $[a,b]$, and $\operatorname{Var}(Y)\leq\mathbb E(Y-(a+b)/2)^2\leq(b-a)^2/4$. Because $\psi(0)=\psi'(0)=0$, integrating twice gives $\psi(t)\leq t^2(b-a)^2/8$ for $t\geq0$; applying the same argument to $-Y$ handles the opposite tail.
The <independence> of the $Y_i$ gives $\mathbb E e^{tS}\leq\exp(t^2V_H/8)$. The <Markov inequality>, in the <Chernoff bound> argument, yields
$$
\mathbb P(S>\epsilon)\leq\inf_{t>0}\exp\left(-t\epsilon+\frac{t^2V_H}{8}\right)
=\exp\left(-\frac{2\epsilon^2}{V_H}\right),
$$
where the minimum is at $t=4\epsilon/V_H$ when $V_H>0$. Apply the same argument to $-S$ and add the bounds to obtain the <Hoeffding inequality>:
$$
\boxed{\mathbb P(|S|>\epsilon)\leq2\exp\left(-\frac{2\epsilon^2}{\sum_i(b_i-a_i)^2}\right).}
$$
If $V_H=0$, every centered $Y_i$ is identically zero and the tail probability is zero; the displayed exponential is interpreted by its zero-variance limit.
For the <Bennett inequality>, write $v=n\sigma^2$, and first assume $M>0$ and $v>0$. For $j\geq2$, boundedness and centering give
$$
\mathbb E Y_i^j\leq\mathbb E|Y_i|^j\leq M^{j-2}\mathbb EY_i^2\leq\sigma^2M^{j-2}.
$$
For $t\geq0$, expanding the <moment-generating function> and using the permitted interchange of sum and <expected value>,
$$
\begin{aligned}
\mathbb E e^{tY_i}
&=1+\sum_{j=2}^\infty\frac{t^j\mathbb EY_i^j}{j!}\\
&\leq1+\frac{\sigma^2}{M^2}(e^{tM}-1-tM)\\
&\leq\exp\left(\frac{\sigma^2}{M^2}(e^{tM}-1-tM)\right).
\end{aligned}
$$
Negative odd <moments> cause no difficulty because the estimate is an upper bound term by term. The <independence> of the $Y_i$ and the <Chernoff bound> then give
$$
\mathbb P(S>\epsilon)\leq
\inf_{t>0}\exp\left[-t\epsilon+\frac v{M^2}(e^{tM}-1-tM)\right].
$$
The derivative vanishes at $t_*=M^{-1}\log(1+M\epsilon/v)$, and substitution gives $-(v/M^2)\phi(M\epsilon/v)$ with the <Bennett rate function> $\phi(u)=(1+u)\log(1+u)-u$. The same absolute bounds apply to $-Y_i$, so
$$
\boxed{\mathbb P(|S|>\epsilon)\leq2\exp\left[-\frac{n\sigma^2}{M^2}\phi\left(\frac{M\epsilon}{n\sigma^2}\right)\right].}
$$
If $\sigma^2=0$, all centered $Y_i$ are zero <almost surely>; if $M=0$, the same is immediate. Handle those cases directly rather than divide by zero. Both derived <concentration inequalities> also hold with $\geq\epsilon$, by the same <Markov inequality> argument or by letting a smaller positive threshold increase to $\epsilon$.
For the <binomial distribution>, write $X=\sum_{i=1}^nZ_i$ with <independent and identically distributed random variables> $Z_i$ having the <Bernoulli distribution> with parameter $p=p_n$. Then $Y_i=Z_i-p$ has range $[-p,1-p]$, width one, and <variance> $p(1-p)$. For large $n$, $p<1/2$, so $M=1-p$ and $v=np(1-p)$. Set $\epsilon=C\sqrt v$.
The <Hoeffding inequality> gives
$$
H_n=2\exp[-2C^2p(1-p)]\longrightarrow2.
$$
After truncation at one, this is asymptotically the trivial probability bound. The <Bennett inequality> instead gives
$$
B_n=2\exp\left[-\frac v{(1-p)^2}\phi\left(\frac{C(1-p)}{\sqrt v}\right)\right].
$$
Since $v\to\infty$ and $\phi(u)=u^2/2+O(u^3)$ by a <Taylor expansion>,
$$
\frac v{(1-p)^2}\phi\left(\frac{C(1-p)}{\sqrt v}\right)
=\frac{C^2}{2}+O(v^{-1/2})\longrightarrow\frac{C^2}{2}.
$$
Thus the <Bennett bounds for sparse binomial fluctuations> yield
$$
\boxed{B_n\longrightarrow2e^{-C^2/2},\qquad H_n\longrightarrow2.}
$$
\b[The <Bennett inequality> supplies the smaller raw exponential bound for every fixed $C>0$ and all sufficiently large $n$.] If $C\leq\sqrt{2\log2}$, clipping probability upper bounds at one makes both eventually trivial; for $C>\sqrt{2\log2}$, the <Bennett inequality> retains a nontrivial limiting bound. This distinction avoids claiming a probability improvement after clipping when both raw bounds exceed one.
Back to article page
