8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jul 9 '20 at 11:01
  • $\begingroup$ Yes, I was glossing over the boundary because it is measure 0. $\endgroup$ Jul 9 '20 at 11:31
6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Jul 9 '20 at 18:46
  • 1
    $\begingroup$ Yeah absolutely feel free to edit it in. $\endgroup$
    – Marcus M
    Jul 9 '20 at 21:26
  • $\begingroup$ I think the exponent can be tightened from $e^{-d/2e}$ to $2^{-d/2}$, but don't have time to complete the proof. $\endgroup$ Jul 14 '20 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.