Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Interpolation of Probability Measures on Graphs Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Concentration of Measure Principle and Entropy-Inequalities

verfasst von : Paul-Marie Samson

Erschienen in: Convexity and Concentration

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The concentration measure principle is presented in an abstract way to encompass and unify different concentration properties. We give a general overview of the links between concentration properties, transport-entropy inequalities, and logarithmic Sobolev inequalities for some specific transport costs. By giving few examples, we emphasize optimal weak transport costs as an efficient tool to establish new transport inequality and new concentration principles for discrete measures (the binomial law, the Poisson measure, the uniform law on the symmetric group).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Entropy and Thinning of Discrete Random Variables
Nächstes Kapitel Structured Random Matrices
Literatur
[ABC+00]
C. Ané, S. Blachère, D. Chafaï, P. Fougères, I. Gentil, F. Malrieu, C. Roberto, and G. Scheffer. Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses]. Société Mathématique de France, Paris, 2000. With a preface by Dominique Bakry and Michel Ledoux.
[ACW14]
R. Adamczak, D. Chafaï, and P. Wolff. Circular law for random matrices with exchangeable entries. ArXiv e-prints, February 2014.
[Ada05]
R. Adamczak. Logarithmic Sobolev inequalities and concentration of measure for convex functions and polynomial chaoses. Bull. Pol. Acad. Sci. Math., 53(2):221–238, 2005.MathSciNetMATHCrossRef
[Ada08]
R. Adamczak. A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electron. J. Probab., 13:no. 34, 1000–1034, 2008.
[AGS14]
L. Ambrosio, N. Gigli, and G. Savaré. Metric measure spaces with Riemannian Ricci curvature bounded from below. Duke Math. J., 163(7):1405–1490, 2014.MathSciNetMATHCrossRef
[AGS15]
L. Ambrosio, N. Gigli, and G. Savaré. Bakry-Émery curvature-dimension condition and Riemannian Ricci curvature bounds. Ann. Probab., 43(1):339–404, 2015.MathSciNetMATHCrossRef
[AS15]
R. Adamczak and M. Strzelecki. Modified log-Sobolev inequalities for convex functions on the real line. Sufficient conditions. ArXiv e-prints, May 2015.
[BG99]
S.G. Bobkov and F. Götze. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal., 163(1):1–28, 1999.MathSciNetMATHCrossRef
[BGL01]
S.G. Bobkov, I. Gentil, and M. Ledoux. Hypercontractivity of Hamilton-Jacobi equations. J. Math. Pures Appl. (9), 80(7):669–696, 2001.MathSciNetMATHCrossRef
[BHT06]
S. G. Bobkov, C. Houdré, and P. Tetali. The subgaussian constant and concentration inequalities. Israel J. Math., 156:255–283, 2006.MathSciNetMATHCrossRef
[BK08]
F. Barthe and A. V. Kolesnikov. Mass transport and variants of the logarithmic Sobolev inequality. J. Geom. Anal., 18(4):921–979, 2008.MathSciNetMATHCrossRef
[BL97]
S. G. Bobkov and M. Ledoux. Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution. Probab. Theory Related Fields, 107(3):383–400, 1997.MathSciNetMATHCrossRef
[BL00]
S. G. Bobkov and M. Ledoux. From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities. Geom. Funct. Anal., 10(5):1028–1052, 2000.MathSciNetMATHCrossRef
[BLM00]
S. Boucheron, G. Lugosi, and P. Massart. A sharp concentration inequality with applications. Random Structures Algorithms, 16(3):277–292, 2000.MathSciNetMATHCrossRef
[BLM03]
S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities using the entropy method. Ann. Probab., 31(3):1583–1614, 2003.MathSciNetMATHCrossRef
[BLM13]
S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
[Bob97]
S. G. Bobkov. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space. Ann. Probab., 25(1):206–214, 1997.MathSciNetMATHCrossRef
[Bou03]
O. Bousquet. Concentration inequalities for sub-additive functions using the entropy method. In Stochastic inequalities and applications, volume 56 of Progr. Probab., pages 213–247. Birkhäuser, Basel, 2003.
[BR03]
F. Barthe and C. Roberto. Sobolev inequalities for probability measures on the real line. Studia Math., 159(3):481–497, 2003.MathSciNetMATHCrossRef
[BR08]
F. Barthe and C. Roberto. Modified logarithmic Sobolev inequalities on \(\mathbb{R}\). Potential Anal., 29(2):167–193, 2008.MathSciNetMATHCrossRef
[CD10]
S. Chatterjee and P.S. Dey. Applications of Stein’s method for concentration inequalities. Ann. Probab., 38(6):2443–2485, 2010.MathSciNetMATHCrossRef
[CG06]
P. Cattiaux and A. Guillin. On quadratic transportation cost inequalities. J. Math. Pures Appl. (9), 86(4):341–361, 2006.MathSciNetMATHCrossRef
[Cha05]
S. Chatterjee. Concentration inequalities with exchangeable pairs (Ph.D. thesis). ArXiv Mathematics e-prints, July 2005.
[Cha07]
S. Chatterjee. Stein’s method for concentration inequalities. Probab. Theory Related Fields, 138(1–2):305–321, 2007.MathSciNetMATHCrossRef
[Csi67]
I. Csiszár. Information-type measures of difference of probability distributions and indirect observations. Studia Sci. Math. Hungar., 2:299–318, 1967.MathSciNetMATH
[Dem97]
[DGW04]
H. Djellout, A. Guillin, and L. Wu. Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab., 32(3B):2702–2732, 2004.MathSciNetMATHCrossRef
[Dou94]
P. Doukhan. Mixing, volume 85 of Lecture Notes in Statistics. Springer-Verlag, New York, 1994. Properties and examples.
[EM12]
M. Erbar and J. Maas. Ricci curvature of finite Markov chains via convexity of the entropy. Arch. Ration. Mech. Anal., 206(3):997–1038, 2012.MathSciNetMATHCrossRef
[EM14]
M. Erbar and J. Maas. Gradient flow structures for discrete porous medium equations. Discrete Contin. Dyn. Syst., 34(4):1355–1374, 2014.MathSciNetMATH
[EMT15]
M. Erbar, J. Maas, and P. Tetali. Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models. Ann. Fac. Sci. Toulouse Math. (6), 24(4):781–800, 2015.MathSciNetMATHCrossRef
[FHT03]
A. A. Fedotov, P. Harremoës, and F. Topsøe. Refinements of Pinsker’s inequality. IEEE Trans. Inform. Theory, 49(6):1491–1498, 2003.MathSciNetMATHCrossRef
[FMNW15]
N. Feldheim, A. Marsiglietti, P. Nayar, and J. Wang. A note on the convex infimum convolution inequality. ArXiv e-prints, May 2015.
[GGM05]
I. Gentil, A. Guillin, and L. Miclo. Modified logarithmic Sobolev inequalities and transportation inequalities. Probab. Theory Related Fields, 133(3):409–436, 2005.MathSciNetMATHCrossRef
[GGM07]
I. Gentil, A. Guillin, and L. Miclo. Modified logarithmic Sobolev inequalities in null curvature. Rev. Mat. Iberoam., 23(1):235–258, 2007.MathSciNetMATHCrossRef
[Gil10]
G. L. Gilardoni. On Pinsker’s and Vajda’s type inequalities for Csiszár’s f-divergences. IEEE Trans. Inform. Theory, 56(11):5377–5386, 2010.MathSciNetMATHCrossRef
[GL10]
N. Gozlan and C. Léonard. Transport inequalities. A survey. Markov Process. Related Fields, 16(4):635–736, 2010.
[GM83]
M. Gromov and V. D. Milman. A topological application of the isoperimetric inequality. Amer. J. Math., 105(4):843–854, 1983.MathSciNetMATHCrossRef
[Goz07]
N. Gozlan. Characterization of Talagrand’s like transportation-cost inequalities on the real line. J. Funct. Anal., 250(2):400–425, 2007.MathSciNetMATHCrossRef
[Goz09]
N. Gozlan. A characterization of dimension free concentration in terms of transportation inequalities. Ann. Probab., 37(6):2480–2498, 2009.MathSciNetMATHCrossRef
[Goz12]
N. Gozlan. Transport-entropy inequalities on the line. Electron. J. Probab., 17:no. 49, 18, 2012.
[Goz15]
[Gro75]
[Gro99]
M. Gromov. Metric structures for Riemannian and non-Riemannian spaces, volume 152 of Progress in Mathematics. Birkhäuser Boston, Inc., Boston, MA, 1999.
[GRS11a]
N. Gozlan, C. Roberto, and P.-M. Samson. From concentration to logarithmic Sobolev and Poincaré inequalities. J. Funct. Anal., 260(5):1491–1522, 2011.MathSciNetMATHCrossRef
[GRS11b]
N. Gozlan, C. Roberto, and P.-M. Samson. A new characterization of Talagrand’s transport-entropy inequalities and applications. Ann. Probab., 39(3):857–880, 2011.MathSciNetMATHCrossRef
[GRS13]
N. Gozlan, C. Roberto, and P.-M. Samson. Characterization of Talagrand’s transport-entropy inequalities in metric spaces. Ann. Probab., 41(5):3112–3139, 2013.MathSciNetMATHCrossRef
[GRS14]
N. Gozlan, C. Roberto, and P.-M. Samson. Hamilton Jacobi equations on metric spaces and transport entropy inequalities. Rev. Mat. Iberoam., 30(1):133–163, 2014.MathSciNetMATHCrossRef
[GRS+15]
N. Gozlan, C. Roberto, P.-M. Samson, Y. Shu, and P. Tetali. Characterization of a class of weak transport-entropy inequalities on the line. ArXiv e-prints, September 2015.
[GRST14a]
N. Gozlan, C. Roberto, P.-M. Samson, and P. Tetali. Displacement convexity of entropy and related inequalities on graphs. Probab. Theory Related Fields, 160(1–2):47–94, 2014.MathSciNetMATHCrossRef
[GRST14b]
N. Gozlan, C. Roberto, P.-M. Samson, and P. Tetali. Kantorovich duality for general transport costs and applications. ArXiv e-prints, December 2014.
[Har66]
[Hil14]
[HS87]
R. Holley and D. Stroock. Logarithmic Sobolev inequalities and stochastic Ising models. J. Statist. Phys., 46(5–6):1159–1194, 1987.MathSciNetMATHCrossRef
[Kom88]
[Kon12]
A. Kontorovich. Obtaining measure concentration from Markov contraction. Markov Process. Related Fields, 18(4):613–638, 2012.MathSciNetMATH
[KR05]
T. Klein and E. Rio. Concentration around the mean for maxima of empirical processes. Ann. Probab., 33(3):1060–1077, 2005.MathSciNetMATHCrossRef
[Kul67]
S. Kullback. Lower bound for discrimination information in terms of variation. IEEE Trans. Information Theory, 4:126–127, 1967.CrossRef
[Led93]
M. Ledoux. Inégalités isopérimétriques en analyse et probabilités. Astérisque, (216):Exp. No. 773, 5, 343–375, 1993. Séminaire Bourbaki, Vol. 1992/93.
[Led97]
M. Ledoux. On Talagrand’s deviation inequalities for product measures. ESAIM Probab. Statist., 1:63–87 (electronic), 1997.
[Led01]
M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.
[Lév51]
P Lévy. Problèmes concrets d’analyse fonctionnelle. Avec un complément sur les fonctionnelles analytiques par F. Pellegrino. Gauthier-Villars, Paris, 1951. 2d ed.
[LM03]
M. J. Luczak and C. McDiarmid. Concentration for locally acting permutations. Discrete Math., 265(1–3):159–171, 2003.MathSciNetMATHCrossRef
[LT91]
M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes.
[Maa11]
[Mar96a]
K. Marton. Bounding \(\overline{d}\)-distance by informational divergence: a method to prove measure concentration. Ann. Probab., 24(2):857–866, 1996.MathSciNetMATHCrossRef
[Mar96b]
[Mar97]
K. Marton. Erratum to: “A measure concentration inequality for contracting Markov chains” [Geom. Funct. Anal. 6 (1996), no. 3, 556–571; MR1392329 (97g:60082)]. Geom. Funct. Anal., 7(3):609–613, 1997.
[Mar03]
K. Marton. Measure concentration and strong mixing. Studia Sci. Math. Hungar., 40(1–2):95–113, 2003.MathSciNetMATH
[Mar04]
K. Marton. Measure concentration for Euclidean distance in the case of dependent random variables. Ann. Probab., 32(3B):2526–2544, 2004.MathSciNetMATHCrossRef
[Mar10]
K. Marton. Correction: Measure concentration for Euclidean distance in the case of dependent random variables [mr2078549]. Ann. Probab., 38(1):439–442, 2010.MathSciNetMATHCrossRef
[Mas00a]
P. Massart. About the constants in Talagrand’s concentration inequalities for empirical processes. Ann. Probab., 28(2):863–884, 2000.MathSciNetMATHCrossRef
[Mas00b]
P. Massart. Some applications of concentration inequalities to statistics. Ann. Fac. Sci. Toulouse Math. (6), 9(2):245–303, 2000. Probability theory.
[Mas07]
P. Massart. Concentration inequalities and model selection, volume 1896 of Lecture Notes in Mathematics. Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003, With a foreword by Jean Picard.
[Mau79]
B. Maurey. Construction de suites symétriques. C. R. Acad. Sci. Paris Sér. A-B, 288(14):A679–A681, 1979.MATHMathSciNet
[Mau91]
[McD02]
[MS86]
V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.
[MSWW11]
Y. Ma, S. Shen, X. Wang, and L. Wu. Transportation inequalities: from Poisson to Gibbs measures. Bernoulli, 17(1):155–169, 2011.MathSciNetMATHCrossRef
[Muc72]
B. Muckenhoupt. Hardy’s inequality with weights. Studia Math., 44:31–38, 1972. Collection of articles honoring the completion by Antoni Zygmund of 50 years of scientific activity, I.
[Oll09]
[OV00]
F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal., 173(2):361–400, 2000.MathSciNetMATHCrossRef
[OV12]
Y. Ollivier and C. Villani. A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube? SIAM J. Discrete Math., 26(3):983–996, 2012.MathSciNetMATHCrossRef
[Pan01]
D. Panchenko. A note on Talagrand’s concentration inequality. Electron. Comm. Probab., 6:55–65 (electronic), 2001.
[Pan02]
D. Panchenko. Some extensions of an inequality of Vapnik and Chervonenkis. Electron. Comm. Probab., 7:55–65 (electronic), 2002.
[Pan03]
D. Panchenko. Symmetrization approach to concentration inequalities for empirical processes. Ann. Probab., 31(4):2068–2081, 2003.MathSciNetMATHCrossRef
[Pau12]
D. Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. ArXiv e-prints, December 2012.
[Pau14]
D. Paulin. The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems. Electron. J. Probab., 19:no. 68, 34, 2014.
[Pin64]
M. S. Pinsker. Information and information stability of random variables and processes. Translated and edited by Amiel Feinstein. Holden-Day Inc., San Francisco, Calif., 1964.
[Rio01]
E. Rio. Inégalités de concentration pour les processus empiriques de classes de parties. Probab. Theory Related Fields, 119(2):163–175, 2001.MathSciNetMATHCrossRef
[Rio02]
E. Rio. Une inégalité de Bennett pour les maxima de processus empiriques. Ann. Inst. H. Poincaré Probab. Statist., 38(6):1053–1057, 2002. En l’honneur de J. Bretagnolle, D. Dacunha-Castelle, I. Ibragimov.
[Rio12]
E. Rio. Sur la fonction de taux dans les inégalités de Talagrand pour les processus empiriques. C. R. Math. Acad. Sci. Paris, 350(5–6):303–305, 2012.MathSciNetMATHCrossRef
[Rio13]
E. Rio. On McDiarmid’s concentration inequality. Electron. Commun. Probab., 18:no. 44, 11, 2013.
[RR91]
M. M. Rao and Z. D. Ren. Theory of Orlicz spaces. Marcel Dekker Inc., 1991.MATH
[Sam00]
P.-M. Samson. Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes. Ann. Probab., 28(1):416–461, 2000.MathSciNetMATHCrossRef
[Sam03]
P.-M. Samson. Concentration inequalities for convex functions on product spaces. In Stochastic inequalities and applications, volume 56 of Progr. Probab., pages 33–52. Birkhäuser, Basel, 2003.
[Sam07]
P.-M. Samson. Infimum-convolution description of concentration properties of product probability measures, with applications. Ann. Inst. H. Poincaré Probab. Statist., 43(3):321–338, 2007.MathSciNetMATHCrossRef
[Sam16]
P.-M. Samson. Transport-entropy inequalities on locally acting groups of permutations. working paper or preprint, September 2016.
[Sio58]
[Str65]
[Tal91]
M. Talagrand. A new isoperimetric inequality and the concentration of measure phenomenon. In Geometric aspects of functional analysis (1989–90), volume 1469 of Lecture Notes in Math., pages 94–124. Springer, Berlin, 1991.
[Tal95]
M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math., (81):73–205, 1995.MathSciNetMATHCrossRef
[Tal96a]
[Tal96b]
[Tal96c]
[Vil09]
C. Villani. Optimal transport: old and new, volume 338 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 2009.
[Wan14]
N.-Y. Wang. Concentration inequalities for Gibbs sampling under \(d_{l_{2}}\)-metric. Electron. Commun. Probab., 19:no. 63, 11, 2014.
[Wu06]
L. Wu. Poincaré and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition. Ann. Probab., 34(5):1960–1989, 2006.MathSciNetCrossRef
[WW77]
D. L. Wang and P. Wang. Extremal configurations on a discrete torus and a generalization of the generalized Macaulay theorem. SIAM. J. Appl. Math., 33(1):55–59, 1977.MathSciNetMATHCrossRef
[WW14]
N.-Y. Wang and L. Wu. Convergence rate and concentration inequalities for Gibbs sampling in high dimension. Bernoulli, 20(4):1698–1716, 2014.MathSciNetMATHCrossRef
Metadaten
Titel
Concentration of Measure Principle and Entropy-Inequalities
verfasst von
Paul-Marie Samson
Copyright-Jahr
2017
Verlag
Springer New York
Buch
Convexity and Concentration

Print ISBN: 978-1-4939-7004-9

Electronic ISBN: 978-1-4939-7005-6

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-1-4939-7005-6_3

Premium Partner

    Bildnachweise