Isoperimetric-type inequality on product spaces
In the probability theory field of mathematics, Talagrand's concentration inequality is an isoperimetric-type inequality for product probability spaces. It was first proved by the French mathematician Michel Talagrand. The inequality is one of the manifestations of the concentration of measure phenomenon.
Roughly, the product of the probability to be in some subset of a product space (e.g. to be in one of some collection of states described by a vector) multiplied by the probability to be outside of a neighbourhood of that subspace at least a distance formula_1 away, is bounded from above by the exponential factor formula_2. It becomes rapidly more unlikely to be outside of a larger neighbourhood of a region in a product space, implying a highly concentrated probability density for states described by independent variables, generically. The inequality can be used to streamline optimisation protocols by sampling a limited subset of the full distribution and being able to bound the probability to find a value far from the average of the samples.
Statement.
The inequality states that if formula_3 is a product space endowed with a product probability measure and formula_4
is a subset in this space, then for any formula_5
 formula_6
where formula_7 is the complement of "formula_8" where this is defined by
formula_9
and where formula_10 is Talagrand's convex distance defined as
 formula_11
where formula_12, formula_13 are formula_14-dimensional vectors with entries
formula_15 respectively and formula_16 is the formula_17-norm. That is,
formula_18
References.
 ;templatestyles src="Reflist/styles.css" / ;