TransWikia.com

Convex hull of prefix sum of $n$ ordered random points

MathOverflow Asked by yupbank on December 21, 2021

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$

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP