Concentration of measure
Encyclopedia
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".
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
. It was further developed in the works of Milman and Gromov, Maurey, Pisier
, Shechtman, Talagrand
, Ledoux, and others.
be a metric measure space, 
.
Let
where
is the
-extension of a set 
.
The function
is called the concentration rate of the space 
. The following equivalent definition has many applications:
where the supremum is over all 1-Lipschitz functions
, and
the median (or Levy mean)
is defined by the inequalities
Informally, the space
exhibits a concentration phenomenon if
decays very fast as 
grows. More formally,
a family of metric measure spaces
is called a Lévy family if
the corresponding concentration rates
satisfy
and a normal Lévy family if
for some constants
. For examples see below.
. According to the spherical isoperimetric inequality, among all subsets
of the sphere 
with prescribed spherical measure
, the spherical cap
has the smallest
-extension 
(for any 
).
Applying this to sets of measure
(where
), one can deduce the following concentration inequality
:
,
where
are universal constants.
Therefore
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
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, concentration of measure (about a median
Median
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
) is a principle that is applied in measure theory, probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, and has consequences for other fields such as Banach space
Banach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
theory. Informally, it states that "A random variable that depends in a Lipschitz
Lipschitz continuity
In mathematical analysis, Lipschitz continuity, named after Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: for every pair of points on the graph of this function, the absolute value of the...
way on many independent variables (but not too much on any of them) is essentially constant".
The c.o.m. phenomenon was put forth in the early 1970s by Vitali Milman
Vitali Milman
Vitali Davidovich Milman is a mathematician specializing in analysis. He is currently a professor at the Tel-Aviv University. In the past he was a President of the Israel Mathematical Union and a member of the “Aliyah” committee of Tel-Aviv University.-Work:Milman received in Ph.D...
in his works on the local theory of Banach space
Banach space
In mathematics, Banach spaces is the name for complete normed vector spaces, one of the central objects of study in functional analysis. A complete normed vector space is a vector space V with a norm ||·|| such that every Cauchy sequence in V has a limit in V In mathematics, Banach spaces is the...
s, extending an idea going back to the work of Paul Lévy
Paul Pierre Lévy
Paul Pierre Lévy was a Jewish French mathematician who was active especially in probability theory, introducing martingales and Lévy flights...
. It was further developed in the works of Milman and Gromov, Maurey, Pisier
Gilles Pisier
Gilles I. Pisier is a Professor of Mathematics at the Pierre and Marie Curie University and a Distinguished Professor and A.G. and M.E. Owen Chair of Mathematics at the Texas A&M University. He is known for his contributions to several fields of mathematics, including functional analysis,...
, Shechtman, Talagrand
Michel Talagrand
Michel Pierre Talagrand is a French mathematician. Docteur ès sciences since 1977, he has been, since 1985, Directeur de Recherches at CNRS and a member of the Functional Analysis Team of the Institut de Mathématique of Paris...
, Ledoux, and others.
The general setting
Let be a metric measure space, .Let
where
is the
-extension of a set .The function
is called the concentration rate of the space . The following equivalent definition has many applications:where the supremum is over all 1-Lipschitz functions
, andthe median (or Levy mean)
is defined by the inequalitiesInformally, the space
exhibits a concentration phenomenon if decays very fast as grows. More formally,a family of metric measure spaces
is called a Lévy family ifthe corresponding concentration rates
satisfyand a normal Lévy family if
for some constants
. For examples see below.Concentration on the sphere
The first example goes back to Paul LévyPaul Pierre Lévy
Paul Pierre Lévy was a Jewish French mathematician who was active especially in probability theory, introducing martingales and Lévy flights...
. According to the spherical isoperimetric inequality, among all subsets
of the sphere with prescribed spherical measureSpherical measure
In mathematics — specifically, in geometric measure theory — spherical measure σn is the “natural” Borel measure on the n-sphere Sn. Spherical measure is often normalized so that it is a probability measure on the sphere, i.e...
, the spherical caphas the smallest
-extension (for any ).Applying this to sets of measure
(where), one can deduce the following concentration inequalityConcentration inequality
In mathematics, concentration inequalities provide probability bounds on how a random variable deviates from some value . The laws of large numbers of classical probability theory state that sums of independent random variables are, under very mild conditions, close to their expectation with a...
:
,where
are universal constants.Therefore
form a normal Lévy family.Vitali Milman
Vitali Milman
Vitali Davidovich Milman is a mathematician specializing in analysis. He is currently a professor at the Tel-Aviv University. In the past he was a President of the Israel Mathematical Union and a member of the “Aliyah” committee of Tel-Aviv University.-Work:Milman received in Ph.D...
applied this fact to several problems in the local theory of Banach spaces, in particular, to give a new proof of Dvoretzky's theorem
Dvoretzky's theorem
In mathematics, in the theory of Banach spaces, Dvoretzky's theorem is an important structural theorem proved by Aryeh Dvoretzky in the early 1960s. It answered a question of Alexander Grothendieck...
.
Other examples
- Talagrand's concentration inequalityTalagrand's concentration inequalityIn probability theory, Talagrand's concentration inequality, is an isoperimetric-type inequality for product probability spaces. It was first proved by the French mathematician Michel Talagrand...
- Gaussian isoperimetric inequality
Further reading
- A. A. Giannopoulos and V. Milman, Concentration property on probability spaces, Advances in Mathematics 156 (2000), 77-106.