Concentration of measure

From Wikipedia, the free encyclopedia

In mathematics, concentration of measure 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 functions that depend on many parameters are almost constant.

The c.o.m. phenomenon was put forth in the early 1970-s by Vitali Milman in his works on the local theory of Banach spaces, extending and idea going back to the work of Paul Lévy. It was further developed in the works of Milman and Gromov, Maurey, Pisier, Schechtman, Talagrand, Ledoux, and others.

Contents

[edit] The general setting

Let (X,d,μ) be a metric measure space, μ(X) = 1. Let

\alpha(\epsilon) = \sup \left\{\mu( X \setminus A_\epsilon) \, | \, \mu(A) = 1/2 \right\},

where

A_\epsilon = \left\{ x \, | \, d(x, A) < \epsilon \right\}

is the ε-extension of a set A.

The function \alpha(\cdot) is called the concentration rate of the space X. The following equivalent definition has many applications:

\alpha(\epsilon) = \sup \left\{ \mu( \{ F \geq \mathop{M} + \epsilon \}) \right\},

where the infimum is over all 1-Lipschitz functions F: X \to \mathbb{R}, and the median (or Levy mean) M = \mathop{Med} F is defined by the inequalities

\mu \{ F \geq M \} \geq 1/2, \, \mu \{ F \leq M \} \geq 1/2.

Informally, the space X exhibits a concentration phenomenon if α(ε) decays very fast as ε grows. More formally, a family of metric measure spaces (Xn,dn,μn) is called a Lévy family if the corresponding concentration rates αn satisfy

\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \to 0,

and a normal Lévy family if

\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \leq C \exp(-c n \epsilon^2)

for some constants c,C > 0. For examples see below.

[edit] Concentration on the sphere

The first example goes back to Paul Lévy. According to the spherical isoperimetric inequality, among all subsets A of the sphere Snwith prescribed measure σn(A), the spherical cap

\left\{ x \in S^n | \mathrm{dist}(x, x_0) \leq R \right\}

has the smallest ε-extension Aε (for any ε > 0).

Applying this to sets of measure σn(A) = 1 / 2 (where σn(Sn) = 1), one can deduce the following concentration inequality:

\sigma_n(A_\epsilon) \geq 1 - C \exp(- c n \epsilon^2) ,

where C,c are universal constants.

Therefore (Sn)n 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.

[edit] Other examples

[edit] See also

[edit] Further reading

  • Ledoux, Michel (2001). The Concentration of Measure Phenomenon. American Mathematical Society. ISBN 0821828649.