= Herbst argument
{c}
The <Herbst argument> converts an exponential <entropy functional> bound into a <concentration inequality>. Let $Z$ be a <random variable> whose <moment-generating function> is finite in a neighborhood of zero, and write $H(\lambda)=\log\mathbb Ee^{\lambda Z}$. Suppose for $0<\lambda<\lambda_0$ that
$$
\operatorname{Ent}(e^{\lambda Z})\leq\frac{v\lambda^2}{2}\mathbb Ee^{\lambda Z},\qquad v>0.
$$
Dividing by $\mathbb Ee^{\lambda Z}$ gives $\lambda H'(\lambda)-H(\lambda)\leq v\lambda^2/2$. Since $(H(\lambda)/\lambda)'=(\lambda H'-H)/\lambda^2$ and $H(\lambda)/\lambda\to\mathbb EZ$ at zero, integration yields
$$
\log\mathbb Ee^{\lambda(Z-\mathbb EZ)}\leq\frac{v\lambda^2}{2}.
$$
The <Chernoff bound> gives $\mathbb P(Z-\mathbb EZ\geq t)\leq e^{-t^2/(2v)}$ whenever the optimizing value $t/v$ lies below $\lambda_0$. A <modified logarithmic Sobolev inequality> is one way to supply the initial hypothesis. Applying the same calculation to $-Z$ controls the lower tail; an upper-tail hypothesis alone does not imply it.
Back to article page
