×

Concentration of measure and isoperimetric inequalities in product spaces. (English) Zbl 0864.60013

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.

MSC:

60E15 Inequalities; stochastic orderings
60D05 Geometric probability and stochastic geometry
28A35 Measures and integrals in product spaces
60G99 Stochastic processes
60G15 Gaussian processes
60A10 Probabilistic measure theory
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

References:

[1] M. Aizenman, J. L. Lebowitz, D. Ruelle, Some rigorous results on the Sherrington-Kirkpatrick spin glass model,Commun. Math. Phys. 112 (1987), 3–20. · Zbl 1108.82312 · doi:10.1007/BF01217677
[2] N. Alon, J. Spencer,The Probabilistic Method, Wiley, 1991. · Zbl 1333.05001
[3] D. Amir, V. D. Milman, Unconditional and symmetric sets inn-dimensional normed spaces,Israel J. Math. 37 (1980), 3–20. · Zbl 0445.46011 · doi:10.1007/BF02762864
[4] B. Bollobás, The chromatic number of random graphs,Combinatorica 8 (1988), 49–55. · Zbl 0666.05033 · doi:10.1007/BF02122551
[5] B. Bollabás, Random graphs revisited,Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 81–98.
[6] B. Bollobás, G. Brightwell, The height of a random partial order: Concentration of Measure,Annals of Applied Probab.2 (1992), 1009–1018. · Zbl 0758.06001 · doi:10.1214/aoap/1177005586
[7] E. G. Coffman, Jr.,G. S. Lucker,Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, 1991.
[8] F. Comets, J. Neveu, The Sherrington-Kirkpatrick Model of Spin Classes and Stochastic Calculus: the high temperature case,Comm. Math. Phys. 166 (1995), 549–564. · Zbl 0811.60098 · doi:10.1007/BF02099887
[9] S. Dilworth, S. Montgomery-Smith, The distribution of vector-valued Rademacher series,Ann. Probab. 21 (1993), 2046–2052. · Zbl 0798.46006 · doi:10.1214/aop/1176989010
[10] A. M. Frieze, On the length of the longest monotone subsequence in a random permutation,Ann. Appl. Prob. 1 (1991), 301–305. · Zbl 0738.05002 · doi:10.1214/aoap/1177005939
[11] M. Gromov, V. D. Milman, A topological application of the isoperimetric inequality,Amer. J. Math. 105 (1983), 843–854. · Zbl 0522.53039 · doi:10.2307/2374298
[12] L. H. Harper, Optimal numbering and isoperimetric problems on graphs,J. Comb. Theory (1966), 385–395. · Zbl 0158.20802
[13] W. Hoeffding, Probability inequalities for sums of bounded random variables,J. Amer. Statist. Assoc. 58 (1963), 13–30. · Zbl 0127.10602 · doi:10.2307/2282952
[14] S. Janson, Poisson approximation for large deviations,Random Structures and Algorithms 1 (1990), 221–290. · Zbl 0747.05079 · doi:10.1002/rsa.3240010209
[15] W. Johnson, G. Schechtman, Remarks on Talagrand’s deviation inequality for Rademacher’s functions,Lecture Notes in Math. 1470, Springer Verlag, 1991, 72–77. · Zbl 0753.60024 · doi:10.1007/BFb0090214
[16] R. M. Karp, An upper bound on the expected cost of an optimal assignment, inDiscrete Algorithm and Complexity: Proceedings of the Japan-US joint Seminar, Academic Press, 1987, 1–4. · Zbl 0639.90066
[17] H. Kesten, Aspects of first-passage percolation, Ecole d’Eté de Probabilité de Saint-Flour XIV,Lecture Notes in Math. 1180, 125–264, Springer Verlag, 1986, 125–264. · doi:10.1007/BFb0074919
[18] H. Kesten, On the speed of convergence in first passage percolation,Ann. Applied Probab. 3 (1993), 296–338. · Zbl 0783.60103 · doi:10.1214/aoap/1177005426
[19] R. M. Karp, J. M. Steele, Probabilistic analysis of heuristics, inThe Traveling Salesman Problem, John Wiley and Sons, 1985, 181–205.
[20] J. Leader, Discrete isoperimetric inequalities,Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 57–80. · Zbl 0744.60013
[21] M. Ledoux,Gaussian randomization and the law of the iterated logarithm in type 2 Banach spaces, Unpublished manuscript, 1985.
[22] M. Ledoux, M. Talagrand, Characterization of the law of the iterated logarithm in Banach spaces,Ann. Probab. 16 (1988), 1242–1264. · Zbl 0662.60008 · doi:10.1214/aop/1176991688
[23] M. Ledoux, M. Talagrand,Probability in Banach Spaces, Springer Verlag, 1991. · Zbl 0748.60004
[24] T. Luczak, The chromatic number of Random graphs,Combinatorica 11 (1991), 45–54. · Zbl 0771.05090 · doi:10.1007/BF01375472
[25] B. Maurey, Construction de suites symétriques,Comptes Rendus Acad. Sci. Paris 288 (1979), 679–681. · Zbl 0398.46019
[26] B. Maurey, Some deviation inequalities,Geometric and Functional Analysis 1 (1991), 188–197. · Zbl 0756.60018 · doi:10.1007/BF01896377
[27] C. McDiarmid, On the method of bounded differences, inSurvey in Combinatorics (J. Simons, Ed.), London Mathematical Society Lecture Notes, Vol. 141, Cambridge Univ. Press, London/New York, 1989, 148–188. · Zbl 0712.05012
[28] C. McDiarmid, RyanHayward, Strong concentration for Quicksort,Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992, 414–421. · Zbl 0829.68040
[29] V. D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces,Lecture Notes in Math. 1200, Springer Verlag, 1986. · Zbl 0606.46013
[30] V. D. Milman, A new proof of the theorem of A. Dvoretzky on sections of convex bodies,Func. Anal. Appl. 5 (1971), 28–37.
[31] V. D. Milman, Asymptotic properties of functions of several variables defined on homogenous spaces,Soviet. Math Dokl. 12 (1971), 1277–1491.
[32] V. D. Milman, The heritage of P. Lévy in geometrical functional analysis,Astérisque 157/158 (1988), 273–301.
[33] G. Pisier, Probabilistic methods in the geometry of Banach spaces. Probability and Analysis, Varena (Italy) 1985,Lecture Notes in Math. 1206, Springer Verlag, 1986, 167–241. · doi:10.1007/BFb0076302
[34] W. Rhee, On the fluctuations of the stochastic traveling salesperson problem,Math. of Operation Research 13 (1991), 482–489. · Zbl 0751.90080 · doi:10.1287/moor.16.3.482
[35] W. Rhee, A matching problem and subadditive Euclidean functionals,Ann. Applied Probab. 3 (1993), 794–801. · Zbl 0784.60020 · doi:10.1214/aoap/1177005364
[36] W. Rhee, On the fluctuations of simple matching,Oper. Res. Letters 16 (1994), 27–32. · Zbl 0814.90070 · doi:10.1016/0167-6377(94)90018-3
[37] W. Rhee, Inequalities for the Bin Packing Problem III,Optimization 29 (1994), 381–385. · Zbl 0820.90079 · doi:10.1080/02331939408843965
[38] J. Rosinski, Remarks on a Strong Exponential Integrability of Vector Valued Random Series and Triangular Arrays,Ann. Probab., to appear.
[39] W. Rhee, M. Talagrand, A sharp deviation inequality for the stochastic traveling salesman problemAnn. Probab. 17 (1989), 1–8. · Zbl 0682.68058 · doi:10.1214/aop/1176991490
[40] G. Schechtman, Levy type inequality for a class of metric spaces, Martingale Theory in Harmonic analysis and Banach spaces, Cleveland 1981,Lecture Note in Math. 939, Springer Verlag, 1981, 211–215. · doi:10.1007/BFb0096270
[41] E. Shamir, J. Spencer, Sharp concentration of the chromatic number of random graphs G n, p ,Combinatorica 7 (1987), 121–129. · Zbl 0632.05024 · doi:10.1007/BF02579208
[42] M. Talagrand, An isoperimetric theorem on the cube and the Kintchine Kahane inequalities,Proc. Amer. Math. Soc. 104 (1988), 905–909. · Zbl 0691.60015 · doi:10.1090/S0002-9939-1988-0964871-7
[43] M. Talagrand, Isoperimetry and integrability of the sum of independent Banach space valued random variables,Ann. Probab. 17 (1989), 1546–1570. · Zbl 0692.60016 · doi:10.1214/aop/1176991174
[44] M. Talagrand, A new isoperimetric inequality for product measure, and the tails of sums of independent random variables,Geometric and Functional Analysis 1 (1991), 211–223. · Zbl 0760.60005 · doi:10.1007/BF01896379
[45] M. Talagrand, A new isoperimetric inequality for product measure, and the concentration of measure phenomenon, Israel Seminar (GAFA),Lecture Notes in Math. 1469, Springer Verlag, 1991, 94–124. · Zbl 0818.46047 · doi:10.1007/BFb0089217
[46] M. Talagrand, Regularity of infinitely divisible processes,Ann. Probab. 21 (1993), 362–432. · Zbl 0776.60053 · doi:10.1214/aop/1176989409
[47] M. Talagrand, Supremum of some canonical processes,Amer. J. Math. 116 (1994), 295–314. · Zbl 0798.60040 · doi:10.2307/2374931
[48] M. Talagrand, New concentration inequalities, in preparation. · Zbl 0893.60001
[49] D. W. Walkup, On the expected value of a random assignment problem,SIAM J. Comput. 8 (1979), 440–442. · Zbl 0413.68062 · doi:10.1137/0208036
[50] V. V. Yurinskii, Exponential bounds for large deviations,Theor. Prob. Appl. 19 (1974), 154–155. · Zbl 0323.60029 · doi:10.1137/1119012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.