Talagrand's concentration inequality

In probability theory, Talagrand's concentration inequality is an isoperimetric-type inequality for product probability spaces. It was first proved by the French mathematician Michel Talagrand. The inequality is one of the manifestations of the concentration of measure phenomenon.

Statement

The inequality states that if $\Omega =\Omega _{1}\times \Omega _{2}\times \cdots \times \Omega _{n}$ is a product space endowed with a product probability measure and $A$ is a subset in this space, then for any $t\geq 0$

$\Pr[A]\cdot \Pr \left[{A_{t}^{c}}\right]\leq e^{-t^{2}/4}\,,$

where ${A_{t}^{c}}$ is the complement of $A_{t}$ where this is defined by

$A_{t}=\{x\in \Omega ~:~\rho (A,x)\leq t\}$

and where $\rho$ is Talagrand's convex distance defined as

$\rho (A,x)=\max _{\alpha ,\|\alpha \|_{2}\leq 1}\ \min _{y\in A}\ \sum _{i~:~x_{i}\neq y_{i}}\alpha _{i}$

where $\alpha \in \mathbf {R} ^{n}$, $x,y\in \Omega$ are $n$-dimensional vectors with entries $\alpha _{i},x_{i},y_{i}$ respectively and $\|\cdot \|_{2}$ is the $\ell ^{2}$-norm. That is,

$\|\alpha \|_{2}=\left(\sum _{i}\alpha _{i}^{2}\right)^{1/2}$