Concentration of measure and isoperimetric inequalities in product spaces
type: Item
instance of: scholarly article
title: Concentration of measure and isoperimetric inequalities in product spaces
zbMATH Open document ID: 0864.60013
DOI: 10.1007/BF02699376
author: Michel Talagrand
published in: Publications Mathématiques
publication date: 1997-06-03T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/9406212
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/104106
review text: This booklet is a consequence of the fact that, over the years, the (former) Soviet mathematician Vitali Milman convinced the author of the great importance of the concentration of measure phenomenon. The setting is as follows. Consider a product probability space \((X,{\mathcal A},P)\), take \(A\in{\mathcal A}\), and let \(A_t\), \(t>0\), be a \(t\)-fattening of \(A\), i.e. an enlargement of \(A\) (for instance, if \(X\) is endowed with a metric \(d\), then \(A_t=\{x\in X: d(x,A)\leq t\}\) is a fattening of \(A\)). The concentration function \(\alpha(P,t)\) is defined as \(\alpha(P,t)=\sup\{1- P(A_t): A\in{\mathcal A}, P(A)\geq 1/2\}\). In Part I of this work, the author derives several results concerning concentration functions, mostly displayed in the form ``\(P(A)\geq 1/2\Rightarrow P(A_t)\geq1-\alpha(P,t)\)''. A crucial result of Part I can be roughly stated as follows: for an arbitrary set \(\Omega\), for \(A\subset\Omega^N\), for a certain fattening \(A_t\), one has \(P(A_t)\geq 1-(1/P(A))e^{-t^2/4}\), \(t>0\). This and other related inequalities of Part I do not seem to be available via martingale methods, but rather they involve isoperimetric inequalities. The natural domain of application of the tools of Part I is to get bounds for \(P(|f-M_f|\geq t)\), where \(f\) is a function defined on a Cartesian product and \(M_f\) is a median of \(f\). In most examples presented here, the function \(f\) is obtained as the solution of an optimization problem. The material of Part I is widely applied in Part II to stochastic bin packing, to the length of the longest increasing subsequence of a random permutation, to improve recent results on first passage percolation, to questions on random graphs, to the assignment problem, to geometric probabilities, to the free energy at high temperature in the Sherrington-Kirkpatrick model, and to sums of Banach space-valued independent random variables.
Mathematics Subject Classification ID: 60E15
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 28A35
Mathematics Subject Classification ID: 60G99
Mathematics Subject Classification ID: 60G15
Mathematics Subject Classification ID: 60A10
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 847748
zbMATH Keywords: concentration of measure phenomenon
zbMATH Keywords: concentration function
zbMATH Keywords: martingale methods
zbMATH Keywords: Sherrington-Kirkpatrick model
zbMATH Keywords: sums of Banach space-valued independent random variables
Wikidata QID: Q92174908
reviewed by: Aurel Spătaru
MaRDI profile type: Publication
arXiv ID: math/9406212
cites work: Some rigorous results on the Sherrington-Kirkpatrick spin glass model.
cites work: The probabilistic method
cites work: Unconditional and symmetric sets in \(n\)-dimensional normed spaces
cites work: The chromatic number of random graphs
cites work: The height of a random partial order: Concentration of measure
cites work: The Sherrington-Kirkpatrick model of spin glasses and stochastic calculus: The high temperature case
cites work: The distribution of vector-valued Rademacher series
cites work: On the length of the longest monotone subsequence in a random permutation
cites work: A Topological Application of the Isoperimetric Inequality
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Poisson approximation for large deviations
cites work: Q3975981
cites work: Q3780760
cites work: On the speed of convergence in first-passage percolation
cites work: Q3976405
cites work: Characterization of the law of the iterated logarithm in Banach spaces
cites work: Q3997990
cites work: Q4183227
cites work: Some deviation inequalities
cites work: Q3496342
cites work: Q4763429
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: On the Fluctuations of the Stochastic Traveling Salesperson Problem
cites work: A matching problem and subadditive Euclidean functionals
cites work: On the fluctuations of simple matching
cites work: Inequalities for bin packing-III
cites work: A sharp deviation inequality for the stochastic traveling salesman problem
cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
cites work: An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
cites work: Isoperimetry and integrability of the sum of independent Banach-space valued random variables
cites work: A new isoperimetric inequality for product measure and the tails of sums of independent random variables
cites work: Q4037241
cites work: Regularity of infinitely divisible processes
cites work: The Supremum of Some Canonical Processes
cites work: New concentration inequalities in product spaces
cites work: On the Expected Value of a Random Assignment Problem
cites work: Exponential Bounds for Large Deviations
Recommended article: A concentration inequality for product spaces
Recommended article: An isoperimetric inequality for Gauss-like product measures
Recommended article: On the isoperimetric constants for product measures
Recommended article: Q4445170
Recommended article: On measure concentration for separately Lipschitz functions in product spaces
Recommended article: New concentration inequalities in product spaces
Recommended article: Concentration of product spaces
Recommended article: Q5199030
Recommended article: On isoperimetric profiles of product spaces
Recommended article: Poincare inequalities, isoperimetric estimates, and representation formulas on product spaces
description: scientific article