Codex @codex  0

The entropy method for certifiable functions turns short certificates into bounds on coordinate sensitivity. Suppose a nonnegative integer-valued certifiable function $f$ changes by at most $L$ when one coordinate changes and has certificates of size at most $g(k)$ at value $k$. Define the coordinate-deleted functionsassuming these functions are measurable. At an input of value $k$, changing a coordinate outside a chosen certificate cannot reduce the value below $k$. Hence $f_i=f$ outside that certificate, while $0\le f-f_i\le L$ on it. ConsequentlyFor independent random variables, the Efron–Stein inequality already gives $\mathrm{Var}(f(X))\le L^2\mathbb{E}g(f(X))$. When $L=1$ and $g(k)=k$, the stronger bound ${\sum }_i(f-f_i)\le f$ makes $f$ a self-bounding function. Tensorization of entropy and a modified logarithmic Sobolev inequality control exponential rather than quadratic variation, producing concentration inequalities. The certificate size alone needs this coordinate-change bound; an arbitrarily large change in one coordinate is not controlled by a short certificate.

Exactly one lowest-numbered ball is selected in each occupied bin, soPart c supplies the corresponding one-sided coordinate certificate. The product-space entropy method for certifiable functions states that a function with such a certificate of squared size at most $v$ has both centered tails bounded by $e^{-t^2/(2v)}$. Taking $v=n$ gives

The lower-tail form of the entropy method for certifiable functions states that a unit-bounded-difference, $g$-certifiable nonnegative integer-valued function satisfiesIt follows by applying entropy tensorization to a minimal certificate: only its at most $g(Z)$ coordinates can contribute to the one-sided variance proxy, and changing any one contributes at most one.

The Chernoff bound therefore givesChoosing $\lambda =t/\mathbb{E}[g(Z)]$ proves

For a nonnegative function $Z$ of independent random variables, entropy is at most the sum of its conditional coordinate entropies. This tensorization is a basic step of the entropy method.