On the failure of concentration for the \ell_\infty-ball

Abstract

Let $(X,d)$ be a compact metric space and $\mu$ a Borel probability on $X$. For each $N\ge 1$ let $d_{\infty }^N$ be the ${\ell }_{\infty }$-product on $X^N$ of copies of $d$, and consider $1$-Lipschitz functions $X^N\to \mathbb{R}$ for $d_{\infty }^N$. If the support of $\mu$ 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.

13 pages; [Jun 23rd, 2014:] Section 2 strengthened following referee's suggestions

Cited by in corpus (2)

• Gradient Estimation with Simultaneous Perturbation and Compressive Sensing
• Juntas in the ${\ell }^1$-grid and Lipschitz maps between discrete tori