= Entropy method (probability)
The <entropy method (probability)> proves concentration by controlling the entropy of an exponential of a <random variable>. For $Z\ge0$, define $\operatorname{Ent}(Z)=\mathbb E[Z\log Z]-\mathbb EZ\log\mathbb EZ$. If $F$ is the quantity of interest and $\psi(\lambda)=\log\mathbb E e^{\lambda F}$, then
$$
\frac{\operatorname{Ent}(e^{\lambda F})}{\mathbb E e^{\lambda F}}=\lambda\psi'(\lambda)-\psi(\lambda).
$$
An entropy bound is therefore a differential inequality for the log <moment-generating function>. If it gives $\operatorname{Ent}(e^{\lambda F})\le\tfrac12v\lambda^2\mathbb E e^{\lambda F}$ for all $\lambda>0$, integration yields $\log\mathbb E e^{\lambda(F-\mathbb EF)}\le v\lambda^2/2$. The <Chernoff bound> then gives $\mathbb P(F-\mathbb EF\ge t)\le e^{-t^2/(2v)}$ for $v>0$.
For a sum of independent unit <Gaussian random variables>, the log moment-generating function is exactly $n\lambda^2/2$, illustrating the scale $v=n$. The method's real power is that entropy can be controlled coordinate by coordinate for many nonlinear functions of independent inputs.<On concentration of self-bounding functions by Stéphane Boucheron and others>[Entropy method and tensorization argument]{ref}
Back to article page
