Concentration of measure

Concentration of measure

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". [1]

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.[2][3] It was further developed in the works of Milman and Gromov, Maurey, Pisier, Shechtman, Talagrand, Ledoux, and others.

Contents

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) \geq 1/2 \right\},

where

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

is the \epsilon-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 supremum 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 \alpha(\epsilon) decays very fast as \epsilon grows. More formally, a family of metric measure spaces (Xn,dnn) is called a Lévy family if the corresponding concentration rates αn satisfy

\forall \epsilon > 0 \,\, \alpha_n(\epsilon) \to 0 {\rm \;as\; } n\to \infty,

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.

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

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

has the smallest \epsilon-extension A_\epsilon (for any \epsilon > 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.

Other examples

Footnotes

  1. ^ Michel Talagand, A New Look at Independence, The Annals of Probability, 1996, Vol. 24, No.1, 1-34
  2. ^ "The concentration of f_\ast(\mu), 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" - M. Gromov, Spaces and questions, GAFA 2000 (Tel Aviv, 1999), Geom. Funct. Anal. 2000, Special Volume, Part I, 118–161.
  3. ^ "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." - M. Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34.

Further reading

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

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Concentration (disambiguation) — Concentration can refer to: Contents 1 Science, engineering, and technology 2 Psychology 3 Economics 4 Games 5 …   Wikipedia

  • Concentration ratio — In economics, a concentration ratio is a measure of the total output produced in an industry by a given number of firms in the industry. The most common concentration ratios are the CR4 and the CR8, which means the four and the eight largest… …   Wikipedia

  • measure of concentration — koncentracijos matas statusas T sritis fizika atitikmenys: angl. measure of concentration vok. Konzentrationsmaß, n rus. мера концентрации, f pranc. mesure de concentration, f …   Fizikos terminų žodynas

  • concentration — [[t]kɒ̱ns(ə)ntre͟ɪʃ(ə)n[/t]] ♦♦♦ concentrations 1) N UNCOUNT Concentration on something involves giving all your attention to it. Neal kept interrupting, breaking my concentration... We lacked concentration and it cost us the goal and the game.… …   English dictionary

  • concentration test — 1. (for renal function) the patient is placed under conditions that cause the normal person to elaborate urine containing one or more constituents in high concentration, and the results are observed to see whether the patient is able to attain… …   Medical dictionary

  • Concentration dimension — In mathematics specifically, in probability theory the concentration dimension of a Banach space valued random variable is a numerical measure of how “spread out” the random variable is compared to the norm on the space. Definition Let… …   Wikipedia

  • concentration — /kon seuhn tray sheuhn/, n. 1. the act of concentrating; the state of being concentrated. 2. exclusive attention to one object; close mental application. 3. something concentrated: a concentration of stars. 4. Mil. a. the assembling of military… …   Universalium

  • concentration — con•cen•tra•tion [[t]ˌkɒn sənˈtreɪ ʃən[/t]] n. 1) the act of concentrating or the state of being concentrated 2) exclusive attention to one object; close mental application 3) something concentrated: a concentration of stars[/ex] 4) chem. (in a… …   From formal English to slang

  • Market concentration — In economics, market concentration is a function of the number of firms and their respective shares of the total production (alternatively, total capacity or total reserves) in a market. Alternative terms are Industry concentration and Seller… …   Wikipedia

  • Measures of pollutant concentration — NOEL redirects here. For other uses, see Noel (disambiguation). Measures of pollutant concentration are used to determine risk assessment in public health. Industry is continually synthesizing new chemicals, the regulation of which requires… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”