Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 112 / 3 / i / Solution

The useful form is Talagrand's convex distance inequality. Let $({\Omega }_i,{\mu }_i)$ be standard probability spaces, let $\Omega ={\prod }_{i=1}^n{\Omega }_i$ carry the product measure $\mu ={⨂}_i{\mu }_i$, and let $A\subset \Omega$ be a measurable event with $\mu (A)>0$. For $x\in \Omega$, form the mismatch vectorsThe Talagrand convex distance is the distance from zero to their closed convex hull:Equivalently, by the Hahn-Banach separation theorem for two convex sets,Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. Talagrand's convex distance inequality statesIn particular, Markov's inequality gives the product-space concentration inequalityThe same conclusion is interpreted with outer probabilities if a distance set is not measurable; the continuous geometric function used below has measurable level sets. A median $M$ of a real random variable $Z$ means that $\mathbb{P}(Z\le M)\ge 1/2$ and $\mathbb{P}(Z\ge M)\ge 1/2$. Applying the displayed concentration inequality to suitable level sets will control deviations around a median.