= 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=\bigotimes_i\mu_i$, and let $A\subset\Omega$ be a measurable event with $\mu(A)>0$. For $x\in\Omega$, form the mismatch vectors
$$
V_A(x)=\{(\mathbf1_{x_i\ne y_i})_{i=1}^n:y\in A\}.
$$
The <Talagrand convex distance> is the distance from zero to their closed <convex hull>:
$$
d_T(x,A)=\inf\{\lVert v\rVert_2:v\in\overline{\operatorname{conv}}V_A(x)\}.
$$
Equivalently, by the <Hahn-Banach separation theorem for two convex sets>,
$$
d_T(x,A)=\sup_{\substack{\alpha_i\geq0\\\sum_i\alpha_i^2\leq1}}\ \inf_{y\in A}\sum_{i:x_i\ne y_i}\alpha_i.
$$
Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. <Talagrand's convex distance inequality> states
$$
\boxed{\int_\Omega\exp(d_T(x,A)^2/4)\,d\mu(x)\leq\frac1{\mu(A)}.}
$$
In particular, <Markov's inequality> gives the product-space <concentration inequality>
$$
\boxed{\mu(A)\,\mu\{x:d_T(x,A)\geq s\}\leq e^{-s^2/4}\qquad(s>0).}
$$
The 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\leq M)\geq1/2$ and $\mathbb P(Z\geq M)\geq1/2$. Applying the displayed <concentration inequality> to suitable level sets will control deviations around a <median>.
Back to article page
