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

Hoeffding lemma states that if $a\le X\le b$ almost surely, then for every real $\lambda$,Convexity of $e^{\lambda x}$ bounds it on $[a,b]$ by the secant joining its endpoint values. Taking expectations reduces the centered moment-generating function to that of a two-point variable on $\{a,b\}$ having the same mean. After rescaling to $[0,1]$, its logarithm iswhere $q$ is its mean. Twice differentiating in $\lambda$ shows that the second derivative is a Bernoulli variance and hence at most $1/4$. The value and first derivative vanish at zero, so Taylor's theorem gives at most ${\lambda }^2/8$. Rescaling proves the claim.

For $X\sim \mathrm{Bernoulli}(p)$,The inequality $-\log (1-p)\le p/(1-p)$ bounds the second term by $p$. Also $\log x\le 2\sqrt{x}$ for $x\ge 1$, so $p\log (1/p)\le 2\sqrt{p}$. Hence

Put $q_i=\min (p_i,1-p_i)$. Applying part (b) after possibly replacing $X_i$ by $1-X_i$ gives $H(X_i)\le 2\sqrt{q_i}+q_i$. If $q_i<{\delta }_i$, then, because $0<{\delta }_i<1$, this is less than $3\sqrt{{\delta }_i}$, contradicting the assumption. Thus $p_i,1-p_i\ge {\delta }_i$.

The centered variablesare independent and have mean zero. Their two possible values differ byApplying Hoeffding inequality to ${\sum }_i{Y}_i$ gives

Independence makes varentropy additive. For a Bernoulli variable,Part (c) bounds the logarithm by $|\log {\delta }_i|$, while $p_i(1-p_i)\le 1/4$. Therefore

Apply the Poincaré inequality in probability theory to $g=e^{\lambda f/2}$. Since $\Vert \nabla f\Vert \le 1$,HenceIterating this estimate $m$ times yieldsvalid under the stated bound on $\lambda$.

Since $\mathbb{E}f(X)=0$ and the moment-generating function is finite near zero, $\log F(u)=O(u^2)$. Consequentlywhich proves $F(\lambda /2^m{)}^{2^m}\to 1$.

For ${\lambda }_{\ast }=C_P(X{)}^{-1/2}$, part (a) and the elementary bound $-\log (1-x)\le 4x/3$ for $0\le x\le 1/4$ giveThus $F({\lambda }_{\ast })\le 3$.

The Chernoff bound and part (b) giveApply the same argument to $-f$ and use the union bound to obtain

Subtract a constant so that $f(0)=0$, and write $m=\mathbb{E}f(Y)$, $V=\mathrm{Var}f(Y)$, and $A=\mathbb{E}{f}^{\prime }(Y{)}^2$. The supplied identity applied to $f$ and $f^2$ givesBy Cauchy-Schwarz inequality, $m^2\le A$ andThus $V+m^2\le 2\sqrt{(V+m^2)A}$, so $V+m^2\le 4A$ and in particular $V\le 4A$. Therefore the standard Laplace distribution has $C_P(Y)\le 4$.

For standard Gaussian measure $\gamma$, the Gaussian Poincaré inequality isThe Gaussian logarithmic Sobolev inequality iswhere ${\mathrm{Ent}}_{\gamma }(G)=\int G\log Gd\gamma -(\int Gd\gamma )\log \int Gd\gamma$.

Set $h=\sqrt{f/\varphi }$. Then $\int h^{2}d\gamma =1$ andMoreover,The Gaussian logarithmic Sobolev inequality therefore gives

With the same $h$, the squared Hellinger distance isSince $0\le \int hd\gamma \le 1$,The Gaussian Poincaré inequality and the derivative calculation in part (b) yield

Write $W=Z-\mathbb{E}Z$ and $\psi (\lambda )=\log {\mathbb{E}}_P{e}^{\lambda W}$. For any $Q\ll P$ and real $\lambda$, define the exponential tiltPositivity of relative entropy givesThus every $Q$ with ${\mathbb{E}}_{Q}W\ge t$ has $D(Q\Vert P)\ge {\sup }_{\lambda \ge 0}\{\lambda t-\psi (\lambda )\}={\psi }^{\ast }(t)$.

For $0<t<b$, continuity of ${\psi }^{\prime }$ supplies ${\lambda }_t>0$ with ${\psi }^{\prime }({\lambda }_t)=t$. Under $P_{{\lambda }_t}$, $\mathbb{E}W=t$, and direct substitution givesThis tilt attains the constrained infimum and proves the identity.

For any coupling $\pi$ of $X\sim P$ and $Y\sim Q$ and every $A\subseteq \Omega$,Its absolute value is at most ${\mathbb{P}}_{\pi }(X\ne Y)$. Taking the supremum over $A$ and then the infimum over couplings proves

For each $i$, the total variation distance between $\mathrm{Bernoulli}(p_i)$ and $\mathrm{Poisson}(p_i)$ isIndeed, compare their masses at zero, one, and the Poisson tail; the positive excess of Bernoulli mass at one is $p_i(1-e^{-p_i})$. A maximal coupling therefore gives a pair $(X_i,N_i)$ with mismatch probability at most $p_i^2$. Couple these pairs independently. Thenby the union bound. Since ${\sum }_i{N}_i\sim \mathrm{Poisson}({\sum }_i{p}_i)=\mathrm{Poisson}(\nu )$, part (b) yields