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

Solution

The lower-tail form of the entropy method for certifiable functions states that a unit-bounded-difference,

g

-certifiable nonnegative integer-valued function satisfies

lo g E e^{- λ (Z - E Z)} \leq \frac{λ ^{2}}{2} E [g (Z)] (λ \geq 0) .

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

P (Z - E Z \leq - t) \leq in f_{λ > 0} exp (- λ t + \frac{λ ^{2}}{2} E [g (Z)]) .

Choosing

λ = t / E [g (Z)]

proves

P (Z - E Z \leq - t) \leq exp (- \frac{t ^{2}}{2 E [ g ( Z )]}) .

There are no discussions about this article yet.

There are currently no matching articles.