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 $\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[{\overline {A_{t}}}\right]\leq e^{-t^{2}/4}\,,$

where ${\overline {A_{t}}}$ 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}$

Explanation

Probability deals with uncertainty. The inference of a future event or process requires the identification of key variables related to it. Certain assumptions about the nature of those variables (random variables) and their functional relationship can be drawn. Yet there are cases where the functional relationships of such variables are not directly available. But in spite of such difficulty Talagrand's concentration inequality helps us to describe some properties (in probabilistic terms) related to the variables and their functional representation. The authors ^[4] clearly describe what Talagrand's concentration inequality implies under certain assumptions-"..if a function of many independent random variables does not depend too much on any of the variables then it is concentrated in the sense that with high probability, it is close to its expected value..."- and by such implication, we can for example (under many other possible applications), quantify the empirical risk of the model we are using to forecast some future event.

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.
4. Boucheron, Stephanie;Lugosi,Gábor;jMassart,Pascal (2013).Concentration Inequalities: A Nonasymptotic Theory of Independence.OUP Oxford.ASIN: B00BPS6QQI.