Random polytope

In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{d}}$. Depending on use the construction and definition, random polytopes may differ.

There are multiple non equivalent definitions of a Random polytope. For the following definitions. Let K be a bounded convex set in a Euclidean space:

• The convex hull of random points selected with respect to a uniform distribution inside K.
• The nonempty intersection of half-spaces in ${\displaystyle \mathbb {R} ^{d}}$.
  • The following parameterization has been used: ${\displaystyle r:(\mathbb {R} ^{d}\times \{0,1\})^{m}\rightarrow {\text{Polytopes}}\in \mathbb {R} ^{d}}$such that ${\displaystyle r((p_{1},0),(p_{2},1),(p_{3},1)...(p_{m},i_{m}))=\{x\in \mathbb {R} ^{n}:|{\frac {p_{j}}{||p_{j}||}}\cdot x\leq ||p_{j}||{\text{ if }}i_{j}=1,{\frac {p_{j}}{||p_{j}||}}\cdot x\geq ||p_{j}||{\text{ if }}i_{j}=0\}}$(Note: these polytopes can be empty).

Let ${\displaystyle \mathrm {K} }$be the set of convex bodies in ${\displaystyle \mathbb {R} ^{d}}$. Assume ${\displaystyle K\in \mathrm {K} }$and consider a set of uniformly distributed points ${\displaystyle x_{1},...,x_{n}}$in ${\displaystyle K}$. The convex hull of these points, ${\displaystyle K_{n}}$, is called a random polytope inscribed in ${\displaystyle K}$. ${\displaystyle K_{n}=[x_{1},...,x_{n}]}$where the set ${\displaystyle [S]}$stands for the convex hull of the set. We define ${\displaystyle E(k,n)}$to be the expected volume of ${\displaystyle K-K_{n}}$. For a large enough ${\displaystyle n}$and given ${\displaystyle K\in \mathbb {R} ^{n}}$.

• vol ${\displaystyle K({\frac {1}{n}})\ll E(K,n)\ll }$vol ${\displaystyle K({\frac {1}{n}})}$
  • Note: One can determine the volume of the wet part to obtain the order of the magnitude of ${\displaystyle E(K,n)}$, instead of determining ${\displaystyle E(K,n)}$.
• For the unit ball ${\displaystyle B^{d}\in \mathbb {R} ^{d}}$, the wet part ${\displaystyle B^{d}(v\leq t)}$is the annulus ${\displaystyle {\frac {B^{d}}{(1-h)B^{d}}}}$where h is of order ${\displaystyle t^{\frac {2}{d+1}}}$: ${\displaystyle E(B^{d},n)\approx }$vol ${\displaystyle B^{d}({\frac {1}{n}})\approx n^{\frac {-2}{d+1}}}$

Given we have ${\displaystyle V=V(x_{1},...,x_{d})}$is the volume of a smaller cap cut off from ${\displaystyle K}$by aff${\displaystyle (x_{1},...,x_{d})}$, and ${\displaystyle F=[x_{1},...,x_{d}]}$is a facet if and only if ${\displaystyle x_{d+1},...,x_{n}}$are all on one side of aff ${\displaystyle \{x_{1},...,x_{d}\}}$.

• ${\displaystyle E_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}[(1-V)^{n-d}+V^{n-d}]\phi (F)dx_{1}...dx_{d}}$.
  • Note: If ${\displaystyle \phi =f_{d-1}}$(a function that returns the amount of d-1 dimensional faces), then ${\displaystyle \phi (F)=1}$and formula can be evaluated for smooth convex sets and for polygons in the plane.

Assume we are given a multivariate probability distribution on ${\displaystyle (\mathbb {R} ^{d}\times \{0,1\})^{m}=(p_{1}\times i_{1},\dots ,p_{m}\times i_{m})^{m}}$that is

1. Absolutely continuous on ${\displaystyle (p_{1},\dots ,p_{d})}$with respect to Lebesgue measure.
2. Generates either 0 or 1 for the ${\displaystyle i}$s with probability of ${\displaystyle {\frac {1}{2}}}$each.
3. Assigns a measure of 0 to the set of elements in ${\displaystyle (\mathbb {R} ^{d}\times \{0,1\})^{m}}$that correspond to empty polytopes.

Given this distribution, and our assumptions, the following properties hold:

• A formula is derived for the expected number of ${\displaystyle k}$dimensional faces on a polytope in ${\displaystyle \mathbb {R} ^{d}}$with ${\displaystyle m}$constraints: ${\displaystyle E_{k}(m)=2^{d-k}\sum _{i=d-k}^{d}{{i} \choose {d-k}}{{m} \choose {i}}/\sum _{i=0}^{d}{{m} \choose {i}}}$. (Note: ${\displaystyle \lim _{m\to \infty }E_{k}(m)={{d} \choose {d-k}}2^{d-k}}$where ${\displaystyle m>d}$). The upper bound, or worst case, for the number of vertices with ${\displaystyle m}$constraints is much larger: ${\displaystyle V_{max}={m-[{\frac {1}{2}}(d+1)] \choose m-d}+{m-[{\frac {1}{2}}(d+2)] \choose m-d}}$.
• The probability that a new constraint is redundant is: ${\displaystyle \pi _{m}=1-{\frac {2\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{m \choose i}}}}$. (Note: ${\displaystyle \lim _{m\to \infty }{\pi _{m}}=1}$, and as we add more constraints, the probability a new constraint is redundant approaches 100%).
• The expected number of non-redundant constraints is: ${\displaystyle C_{d}(m)={\frac {2m\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{{m} \choose i}}}}$. (Note: ${\displaystyle \lim _{m\to \infty }C_{d}(m)=2d}$).

• Minimal caps
• Macbeath regions
• Approximations (approximations of convex bodies see properties of definition 1)
• Economic cap covering theorem (see relation from properties of definition 1 to floating bodies)