![]() | This article may be too technical for most readers to understand.(January 2022) |
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]
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,