Top Qs
Timeline
Chat
Perspective

Talagrand's concentration inequality

Isoperimetric-type inequality on product spaces From Wikipedia, the free encyclopedia

Remove ads

In the probability theory field of mathematics, Talagrand's concentration inequality is an isoperimetric-type inequality for product probability spaces.[1][2] It was first proved by the French mathematician Michel Talagrand.[3] The inequality is one of the manifestations of the concentration of measure phenomenon.[2]

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 away, is bounded from above by the exponential factor . 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.[4]

Remove ads

Statement

The inequality states that if is a product space endowed with a product probability measure and is a subset in this space, then for any

where is the complement of where this is defined by

and where is Talagrand's convex distance defined as

where , are -dimensional vectors with entries respectively and is the -norm. That is,

Remove ads

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads