Abstract
Let (X, d) be a compact metric space and µ a Borel probability on X. For each N ≥ 1 let d N∞ be the ℓ ∞-product on X N of copies of d, and consider 1-Lipschitz functions X N → ℝ for d N∞ .
If the support of µ is connected and locally connected, then all such functions are close in probability to juntas: that is, functions that depend on only a few coordinates of X N. This describes the failure of measure concentration for these product spaces, and can be seen as a Lipschitz-function counterpart of the celebrated result of Friedgut that Boolean functions with small influences are close to juntas.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. Barthe, Infinite dimensional isoperimetric inequalities in product spaces with the supremum distance, Journal of Theoretical Probability 17 (2004), 293–308.
I. Benjamini, G. Cohen and I. Shinkar, Bi-Lipschitz bijection between the Boolean cube and the Hamming ball, preprint, available online at arXiv.org: 1310. 2017.
D. Bakry, I. Gentil and M. Ledoux, Analysis and Geometry of Markov Diffusion Operators, Grundlehren der Mathematischen Wissenschaften, Vol. 348, Springer, Cham, 2014.
J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial, The influence of variables in product spaces, Israel Journal of Mathematics 77 (1992), 55–64.
D. Cordero-Erausquin and M. Ledoux, Hypercontractive measures, Talagrand’s inequality, and influences, in Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, Vol. 2050, Springer, Heidelberg, 2012, pp. 169–189.
I. Dinur, E. Friedgut and O. Regev, Independent sets in graph powers are almost contained in juntas, Geometric and Functional Analysis 18 (2008), 77–97.
E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993–3002.
E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), 27–35.
E. Friedgut, Influences in product spaces: KKL and BKKKL revisited, Combinatorics, Probability and Computing 13 (2004), 17–29.
L. Gross, Logarithmic Sobolev inequalities, American Journal of Mathematics 97 (1975), 1061–1083.
M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, second edition, Modern Birkhäuser Classics, Birkhäuser Boston, Boston, MA, 2001.
H. Hatami, Decision trees and influences of variables over product probability spaces, Combinatorics, Probability and Computing 18 (2009), 357–369.
H. Hatami, A structure theorem for Boolean functions with small total influences, Annals of Mathematics 176(2012), 509–533.
J. Kahn, G. Kalai and N. Linial, The influence of variables on Boolean functions, in Proceedings of the 29th Annual Symposium on Foundations of Computer Science IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 68–80.
N. Keller, E. Mossel and A. Sen, Geometric influences, Annals of Probability 40 (2012), 1135–1166.
M. Ledoux, The geometry of Markov diffusion generators, Annales de la Faculté des Sciences de Toulouse. Mathématique. Série 6 9 (2000), 305–366. Probability theory.
M. Ledoux, The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, Vol. 89, American Mathematical Society, Providence, RI, 2001.
M. Talagrand, On Russo’s approximate zero-one law, Annals of Probability 22 (1994), 1576–1587.
F. B. Weissler, Logarithmic Sobolev inequalities and hypercontractive estimates on the circle, Journal of Functional Analysis 37 (1980), 218–234.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by a fellowship from the Clay Mathematics Institute.
Rights and permissions
About this article
Cite this article
Austin, T. On the failure of concentration for the ℓ ∞-ball. Isr. J. Math. 211, 221–238 (2016). https://doi.org/10.1007/s11856-015-1265-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-015-1265-6