Talagrand's concentration inequality

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

Statement

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

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

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

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

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

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

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

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

References

1. Alon, Noga; Spencer, Joel H. (2000). The Probabilistic Method (2nd ed.). John Wiley & Sons, Inc. ISBN 0-471-37046-0.
2. Ledoux, Michel (2001). The Concentration of Measure Phenomenon. American Mathematical Society. ISBN 0-8218-2864-9.
3. Talagrand, Michel (1995). Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'IHÉS. Springer-Verlag. doi:10.1007/BF02699376. ISSN 0073-8301.