Extremal Lipschitz functions in the deviation inequalities from the mean

Dainius Dzindzalieta (Vilnius University)


We obtain an optimal deviation from the mean upper bound $D(x)=\sup\{\mu\{f-\mathbb{E}_{\mu} f\geq x\}:f\in\mathcal{F},x\in\mathbb{R}\}$ where $\mathcal{F}$ is the class of the integrable, Lipschitz functions on probability metric (product) spaces. As corollaries we get exact bounds for Euclidean unit sphere $S^{n-1}$ with a geodesic distance and a normalized Haar measure, for $\mathbb{R}^n$ equipped with a Gaussian measure and for the multidimensional cube, rectangle, torus or Diamond graph equipped with uniform measure and Hamming distance. We also prove that in general probability metric spaces the $\sup$ is achieved on a family of distance functions.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-5

Publication Date: August 6, 2013

DOI: 10.1214/ECP.v18-2814


  • Barthe, F.; Cattiaux, P.; Roberto, C. Isoperimetry between exponential and Gaussian. Electron. J. Probab. 12 (2007), no. 44, 1212--1237 (electronic). MR2346509
  • Benyamini, Yoav. Two-point symmetrization, the isoperimetric inequality on the sphere and some applications. Texas functional analysis seminar 1983–1984 (Austin, Tex.), 53--76, Longhorn Notes, Univ. Texas Press, Austin, TX, 1984. MR0832231
  • Bentkus, Vidmantas. On measure concentration for separately Lipschitz functions in product spaces. Israel J. Math. 158 (2007), 1--17. MR2342455
  • Bezrukov, Sergei L.; Rius, Miquel; Serra, Oriol. The vertex isoperimetric problem for the powers of the diamond graph. Discrete Math. 308 (2008), no. 11, 2067--2074. MR2404533
  • Bezrukov, Sergei L.; Serra, Oriol. A local-global principle for vertex-isoperimetric problems. Kleitman and combinatorics: a celebration (Cambridge, MA, 1999). Discrete Math. 257 (2002), no. 2-3, 285--309. MR1935729
  • Bollobás, Béla; Leader, Imre. Isoperimetric inequalities and fractional set systems. J. Combin. Theory Ser. A 56 (1991), no. 1, 63--74. MR1082843
  • Bobkov, S. G.; Houdré, C. Isoperimetric constants for product probability measures. Ann. Probab. 25 (1997), no. 1, 184--205. MR1428505
  • Bobkov, S. G. Isoperimetric problem for uniform enlargement. Studia Math. 123 (1997), no. 1, 81--95. MR1438305
  • Bobkov, S. G. A localized proof of the isoperimetric Bakry-Ledoux inequality and some applications. (Russian) Teor. Veroyatnost. i Primenen. 47 (2002), no. 2, 340--346; translation in Theory Probab. Appl. 47 (2003), no. 2, 308--314 MR2001838
  • Borell, Christer. The Brunn-Minkowski inequality in Gauss space. Invent. Math. 30 (1975), no. 2, 207--216. MR0399402
  • Figiel, T.; Lindenstrauss, J.; Milman, V. D. The dimension of almost spherical sections of convex bodies. Acta Math. 139 (1977), no. 1-2, 53--94. MR0445274
  • M. Gromov. Paul Levy's isoperimetric inequality. Preprint I.H.E.S, 1980.
  • Harper, L. H. Optimal assignments of numbers to vertices. J. Soc. Indust. Appl. Math. 12 1964 131--135. MR0162737
  • V. M. Karachanjan. A discrete isoperimetric problem on multidimensional torus. (In Russian) Doklady AN Arm. SSR, vol. LXXIV, volume~2, pages 61--65, 1982.
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • Lévy, Paul. Problèmes concrets d'analyse fonctionnelle. Avec un complément sur les fonctionnelles analytiques par F. Pellegrino. (French) 2d ed. Gauthier-Villars, Paris, 1951. xiv+484 pp. MR0041346
  • Ledoux, Michel. On Talagrand's deviation inequalities for product measures. ESAIM Probab. Statist. 1 (1995/97), 63--87 (electronic). MR1399224
  • Ledoux, Michel; Talagrand, Michel. Probability in Banach spaces. Isoperimetry and processes. Reprint of the 1991 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2011. xii+480 pp. ISBN: 978-3-642-20211-7 MR2814399
  • McDiarmid, Colin. On the method of bounded differences. Surveys in combinatorics, 1989 (Norwich, 1989), 148--188, London Math. Soc. Lecture Note Ser., 141, Cambridge Univ. Press, Cambridge, 1989. MR1036755
  • Milman, Vitali D.; Schechtman, Gideon. Asymptotic theory of finite-dimensional normed spaces. With an appendix by M. Gromov. Lecture Notes in Mathematics, 1200. Springer-Verlag, Berlin, 1986. viii+156 pp. ISBN: 3-540-16769-2 MR0856576
  • Riordan, Oliver. An ordering on the even discrete torus. SIAM J. Discrete Math. 11 (1998), no. 1, 110--127. MR1612869
  • Schmidt, Erhard. Die Brunn-Minkowskische Ungleichung und ihr Spiegelbild sowie die isoperimetrische Eigenschaft der Kugel in der euklidischen und nichteuklidischen Geometrie. I. (German) Math. Nachr. 1, (1948). 81--157. MR0028600
  • V. N. Sudakov and B. S. Tsirel'son. Extremal properties of half-spaces for spherically invariant measures. Journal of Mathematical Sciences, 9(1):9--18, 1978.
  • Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. No. 81 (1995), 73--205. MR1361756
  • Talagrand, Michel. A new look at independence. Ann. Probab. 24 (1996), no. 1, 1--34. MR1387624

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.