View source for Talagrand's concentration inequality

{{Short description|Isoperimetric-type inequality on product spaces}}
{{Technical|date=January 2022}}
In the [[probability theory]] field of [[mathematics]], '''Talagrand's concentration inequality''' is an [[isoperimetric]]-type [[inequality (mathematics)|inequality]] for [[product space|product]] [[probability space]]s.<ref>{{Cite book | last1=Alon | first1=Noga | last2=Spencer | first2=Joel H. | title=The Probabilistic Method | edition=2nd | year=2000 | publisher=John Wiley & Sons, Inc. | isbn=0-471-37046-0}}</ref><ref name=ledoux>{{cite book | last       = Ledoux | first      = Michel   | title      = The Concentration of Measure Phenomenon | publisher  = American Mathematical Society | year       = 2001 | isbn         = 0-8218-2864-9}}</ref> It was first proved by the French mathematician [[Michel Talagrand]].<ref>{{Cite journal | last1=Talagrand | first1=Michel | title=Concentration of measure and isoperimetric inequalities in product spaces | journal=Publications Mathématiques de l'IHÉS| year=1995 | volume=81 | pages=73–205 | publisher=Springer-Verlag | issn=0073-8301|doi=10.1007/BF02699376| arxiv=math/9406212 | s2cid=119668709 }}</ref> The inequality is one of the manifestations of the [[concentration of measure]] phenomenon.<ref name=ledoux/>

Roughly, the product of the probability to be in some subset of a product space (e.g. to be in one of some collection of states described by a vector) multiplied by the probability to be outside of a neighbourhood of that subspace at least a distance <math> t </math> away, is bounded from above by the exponential factor <math> e^{-t^2/4} </math>. It becomes rapidly more unlikely to be outside of a larger neighbourhood of a region in a product space, implying a highly concentrated probability density for states described by independent variables, generically. The inequality can be used to streamline optimisation protocols by sampling a limited subset of the full distribution and being able to bound the probability to find a value far from the average of the samples.<ref>{{Cite journal | last1=Castelvecchi | first1=Davide | title=Mathematician who tamed randomness wins Abel Prize | date=21 March 2024 | journal=Nature | volume=627 | issue=8005 | pages=714–715 | url=https://www.nature.com/articles/d41586-024-00839-6 | doi=10.1038/d41586-024-00839-6| bibcode=2024Natur.627..714C }}</ref>

==Statement==
The inequality states that if <math>\Omega = \Omega_1 \times \Omega_2 \times \cdots \times \Omega_n</math> is a [[product space]] endowed with a [[product measure|product probability measure]] and <math>A</math>
is a subset in this space, then for any <math>t \ge 0</math>

: <math>\Pr[A] \cdot \Pr\left[{A^c_t}\right] \le e^{-t^2/4} \, ,</math>

where <math>{A^c_t}</math> is the complement of ''<math>A_{t}</math>'' where this is defined by
:<math>A_t = \{ x \in \Omega\colon~ \rho(A,x) \le t \}</math>
and where <math>\rho</math> is Talagrand's convex distance defined as

: <math>\rho(A,x) = \max_{\alpha, \|\alpha\|_2 \le 1} \ \min_{y \in A} \ \sum_{i\colon~x_i \neq y_i} \alpha_i</math>

where <math>\alpha \in \mathbf{R}^n</math>, <math>x,y \in \Omega</math> are <math>n</math>-dimensional vectors with entries
<math>\alpha_i, x_i, y_i</math> respectively and <math>\|\cdot\|_2</math> is the <math>\ell^2</math>-norm.  That is,

:<math>\|\alpha\|_2=\left(\sum_i\alpha_i^2\right)^{1/2}</math>

==References==

{{Reflist}}

{{DEFAULTSORT:Talagrand's Concentration Inequality}}
[[Category:Probabilistic inequalities]]
[[Category:Measure theory]]


{{probability-stub}}