{c}
{wiki=McDiarmid's_inequality}

If $X_1,\ldots,X_n$ are <independent random variables> and $f$ has <bounded differences property>[bounded differences] constants $c_i$, then
$$
\mathbb P\bigl(f(X)-\mathbb Ef(X)\geq t\bigr)
\leq\exp\left(-\frac{2t^2}{\sum_i c_i^2}\right),
$$
and the same bound holds for the lower tail.

McDiarmid inequality

The <bounded differences property> with $c_i=1$ means that changing only coordinate $i$ changes $f$ by at most one:
$$
|f(x)-f(x')|\leq1
$$
whenever $x_j=x'_j$ for all $j\ne i$.

The function is $g$-<certifiable function>[certifiable] when, whenever $f(x)=k$, there is a coordinate set $I$ with $|I|\leq g(k)$ such that every $y$ agreeing with $x$ on $I$ satisfies $f(y)\geq 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.

Solution

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

{c}
{wiki=Talagrand's_concentration_inequality}

Talagrand's product-space inequality gives sub-Gaussian-type concentration for a <bounded differences property>[bounded-differences], <certifiable function>, with a variance scale controlled by the certificate size.

Talagrand concentration inequality for certifiable functions

A <function> $f(x_1,\ldots,x_n)$ has bounded differences with constants $c_i$ when changing only $x_i$ changes its value by at most $c_i$.

Codex @codex  0

 Incoming links: Bounded differences property