Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 208 / 3

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