View source for Curse of dimensionality

In [[mathematics]], '''concentration of measure''' (about a [[median]]) is a principle that is applied in [[measure theory]], [[probability]] and [[combinatorics]], and has consequences for other fields such as [[Banach space]] theory. Informally, it states that "A random variable that depends in a [[Lipschitz continuity|Lipschitz]] way on many independent variables (but not too much on any of them) is essentially constant". <ref>Michel Talagand, A New Look at Independence, The Annals of Probability, 1996, Vol. 24, No.1, 1-34</ref>

The c.o.m. phenomenon was put forth in the early 1970s by [[Vitali Milman]] in his works on the local theory of [[Banach space]]s, extending an idea going back to the work of [[Paul Lévy (mathematician)|Paul Lévy]].<ref>"''The concentration of <math>f_\ast(\mu)</math>, ubiquitous in the probability theory and statistical mechanics, was brought to geometry (starting from Banach spaces) by Vitali Milman, following the earlier work by Paul Lévy''" - [[Mikhail Gromov (mathematician)|M. Gromov]], Spaces and questions, GAFA 2000 (Tel Aviv, 1999), Geom. Funct. Anal. 2000, Special Volume, Part I, 118&ndash;161.</ref><ref>"''The idea of concentration of measure (which was discovered by V.Milman) is arguably one of the great ideas of analysis in our times. While its impact on Probability is only a small part of the whole picture, this impact should not be ignored.''" - [[Michel Talagrand|M. Talagrand]], A new look at independence, Ann. Probab. 24 (1996), no. 1, 1&ndash;34.</ref> It was further developed in the works of Milman and [[Mikhail Gromov (mathematician)|Gromov]], [[Bernard Maurey|Maurey]], [[Gilles Pisier|Pisier]], [[Gideon Shechtman|Shechtman]], [[Michel Talagrand|Talagrand]], Ledoux, and others.

==The general setting==

Let <math>(X, d, \mu) </math> be a metric measure space, <math>\mu(X) = 1</math>.
Let 
:<math>\alpha(\epsilon) = \sup \left\{\mu( X \setminus A_\epsilon) \, | \, \mu(A) \geq 1/2 \right\},</math>
where 
:<math>A_\epsilon = \left\{ x \, | \, d(x, A) < \epsilon \right\} </math>
is the <math>\epsilon</math>-''extension'' of a set <math>A</math>.

The function <math>\alpha(\cdot)</math> is called the ''concentration rate'' of the space <math>X</math>. The following equivalent definition has many applications:
:<math>\alpha(\epsilon) = \sup \left\{ \mu( \{ F \geq \mathop{M} + \epsilon \}) \right\},</math>
where the supremum is over all 1-Lipschitz functions <math>F: X \to \mathbb{R}</math>, and 
the median (or Levy mean) <math> M = \mathop{Med} F </math> is defined by the inequalities
:<math>\mu \{ F \geq M \} \geq 1/2, \, \mu \{ F \leq M \} \geq 1/2.</math>

Informally, the space <math>X</math> exhibits a concentration phenomenon if
<math>\alpha(\epsilon)</math> decays very fast as <math>\epsilon</math> grows. More formally,
a family of metric measure spaces <math>(X_n, d_n, \mu_n)</math> is called a ''Lévy family'' if
the corresponding concentration rates <math>\alpha_n</math> satisfy
:<math>\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \to 0 {\rm \;as\; } n\to \infty,</math>
and a ''normal Lévy family'' if
:<math>\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \leq C \exp(-c n \epsilon^2)</math>
for some constants <math>c,C>0</math>. For examples see below.

==Concentration on the sphere==

The first example goes back to [[Paul Lévy (mathematician)|Paul Lévy]]. According to the [[spherical isoperimetric inequality]], among all subsets <math>A</math> of the sphere <math>S^n</math> with prescribed [[spherical measure]] <math>\sigma_n(A)</math>, the spherical cap
:<math> \left\{ x \in S^n | \mathrm{dist}(x, x_0) \leq R \right\} </math>
has the smallest <math>\epsilon</math>-extension <math>A_\epsilon</math> (for any <math>\epsilon > 0</math>).

Applying this to sets of measure <math>\sigma_n(A) = 1/2</math> (where 
<math>\sigma_n(S^n) = 1</math>), one can deduce the following [[concentration inequality]]:
:<math>\sigma_n(A_\epsilon) \geq 1 - C \exp(- c n \epsilon^2) </math>,
where <math>C,c</math> are universal constants.

Therefore <math>(S^n)_n</math> form a ''normal Lévy family''.

[[Vitali Milman]] applied this fact to several problems in the local theory of Banach spaces, in particular, to give a new proof of [[Dvoretzky's theorem]].

==Other examples==

* [[Talagrand's concentration inequality]]
* [[Gaussian isoperimetric inequality]]

==Footnotes==
<references/>

==Further reading==

*{{cite book
 | last       = Ledoux
 | first      = Michel  
 | title      = The Concentration of Measure Phenomenon
 | publisher  = American Mathematical Society
 | year       = 2001
 | isbn         = 0-8218-2864-9
}}

* A. A. Giannopoulos and V. Milman, [http://users.uoa.gr/~apgiannop/concentration.ps ''Concentration property on probability spaces''], Advances in Mathematics 156 (2000), 77-106.

[[Category:Measure theory]]
[[Category:Asymptotic geometric analysis]]