# Probability that random high dimensional vectors are all on the convex hull

Say I pick $$n$$ i.i.d. random standard normal points in $$\mathbb{R}^d$$. Roughly, as long as $$n$$ is much smaller than exponential in $$d$$, with high probability all points will be on the convex hull. This is because with high probability they will all be near the radius $$\sqrt{d}$$ sphere and all almost orthogonal, and thus each point is the furthest in its own direction from the origin. Let $$p(n,d)$$ be the failure probability that at least one point is in the interior of the convex hull.

Question: What's the best upper bound on $$p(n,d)$$ as a function of $$n$$ and $$d$$? I care most about the regime $$d \gg 1$$, $$n \in O(\operatorname{poly}(d))$$.

• I think that by "all points will be on the convex hull" you mean, that no $X_i \in co(X_1,\ldots,X_n)^0$, when $X_1,\ldots,X_n$ are the generated random $X_i$, It seems that the condition $X_i \not\in ext(co(X_1,\ldots,X_n))$ gives the same probabilities. Jul 9 '20 at 11:01
• Yes, I was glossing over the boundary because it is measure 0. Jul 9 '20 at 11:31

## 1 Answer

It's not too bad to see that the probability is at most $$2n^2 e^{-d/2e}$$. Let $$x_1,\ldots,x_n$$ be the points. We will use a union bound, so it is sufficient to examine the probability that $$x_1$$ is in the convex hull of $$x_2,\ldots,x_n$$. This happens if and only if there are $$\lambda_j \in [0,1]$$ with $$\sum \lambda_j = 1$$ and $$x_1 = \sum_{j = 2}^n \lambda_j x_j\,.$$

Take an inner product with $$x_1$$ to see that this implies $$\| x_1 \|_2^2 = \sum_{j = 2}^n \lambda_j \langle x_1, x_j \rangle.$$

Thus $$P(x_1 \in \mathrm{conv}(x_2,\ldots,x_n)) \leq P( \|x_1\|^2 \leq \max_{j \geq 2} |\langle x_1, x_j \rangle|).$$

If we divide by $$\|x_1\|$$, the RHS probability bound becomes

$$P\left(\|x_1\| \le \max_{j \ge 2} \left|\left\right|\right).$$

$$\|x_1\|^2 \sim \chi^2_d$$ and $$\left \sim N(0,1)$$, so from $$\chi^2_d$$ and $$N(0,1)$$ tail bounds we have

\begin{align*} P(\|x_1\| \le t\sqrt{d}) &\le \left(t e^{(1-t^2)/2}\right)^d \\ P\left(\left \ge t\sqrt{d}\right) &\le \frac{\left(e^{-t^2/2}\right)^d}{t\sqrt{2\pi d}} \end{align*}

for any $$t \in (0,1)$$. Matching the base of the exponents gives \begin{align*} t e^{(1-t^2)/2} &= e^{-t^2/2} \\ t &= e^{-1/2} \approx 0.606531 \end{align*}

whence union bounding shows \begin{align*}P(x_1 \in \mathrm{conv}(x_2,\ldots,x_n)) &\le (n-1) \left(1 + \frac{1}{\sqrt{2\pi d/e}}\right) e^{-d/2e} \\ &< 2ne^{-d/2e} \end{align*} and so $$P(\exists~j \text{ s.t. }x_j \in \mathrm{conv}(x_1,\ldots,x_{j-1},x_{j+1},\ldots,x_n)) < 2n^2 e^{-d/2e}.$$

I do not know if this is optimal, but it's worth noting that it's basically the strategy you suggested. When $$n$$ is exponentially large in $$d$$ the probability does not tend to $$0$$ provided the exponent is big enough, which is where this bound breaks.

• Thanks, yes this the argument I had in mind, but nicely expressed. I’m interesting in knowing $c$; if you don’t feel like writing that out okay if I edit to fill in later? Jul 9 '20 at 18:46
• Yeah absolutely feel free to edit it in. Jul 9 '20 at 21:26
• I think the exponent can be tightened from $e^{-d/2e}$ to $2^{-d/2}$, but don't have time to complete the proof. Jul 14 '20 at 20:23