Bennett inequality

Let $X_1,\dots ,X_n$ be independent random variables with zero expected value, $X_i\le b$ almost surely for $b>0$, and ${\sum }_i\mathbb{E}{X}_i^2\le v$ for $v>0$. For $t\ge 0$, the Bennett inequality statesOnly an upper bound on each $X_i$ is needed for this upper tail. Apply the same result to $-X_i$ for a lower tail when the corresponding lower bounds are available.

To see the exponent, for $\lambda \ge 0$ the pointwise boundfollows because $(e^u-1-u)/u^2={\int }_0^1(1-s)e^{su}ds$ is increasing in $u$. Taking expected values, using $1+z\le e^z$, and multiplying by independence bounds the moment-generating function of the sum by $\exp [v(e^{\lambda b}-1-\lambda b)/b^2]$. The Chernoff bound is optimized at $\lambda =b^{-1}\log (1+bt/v)$, giving the result. The Bennett rate function is approximately quadratic for small deviations, with a stronger large-deviation shape than its quadratic approximation. If the total variance is zero, all centered variables vanish almost surely and the positive tail is zero.

For a binomial distribution with $p_n\to 0$ and $n{p}_n\to \infty$, the Bennett inequality at $C$ standard deviations tends to $2e^{-C^2/2}$, whereas the Hoeffding inequality tends to two. The raw Bennett inequality bound is eventually smaller for any fixed $C>0$; after clipping at one it is nontrivial in the limit only when $C>\sqrt{2\log 2}$.

The Bennett rate function has Taylor expansion $\varphi (u)=u^2/2-u^3/6+O(u^4)$ near zero. It is the optimized exponent in the Chernoff bound based on the moment-generating function estimate for the Bennett inequality.