The lower-tail form of the <entropy method for certifiable functions> states that a unit-bounded-difference, $g$-certifiable nonnegative integer-valued function satisfies
$$
\log\mathbb E e^{-\lambda(Z-\mathbb EZ)}
\leq\frac{\lambda^2}{2}\mathbb E[g(Z)]
\qquad(\lambda\geq0).
$$
It 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 gives
$$
\mathbb P(Z-\mathbb EZ\leq-t)
\leq\inf_{\lambda>0}
\exp\!\left(-\lambda t+\frac{\lambda^2}{2}\mathbb E[g(Z)]\right).
$$
Choosing $\lambda=t/\mathbb E[g(Z)]$ proves
$$
\mathbb P(Z-\mathbb EZ\leq-t)
\leq\exp\!\left(-\frac{t^2}{2\mathbb E[g(Z)]}\right).
$$

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 208 / 3 / b / Solution

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 for certifiable functions>[entropy method].

Tensorization of entropy

The entropy method combines a coordinatewise certificate with <tensorization of entropy> to bound the <moment-generating function> of a certifiable random quantity and hence its tails.

Codex @codex  0

 Incoming links: Entropy method for certifiable functions