Expected value of Tukey’s half-space depth for log-concave measures

Question

Let ${\mathbb P}$ be a probability measure in ${\mathbb R}^n$. Let $x\in{\mathbb R}^n$ be an arbitrary point. Let ${\mathbb H}_x$ be the set of halfspaces of ${\mathbb R}^n$ containing $x$. Let \begin{equation}\label{eq:oneshotphi} \phi_{\mathbb P}(x) = \inf_{H \in {\mathbb H}_x} {\mathbb P}(H) \end{equation} be the minimal probability of a halfspace containing $x$. Function $\phi_{\mathbb P}(x)$ is called Tukey’s half-space depth. Also, denote $$ c_{\mathbb P}={\mathbb E}[\phi_{\mathbb P}(X)], $$ where $X$ is a random variable with distribution ${\mathbb P}$. Does these exists a universal constant $c\in(0,1)$ such that $$ c_{\mathbb P} \leq c^n $$ for all $n=1,2,\dots$ and all log-concave probability measures ${\mathbb P}$ in ${\mathbb R}^n$?

Answer 1

This question has been considered in detail, and essentially solved, in the recent preprint Half-space depth of log-concave probability measures, where the authors show the bound $c_\mathbb{P} \leq c^{n^{1-o(1)}}$.

Answer 2

Let me prove the weaker bound $c_n \leq c^{\sqrt{n}}$.

Since the problem is affine-invariant, we may assume that $\mathbb{P}$ is isotropic, i.e. has mean zero and covariance matrix equal to identity.

Now consider the following elementary inequality (every log-concave measure is subexponential): if $X$ is a log-concave isotropic random variable, then for every $t\geq0$ $$\mathbb{P}(X \geq t) \leq C\exp(-ct)$$ for some absolute constants $C$, $c$.

For $x \in \mathbb{R}^n$, consider the half-space $H$ such that $x$ is the closest point to the origin in $H$. By the previous inequality (using the fact that the class of log-concave measures is stable under marginals), we have $\mathbb{P}(H) \leq C \exp(-c \|x\|)$, where $\|\cdot\|$ is the Euclidean norm.

It follows that $c_\mathbb{P} \leq \mathbb{E} C \exp (-c \|X\|)$. The claimed bound follows by writing

$$ \mathbb{E} \exp (-c \|X\|) \leq \exp(- \frac{c}{2} \sqrt{n} ) + \mathbb{P}(\|X\| \leq \frac 12 \sqrt{n})$$ since small ball estimates for isotropic convex bodies (e.g. Theorem 13.2.3 in Brazitikos, Silouanos; Giannopoulos, Apostolos; Valettas, Petros; Vritsiou, Beatrice-Helen, Geometry of isotropic convex bodies, Mathematical Surveys and Monographs 196. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-1456-6/hbk). xx, 594 p. (2014). ZBL1304.52001.) imply that the last probability is bounded by $\exp(-c'\sqrt{n})$.

In most directions, high-dimensional isotropic log-concave measures are sub-gaussian rather than sub-exponential (see chapter 8 in the aforementioned book) so it is indeed very plausible to improve the bound to $c_n \leq c^n$.