Talagrand's concentration inequality

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In probability theory, 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]

Statement[edit]

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,

References[edit]

  1. ^ Alon, Noga; Spencer, Joel H. (2000). The Probabilistic Method (2nd ed.). John Wiley & Sons, Inc. ISBN 0-471-37046-0.
  2. ^ a b Ledoux, Michel (2001). The Concentration of Measure Phenomenon. American Mathematical Society. ISBN 0-8218-2864-9.
  3. ^ Talagrand, Michel (1995). Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'IHÉS. Springer-Verlag. doi:10.1007/BF02699376. ISSN 0073-8301.