# 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_{t}]\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}$ 