Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 208 (Concentration Inequalities)

Because the moment-generating function is finite in a neighborhood to the right of zero and $\mathbb{E}X=0$, its cumulant-generating function satisfiesDivide the defining Sub-Gamma random variable in the right tail inequality by ${\lambda }^2/2$ and let $\lambda \downarrow 0$. The right side converges to $\nu$, proving $\mathrm{Var}(X)\le \nu$.

Independence makes cumulant-generating functions additive:SetFor $0<\lambda <1/c$, every denominator is positive and $1-c_i\lambda \ge 1-c\lambda$, soAlso $\mathbb{E}Z=0$, and hence $Z\in {\Gamma }_{+}(\nu ,c)$.

The Chernoff bound gives, for $0<\lambda <1/c$,Writing $u=ct/\nu$, elementary differentiation shows that the exponent is minimized atSubstitution givesThus $h$ is the Legendre transform generated by the sub-Gamma cumulant bound after its natural rescaling.

Put $x=\sqrt{2\nu t}+ct$ and $y=c^{2}t/\nu$. ThenConsequentlyThe tail bound from part c therefore has exponent $-(\nu /c^2)y=-t$, and

For $X^{(i)}=X_{1:n}\setminus X_i$, Han's inequality for relative entropy states that, when $P={⨂}_{i=1}^n{P}_i$,

First prove the chain rule for relative entropy. For two coordinates,Taking expectation under $Q$ givesand iteration proves the chain rule for any finite product.

Write $Q_i(\cdot \mid x_{<i})$ for the successive conditional distributions. Since $P$ is a product, the chain rule givesFor a fixed omitted coordinate $j$, applying the chain rule in the remaining coordinate order givesThe convexity of Kullback-Leibler divergence implies that removing $X_j$ from the conditioning can only decrease each averaged conditional divergence. Summing over $j$, each full conditional increment occurs for exactly the $n-1$ indices $j\ne i$, and thereforewhich is the claimed inequality. Equivalently, this is Han's entropy inequality after expanding each divergence: the product-reference cross-entropy terms cancel because they are modular.

Define the tilted probability measure $Q$ by $dQ=ZdP$; this is normalized because $\mathbb{E}Z=1$. ThenLet ${\mathbb{E}}_i$ average only coordinate $i$, keeping $X^{(i)}$ fixed. The marginal density of $Q_{X^{(i)}}$ relative to $P_{X^{(i)}}$ is ${\mathbb{E}}_{i}Z$, and henceMoreover,Substituting Han's inequality for relative entropy and rearranging gives the tensorization of entropy

The chain rule, now separating $X_i$ first, giveswhere the second term denotes the conditional divergence averaged over $Q_{X_i}$. Summing over $i$ yieldsRepeated use of the chain rule and convexity gives the tensorization lower bound for relative entropyTherefore the preceding sum is at least $(n-1)D(Q\Vert P)$, which is equivalent to the required inequality.

Again put $dQ=ZdP$. With ${\mathbb{E}}^{[i]}Z=\mathbb{E}[Z\mid X_i]$, the conditional density of $Q_{X^{(i)}\mid X_i}$ relative to $P_{X^{(i)}}$ is $Z/{\mathbb{E}}^{[i]}Z$. ConsequentlyPart c now gives the alternative tensorization boundUnlike the bound in part b, each summand averages over all coordinates other than $i$ while holding $X_i$ fixed.

Yes. Write $D_S=D(Q_{X_S}\Vert P_{X_S})$ and $D=D_{\{1,\dots ,n\}}$. The bounds from b and d are respectivelyThe Strong form of Han's entropy inequality, obtained by repeated entropy submodularity, statesAfter replacing entropies by divergences from the product reference, whose cross-entropy terms cancel, this is exactly $B_{\mathrm{new}}\le B_{\mathrm{old}}$. Equality holds for product $Q$ and when $n=2$; dependence can make the new bound strictly smaller.

The Gaussian logarithmic Sobolev inequality says that for standard Gaussian $X\in {\mathbb{R}}^n$ and smooth $u$,Apply it to $u=\sqrt{f}$. Since $\nabla \sqrt{f}=\nabla f/(2\sqrt{f})$,This sharp inequality immediately implies the requested weaker bound with constant $2$.

For $k\ge 0$, take $f_k(x)=1_{\{x\ge k+1\}}$ and write $q_k=\mathbb{P}(X\ge k+1)$. Since $f_k^2=f_k$,Its discrete derivative is nonzero only at $k$, soFor a Poisson distribution, $p_{k+1}/p_k=\lambda /(k+1)$ and $q_k\sim p_{k+1}$ as $k\to \infty$. Hencewhere the final estimate follows from Stirling formula. No finite constant $C$ can therefore make the proposed inequality hold for every $f$.

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be independent $\mathrm{Bernoulli}(\lambda /n)$ variables and $S_n={\sum }_i{\epsilon }_i$. Apply the tensorization of entropy to $f(S_n)$ and then apply the stated Bernoulli log-Sobolev inequality in each coordinate. If $S_n^{(i)}=S_n-{\epsilon }_i$, this givesFor each fixed $i$, $(S_n^{(i)},{\epsilon }_i)$ converges in distribution to $(X,0)$, where $X\sim \mathrm{Poisson}(\lambda )$. The Poisson limit theorem in fact gives convergence in total variation. The assumptions $K_1\le f\le K_2$ and $|Df|\le K_3$ make all displayed integrands bounded, so expectations and entropy pass to the limit. Since $n(\lambda /n)(1-\lambda /n)\to \lambda$,

Put $Y=g(X)-\mathbb{E}g(X)$ and $H(\lambda )=\log \mathbb{E}{e}^{\lambda Y}$. Apply the assumed Poisson log-Sobolev inequality to $f=e^{\lambda g}$. Since $|Dg|\le 1$ and $|e^a-1|\le \lambda e^{\lambda }$ for $|a|\le \lambda$,After division by $\mathbb{E}{e}^{\lambda g}$, the entropy bound becomesBecause $(H(\lambda )/\lambda {)}^{\prime }=(\lambda H^{\prime }-H)/{\lambda }^2$ and $H^{\prime }(0)=0$, integration from $0$ to $\lambda$ givesThe Chernoff bound and optimization over $\lambda \ge 0$ therefore yieldwhere ${\psi }^{\ast }$ is the Legendre transform of a cumulant-generating function, also called the Chernoff-Cramér transform.

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.