$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary

Question

Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. We denote by $V(\mathcal{S}^{d})$ and $V(\mathcal{C}_n)$ the volume of $\mathcal{S}^d$ and $\mathcal{C}_n$ respectively.

---

Question: Can we prove that, for all constant values $a\in (0,1)$, $n$ has to grow superpolynomially in $d$ (for $d\to\infty$) to satisfy $\mathbb{E}[V(\mathcal{C}_n)]\ge aV(\mathcal{S}^{d})$ ?

---

---

Note: Do you please have any reference for the convex hull $\mathcal{C}_n^*$ of the $n$ points of $\mathcal{S}^{d-1}$ maximizing $V(\mathcal{C}_n)$ (so that we can hopefully avoid to calculate the expectation $\mathbb{E}[V(\mathcal{C}_n)]$ if $n=\omega(\mathrm{poly}(d))$ to satisfy $V(\mathcal{C}_n^*)\ge aV(\mathcal{S}^{d})$ for any $a\in(0,1)$ when $d\to\infty$) ?

Answer 1

It's true deterministically in $P_n$. In fact, here's a proof that there is some $c$ so that if $n \leq e^{cd}$ then we have that $V(C_n)/V(S^d) \to 0$.

We'll work with the ball of radius $1$. For a given configuration $P_n$, let $p$ denote the probability that a point chosen uniformly from the sphere lies in the $C_n$; then $p = V(C_n)/V(S^d)$. Let $X$ be a point chosen uniformly at random form the ball $S^d$.

If $X \in C_n$, then there must be a point $y \in P_n$ so that $\langle y , \frac{X}{\|X\|} \rangle \geq \|X\|$; otherwise, then hyperplane with normal vector $X/\|X\|$ separates $X$ from the set $P_n$. Union bounding over all points we have $$ \mathbb{P}(X \in C_n) \leq \sum_{y \in P_n} \mathbb{P}\left( \left\langle y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right) = n \mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right)$$ where in the last line we used spherically symmetry of $X$, and we let $Y$ be chosen uniformly at random from the sphere.

It is thus sufficient to show that this probability decays exponentially. Note that $\mathbb{P}(\|X \| < 1/2) = 2^{-d}$ and so $$\mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right) < 2^{-d} + \mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq 1/2\right).$$ By rotational symmetry of $Y$, we may assume WLOG that $X/\|X\|$ is the first coordinate vector $e_1$. We may sample $Y$ by considering $d$ i.i.d. standard Gaussians $Z = (Z_1,\ldots,Z_d)$ and taking $Y = Z/\|Z\|$. Thus we have that $\langle Y, e_1 \rangle$ has the same distribution as $\frac{Z_1}{\|Z\|}$. We have that $\mathbb{P}(\|Z\| < \sqrt{d}/2) \leq e^{-cd}$, and so $$ \mathbb{P}\left(\frac{Z_1}{\|Z\|} \geq 1/2\right) \leq e^{-cd} + \mathbb{P}(Z_1 \geq \sqrt{d}/4) \leq e^{-c'd}.$$