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

LetThe entropy functional satisfiesHence the assumed inequality givesBecause $\mathbb{E}X=0$, $\psi (\lambda )/\lambda \to 0$ as $\lambda \to 0$. Integrating from zero to $\lambda$ when $\lambda >0$, and from $\lambda$ to zero and then multiplying by the negative number $\lambda$ when $\lambda <0$, gives in both casesThus $\mathbb{E}{e}^{\lambda X}\le e^{\nu {\lambda }^2/2}$ for every real $\lambda$, which is precisely the sub-Gaussian random variable bound with variance parameter $\nu$. This integration is the Herbst argument.

SetUnder the probability measure with density $Z$, the Jensen inequality for the concave logarithm givesThe sub-Gaussian assumption with variance parameter $\nu /4$ gives $M(2\lambda )\le e^{\nu {\lambda }^2/2}$. A second application of Jensen inequality gives $M(\lambda )\ge e^{\lambda \mathbb{E}X}=1$. Consequentlyas required.

Write $X_{-i}$ for all coordinates except $X_i$, let $X_i^{\prime }$ be an independent random variable with the same distribution as $X_i$, and let $Z_i^{\prime }=f(X_1,\dots ,X_i^{\prime },\dots ,X_n)$. Three equivalent forms of the Efron–Stein inequality arefor arbitrary square-integrable $Z_i$ measurable with respect to $X_{-i}$, andThe first is the sharp choice within the second because conditional expectation is the least-squares projection. The first and third right sides are equal because two conditionally independent copies have expected squared difference twice their conditional variance.

The bounded differences property with constants $c_i$ meanswhenever $x$ and $x^{\prime }$ differ only in coordinate $i$. Conditional on $X_{-i}$, the range of $Z$ is therefore at most $c_i$. The range bound on variance givesSubstitution into the Efron–Stein inequality yields

Changing $X_k$ while keeping all other coordinates fixed changes every candidate linear form by at mostThe maximum of finitely many functions obeys the same bound, so part b applies with $c_k=2{\max }_{\ell }|A_{k,\ell }|$. Therefore

Let ${\ell }^{\ast }$ be a maximizing index for the original sample. Since $Z_i^{\prime }$ is at least the value of its ${\ell }^{\ast }$th linear form,and henceThe one-sided replacement form of the Efron–Stein inequality isFor independent uniform signs, $\mathbb{E}[(X_i-X_i^{\prime }{)}^2\mid X]=2$. It follows that

The empty-bin indicators are not independent. For distinct $i,k$,whereas $\mathbb{P}(Z_i=1)\mathbb{P}(Z_k=1)=(1-1/n{)}^{2m}$.

Each bin is empty precisely when all $m$ balls avoid it, soThe linearity of expectation does not require independence and gives

Moving one ball can destroy at most one empty bin and create at most one empty bin; the net number of empty bins therefore changes by at most one. Thus $f$ has the bounded differences property with $c_j=1$ for all $m$ ball coordinates. The upper- and lower-tail forms of the McDiarmid inequality give, for $t>0$,

Let $B$ be the set of bins that are occupied in configuration $x$ but empty in configuration $y$. For each $b\in B$, choose the lowest-numbered ball $j_b$ lying in $b$ under $x$. Then ${\alpha }_{j_b}(x)=1$ and $x_{j_b}\ne y_{j_b}$. Distinct bins choose distinct balls, soEvery increase in the number of empty bins is accounted for by a newly empty bin, while newly occupied bins only decrease that number. Hence $f(y)-f(x)\le |B|$, proving the stated inequality.

Exactly one lowest-numbered ball is selected in each occupied bin, soPart c supplies the corresponding one-sided coordinate certificate. The product-space entropy method for certifiable functions states that a function with such a certificate of squared size at most $v$ has both centered tails bounded by $e^{-t^2/(2v)}$. Taking $v=n$ gives