Samiksha Jaiswal (Editor)

Concentration of measure

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

Sudeep kamath concentration of measure 1


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 way on many independent variables (but not too much on any of them) is essentially constant".

Contents

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

Lecture 18 concentration of measure


The general setting

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

α ( ϵ ) = sup { μ ( X ∖ A ϵ ) | μ ( A ) ≥ 1 / 2 } ,

where

A ϵ = { x | d ( x , A ) < ϵ }

is the ϵ -extension of a set A .

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

α ( ϵ ) = sup { μ ( { F ≥ M + ϵ } ) } ,

where the supremum is over all 1-Lipschitz functions F : X → R , and the median (or Levy mean) M = M e d F is defined by the inequalities

μ { F ≥ M } ≥ 1 / 2 , μ { F ≤ M } ≥ 1 / 2.

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

∀ ϵ > 0 α n ( ϵ ) → 0 a s n → ∞ ,

and a normal Lévy family if

∀ ϵ > 0 α n ( ϵ ) ≤ C exp ⁡ ( − c n ϵ 2 )

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

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 S n with prescribed spherical measure σ n ( A ) , the spherical cap

{ x ∈ S n | d i s t ( x , x 0 ) ≤ R } ,

for suitable R , has the smallest ϵ -extension A ϵ (for any ϵ > 0 ).

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

σ n ( A ϵ ) ≥ 1 − C exp ⁡ ( − c n ϵ 2 ) ,

where C , c are universal constants. Therefore ( S n ) n meet the definition above of 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

  • Borell–TIS inequality
  • Gaussian isoperimetric inequality
  • McDiarmid's inequality
  • Talagrand's concentration inequality

    • References

    Concentration of measure Wikipedia
    (Text) CC BY-SA


    Similar Topics