Suppose we have $n$ ordered realizations of a random variable uniformly distributed over the unit cube $P = (p_1, p_2, \cdots, p_n), p_i \in [0,1]^d $. And we obtain the prefix sum $S = (p_1, p_1+p_2, \cdots, \sum_{i=1}^n p_i)$.

What is the probability that the convex hull of $S$ has all of the $n$ points of $S$ as extreme points?

I tried some brutal force enumeration with small n. Since $\{S\}$ is bounded by a Zonotope $Z = \{G*P: G \in [0, 1]^n\}$, i also plotted the $Z$

enter image description here

$n=6, d=2, p_i \sim (Uniform(0, 1) \times Uniform(0, 1)) $, and on the left, it's density distribution of extreme points from all $n!$ different permutation and on the right, it's density distribution of extreme points of $Z$



Your Answer

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