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))$.



Probability that random high dimensional vectors are all on the convex hull
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<x\_1/\|x\_1\|, x\_j \right>\right|\right).$$


$\|x\_1\|^2 \sim \chi^2\_d$ and $\left<x\_1/\|x\_1\|, x\_j\right> \sim N(0,1)$, so from [$\chi^2\_d$](https://en.wikipedia.org/wiki/Chi-square_distribution#Cumulative_distribution_function) and [$N(0,1)$](https://math.stackexchange.com/questions/28751/proof-of-upper-tail-inequality-for-standard-normal-distribution/28754#28754) 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<x\_1/\|x\_1\|, x\_j\right> \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.


