Concentration of measure and isoperimetric inequalities in product spaces

Michel Talagrand

Publications Mathématiques de l'IHÉS (1995)

  • Volume: 81, page 73-205
  • ISSN: 0073-8301

How to cite


Talagrand, Michel. "Concentration of measure and isoperimetric inequalities in product spaces." Publications Mathématiques de l'IHÉS 81 (1995): 73-205. <>.

author = {Talagrand, Michel},
journal = {Publications Mathématiques de l'IHÉS},
keywords = {concentration of measure phenomenon; concentration function; martingale methods; Sherrington-Kirkpatrick model; sums of Banach space-valued independent random variables},
language = {fre},
pages = {73-205},
publisher = {Institut des Hautes Études Scientifiques},
title = {Concentration of measure and isoperimetric inequalities in product spaces},
url = {},
volume = {81},
year = {1995},

AU - Talagrand, Michel
TI - Concentration of measure and isoperimetric inequalities in product spaces
JO - Publications Mathématiques de l'IHÉS
PY - 1995
PB - Institut des Hautes Études Scientifiques
VL - 81
SP - 73
EP - 205
LA - fre
KW - concentration of measure phenomenon; concentration function; martingale methods; Sherrington-Kirkpatrick model; sums of Banach space-valued independent random variables
UR -
ER -


  1. [A-L-R] M. AIZENMAN, J. L. LEBOWITZ, D. RUELLE, Some rigorous results on the Sherrington-Kirkpatrick spin glass model, Commun. Math. Phys. 112 (1987), 3-20. Zbl1108.82312MR88k:82104a
  2. [A-S] N. ALON, J. SPENCER, The Probabilistic Method, Wiley, 1991. 
  3. [A-M] D. AMIR, V. D. MILMAN, Unconditional and symmetric sets in n-dimensional normed spaces, Israel J. Math. 37 (1980), 3-20. Zbl0445.46011MR83b:46016
  4. [B1] B. BOLLOBÁS, The chromatic number of random graphs, Combinatorica 8 (1988), 49-55. Zbl0666.05033MR89i:05244
  5. [B2] B. BOLLOBÁS, Random graphs revisited, Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 81-98. Zbl0752.05045MR92m:05168
  6. [B-B] B. BOLLOBÁS, G. BRIGHTWELL, The height of a random partial order : Concentration of Measure, Annals of Applied Probab. 2 (1992), 1009-1018. Zbl0758.06001MR94b:06005
  7. [C-L] E. G. COFFMAN, Jr., G. S. LUCKER, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, 1991. Zbl0759.90043
  8. [C-N] 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. Zbl0811.60098MR96d:82035
  9. [D-MS] S. DILWORTH, S. MONTGOMERY-SMITH, The distribution of vector-valued Rademacher series, Ann. Probab. 21 (1993), 2046-2052. Zbl0798.46006MR94i:60027
  10. [F] A. M. FRIEZE, On the length of the longest monotone subsequence in a random permutation, Ann. Appl. Prob. 1 (1991), 301-305. Zbl0738.05002MR92e:60020
  11. [G-M] M. GROMOV, V. D. MILMAN, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), 843-854. Zbl0522.53039MR84k:28012
  12. [Har] L. H. HARPER, Optimal numbering and isoperimetric problems on graphs, J. Comb. Theory (1966), 385-395. Zbl0158.20802MR34 #91
  13. [H] W. HOEFFDING, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. Zbl0127.10602MR26 #1908
  14. [J] S. JANSON, Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990), 221-290. Zbl0747.05079MR93a:60041
  15. [J-S] W. JOHNSON, G. SCHECHTMAN, Remarks on Talagrand's deviation inequality for Rademacher's functions, Lecture Notes in Math. 1470, Springer Verlag, 1991, 72-77. Zbl0753.60024MR92m:60017
  16. [Ka] R. M. KARP, An upper bound on the expected cost of an optimal assignment, in Discrete Algorithm and Complexity : Proceedings of the Japan-US joint Seminar, Academic Press, 1987, 1-4. Zbl0639.90066MR88k:90128
  17. [K1] 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. Zbl0602.60098MR88h:60201
  18. [K2] H. KESTEN, On the speed of convergence in first passage percolation, Ann. Applied Probab. 3 (1993), 296-338. Zbl0783.60103MR94m:60205
  19. [K-S] R. M. KARP, J. M. STEELE, Probabilistic analysis of heuristics, in The Traveling Salesman Problem, John Wiley and Sons, 1985, 181-205. Zbl0582.90100MR811473
  20. [Lea] J. LEADER, Discrete isoperimetric inequalities, Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 57-80. Zbl0744.60013MR93j:60010
  21. [L] M. LEDOUX, Gaussian randomization and the law of the iterated logarithm in type 2 Banach spaces, Unpublished manuscript, 1985. 
  22. [L-T1] M. LEDOUX, M. TALAGRAND, Characterization of the law of the iterated logarithm in Banach spaces, Ann. Probab. 16 (1988), 1242-1264. Zbl0662.60008MR89i:60016
  23. [L-T2] M. LEDOUX, M. TALAGRAND, Probability in Banach Spaces, Springer Verlag, 1991. Zbl0748.60004MR93c:60001
  24. [Lu] T. LUCZAK, The chromatic number of Random graphs, Combinatorica 11 (1991), 45-54. Zbl0771.05090MR92g:05164
  25. [Mau1] B. MAUREY, Construction de suites symétriques, Comptes Rendus Acad. Sci. Paris 288 (1979), 679-681. Zbl0398.46019MR80c:46020
  26. [Mau2] B. MAUREY, Some deviation inequalities, Geometric and Functional Analysis 1 (1991), 188-197. Zbl0756.60018MR92g:60024
  27. [McD] C. McDIARMID, On the method of bounded differences, in Survey in Combinatorics (J. Simons, Ed.), London Mathematical Society Lecture Notes, Vol. 141, Cambridge Univ. Press, London/New York, 1989, 148-188. Zbl0712.05012MR91e:05077
  28. [M-H] C. McDIARMID, Ryan HAYWARD, Strong concentration for Quicksort, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992, 414-421. Zbl0829.68040MR1173912
  29. [M-S] V. D. MILMAN, G. SCHECHTMAN, Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Math. 1200, Springer Verlag, 1986. Zbl0606.46013MR87m:46038
  30. [Mi1] V. D. MILMAN, A new proof of the theorem of A. Dvoretzky on sections of convex bodies, Func. Anal. Appl. 5 (1971), 28-37. Zbl0239.46018MR45 #2451
  31. [Mi2] V. D. MILMAN, Asymptotic properties of functions of several variables defined on homogenous spaces, Soviet. Math. Dokl. 12 (1971), 1277-1491. Zbl0236.26009MR46 #2703
  32. [Mi3] V. D. MILMAN, The heritage of P. Lévy in geometrical functional analysis, Astérisque 157/158 (1988), 273-301. Zbl0681.46021MR91d:01005
  33. [P] 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. Zbl0606.60008MR88d:46032
  34. [R1] W. RHEE, On the fluctuations of the stochastic traveling salesperson problem, Math. of Operation Research 13 (1991), 482-489. Zbl0751.90080MR92k:90050
  35. [R2] W. RHEE, A matching problem and subadditive Euclidean functionals, Ann. Applied Probab. 3 (1993), 794-801. Zbl0784.60020MR95d:60024
  36. [R3] W. RHEE, On the fluctuations of simple matching, Oper. Res. Letters 16 (1994), 27-32. Zbl0814.90070MR95f:60019
  37. [R4] W. RHEE, Inequalities for the Bin Packing Problem III, Optimization 29 (1994), 381-385. Zbl0820.90079MR95i:90021
  38. [Ro] J. ROSINSKI, Remarks on a Strong Exponential Integrability of Vector Valued Random Series and Triangular Arrays, Ann. Probab., to appear. Zbl0831.60007
  39. [R-T] W. RHEE, M. TALAGRAND, A sharp deviation inequality for the stochastic traveling salesman problem Ann. Probab. 17 (1989), 1-8. Zbl0682.68058MR89m:60065
  40. [S] 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. Zbl0502.47031
  41. [S-S] E. SHAMIR, J. SPENCER, Sharp concentration of the chromatic number of random graphs Gn,p, Combinatorica 7 (1987), 121-129. Zbl0632.05024MR88i:05164
  42. [T1] M. TALAGRAND, An isoperimetric theorem on the cube and the Kintchine Kahane inequalities, Proc. Amer. Math. Soc. 104 (1988), 905-909. Zbl0691.60015MR90h:60016
  43. [T2] M. TALAGRAND, Isoperimetry and integrability of the sum of independent Banach space valued random variables, Ann. Probab. 17 (1989), 1546-1570. Zbl0692.60016MR91e:60054
  44. [T3] 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. Zbl0760.60005MR92j:60004
  45. [T4] 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. Zbl0818.46047MR93d:60095
  46. [T5] M. TALAGRAND, Regularity of infinitely divisible processes, Ann. Probab. 21 (1993), 362-432. Zbl0776.60053MR94h:60058
  47. [T6] M. TALAGRAND, Supremum of some canonical processes, Amer. J. Math. 116 (1994), 295-314. Zbl0798.60040MR95g:60052
  48. [T7] M. TALAGRAND, New concentration inequalities, in preparation. Zbl0893.60001
  49. [W] D. W. WALKUP, On the expected value of a random assignment problem, SIAM J. Comput. 8 (1979), 440-442. Zbl0413.68062MR80e:68176
  50. [Y] V. V. YURINSKII, Exponential bounds for large deviations, Theor. Prob. Appl. 19 (1974), 154-155. Zbl0323.60029

Citations in EuDML Documents

  1. Timo Seppäläinen, Strong law of large numbers for the interface in ballistic deposition
  2. Michel Talagrand, Verres de Spin et optimisation combinatoire
  3. Cathy Maugis, Bertrand Michel, A non asymptotic penalized criterion for gaussian mixture model selection
  4. Michel Ledoux, On Talagrand's deviation inequalities for product measures
  5. Cathy Maugis, Bertrand Michel, A non asymptotic penalized criterion for Gaussian mixture model selection
  6. Anton Bovier, Irina Kurkova, Derrida's generalised random energy models 1 : models with finitely many hierarchies
  7. T. J. Sullivan, M. McKerns, D. Meyer, F. Theil, H. Owhadi, M. Ortiz, Optimal uncertainty quantification for legacy data observations of Lipschitz functions
  8. Itai Benjamini, Gil Kalai, Oded Schramm, Noise sensitivity of boolean functions and applications to percolation
  9. S. Bobkov, Isoperimetric problem for uniform enlargement
  10. Ivan Gentil, From the Prékopa-Leindler inequality to modified logarithmic Sobolev inequality

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.