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

Disintegrate $Q$ successively asFor each history $y_{<i}$, choose an optimal coupling of $P_i$ and $Q_i(\cdot \mid y_{<i})$. Sampling these couplings recursively produces a joint law of $(X,Y)$ with $Y\sim Q$. Its conditional $X_i$-marginal is always $P_i$ and is independent of the past, so $X\sim P_1\otimes \cdots \otimes P_N=P$. It is therefore a coupling $\pi \in \Pi (P,Q)$.

Write $c_i(y_{<i})$ for the conditional expected cost $w(X_i,Y_i)$ in the chosen coordinate coupling. The assumed one-coordinate transport-entropy inequality givesBy Jensen inequality and the chain rule for relative entropy,Taking the infimum over all couplings proves the tensorization of a transport-entropy inequality.

Solved by gpt-5.6-sol high.

Put $\mu =\mathbb{E}Z$ and $h(u)=(1+u)\log (1+u)-u$. For $\lambda >0$, the Chernoff bound and the assumed cumulant-generating-function estimate giveThe optimizer satisfies $e^{\lambda }=1+t/\mu$, and hence

For the left tail, apply the same argument at a negative parameter. If $0<t<\mu$ the optimizer satisfies $e^{-\lambda }=1-t/\mu$, givingFor $t\ge \mu$, nonnegativity of $Z$ makes the strict lower-tail event empty, with the boundary handled directly.

Solved by gpt-5.6-sol high.

Let $d_i=f(X)-f_i(X^{(i)})$. The self-bounding function assumptions say $0\le d_i\le 1$ and ${\sum }_i{d}_i\le Z$. Apply tensorization of entropy to $e^{\lambda Z}$ and the one-coordinate entropy inequality. Since $\phi (u)=e^u-u-1$ is convex and $\phi (td)\le d\phi (t)$ for $0\le d\le 1$, the resulting bound is

Writing $\psi (\lambda )=\log \mathbb{E}{e}^{\lambda (Z-\mu )}$ and dividing by the moment-generating function reduces this toBoth sides have finite limits at zero and $\psi (0)={\psi }^{\prime }(0)=0$. Integrating from zero to $\lambda$, with the direction interpreted correctly when $\lambda <0$, yieldswhich is the required inequality.

Solved by gpt-5.6-sol high.

The bounded differences property with $c_i=1$ means that changing only coordinate $i$ changes $f$ by at most one:whenever $x_j=x_j^{\prime }$ for all $j\ne i$.

The function is $g$-certifiable when, whenever $f(x)=k$, there is a coordinate set $I$ with $|I|\le g(k)$ such that every $y$ agreeing with $x$ on $I$ satisfies $f(y)\ge k$. The coordinates in $I$ form a certificate for the assertion that the value is at least $k$.

Solved by gpt-5.6-sol high.

The lower-tail form of the entropy method for certifiable functions states that a unit-bounded-difference, $g$-certifiable nonnegative integer-valued function satisfiesIt 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 givesChoosing $\lambda =t/\mathbb{E}[g(Z)]$ proves

Solved by gpt-5.6-sol high.

There are $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ independent edge indicators. Conditional on all indicators except one, changing that edge changes the maximum matching number by at most one. The conditional range is therefore at most one, so Popoviciu inequality on variances bounds each conditional variance by $1/4$. The tensorized conditional-variance inequality gives

Solved by gpt-5.6-sol high.

The same edge exposure shows that $f$ has bounded differences constants $c_e=1$ for its $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ independent inputs. McDiarmid inequality therefore gives both one-sided bounds

Solved by gpt-5.6-sol high.

Group the edge indicators into $n-1$ independent blocksAll edges in one block share vertex $i$. Replacing the entire block can change the maximum matching number by at most one: after deleting the at most one matched edge incident to $i$, a matching from either graph remains valid in the other. Applying McDiarmid inequality to these $n-1$ blocks gives

Solved by gpt-5.6-sol high.

Part (a) only gives a standard-deviation scale of order $n$, and part (b) gives the same concentration scale. Part (c) improves this to order $\sqrt{n}$. When $p=n^{-3/2}$, however, the mean itself is of order $\sqrt{n}$, so even part (c) does not show that fluctuations are little-$o$ of the mean. None of these bounds reveals the natural $n^{1/4}$ fluctuation scale obtained below.

Solved by gpt-5.6-sol high.

As a function of the independent edge indicators, the maximum matching number is unit-Lipschitz. The event $f(G)\ge k$ is certified by exhibiting the $k$ present edges of a matching, so $f$ is $g(k)=k$ certifiable. The Talagrand concentration inequality for certifiable functions around a median $M$ gives, for universal constants in the displayed standard version,Here $M\asymp \sqrt{n}$. If $t/n^{1/4}\to \infty$, then $t^2/(M+t)\to \infty$, as does $t^2/M$ whenever the corresponding event is possible. Both tail probabilities therefore tend to zero. Thus deviations of any order larger than $n^{1/4}$ are unlikely.

Solved by gpt-5.6-sol high.