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)