Concentration of measure and isoperimetric inequalities in product spaces (Q1908323): Difference between revisions

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.