[Math] Convex hull of $k$ random points

convex-hullspr.probability

Suppose we have $k$ realizations of a random variable uniformly distributed over the unit cube $[0,1]^n$.

What is the probability that their convex hull has all of the $k$ points as extreme points?

If it would be easier, "unit cube" can be replaced by "unit ball".

Best Answer

Imre Bárány has investigated similar questions, including the asymptotics of $p(k,S)$, the probability that $k$ uniformly chosen points from the convex body $S\subset \mathbb{R}^n$ are in convex position (they are extreme points of their convex hull). In general one can give the bounds $$c_1\le k^{2/(n-1)}\sqrt[k]{p(k,S)}\le c_2$$ for large enough $k$ and constants $c_1,c_2$. I don't think closed form formulas are known for all $k$ even for simple convex sets $S$. See here and the papers in the references. See here for the case when $S$ is the unit ball.

Related Question