Expected value of Tukey’s half-space depth for log-concave measures 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$?
 A: 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)}}$.
A: 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$.
