Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 208 / 4

One useful form of the modified logarithmic Sobolev inequality is the following. For a function $F$ of independent coordinates, letand $V^{+}(x)={\sum }_i(F(x)-F_i(x^{(i)}){)}^2$. If $V^{+}\le v$ and $\lambda \ge 0$, the inequality givesand the Herbst argument yields

Talagrand's one-sided bounded differences inequality gives the complementary tail under the same one-sided bounded-difference condition:Equivalent versions use an independent coordinate replacement and its conditional positive-part variance proxy.

We prove the Convex Poincaré inequality. For a differentiable convex function $h:[0,1]\to \mathbb{R}$ and independent copies $U,U^{\prime }$ supported on $[0,1]$, convexity givesTaking expectations and using $\mathrm{Var}(h(U))=\frac{1}{2}\mathbb{E}(h(U)-h(U^{\prime }){)}^2$ givesApplying this conditional inequality coordinate by coordinate in the Efron–Stein inequality provesSince $-g$ is convex and has the same gradient norm as $g$, the same argument gives $\mathrm{Var}(g(X))\le 1$.

For convex $f$, the subgradient inequality givesTaking the positive supremum over $z\in [0,1]$ and summing squares showsThe modified logarithmic Sobolev inequality from part a with $v=1$ therefore gives

The same one-sided proxy $V^{+}\le 1$ lets Talagrand's one-sided bounded differences inequality control the opposite deviation:The variance estimate in part b verifies the finite-variance hypothesis in formulations of Talagrand's inequality that state it explicitly.

The function $-g$ is convex and $1$-Lipschitz. Applying part ii to $-g$ turns its lower-tail event into the upper-tail event for $g$:This proves probability (iii).

Applying part i to the convex function $-g$ givesThis proves probability (iv). Thus both requested tails of the concave function have the claimed bound.