Random polytope
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space \R^d . Depending on use the construction and definition, random polytopes may differ.
Impact
In mathematics, a random polytope is a structure commonly used in convex analysis and the analysis of linear programs in d-dimensional Euclidean space \R^d . Depending on use the construction and definition, random polytopes may differ. The following parameterization has been used: r:(\R^d \times \{0,1\})^m\rightarrow \text{Polytopes} \in \R^d such that r((p_1, 0), (p_2, 1), (p_3, 1)...(p_m, i_m)) = \{x \in \R^n: | \frac{p_j} \cdot x \leq ||p_j|| \text{ if } i_j=1, \frac{p_j} \cdot x \geq ||p_j|| \text{ if } i_j=0 \} (Note: these polytopes can be empty).
Let \Kappa be the set of convex bodies in \R^d . Assume K \in\Kappa and consider a set of uniformly distributed points x_1, ..., x_n in K . The convex hull of these points, K_n , is called a random polytope inscribed in K . K_n = [x_1, ..., x_n] where the set [S] stands for the convex hull of the set. We define E(k,n) to be the expected volume of K - K_n .
For a large enough n and given K \in \R^n . vol K(\frac{1}{n})\ll E(K,n) \ll vol K(\frac{1}{n}) Note: One can determine the volume of the wet part to obtain the order of the magnitude of E(K,n) , instead of determining E(K,n) .
For the unit ball B^d \in \R^d , the wet part B^d(v \leq t) is the annulus \frac{B^d}{(1-h)B^d} where h is of order t^{\frac{2}{d+1}} : E(B^d,n) \approx vol B^d (\frac{1}{n}) \approx n^{\frac{-2}{d+1}} Given we have V = V(x_1,...,x_d) is the volume of a smaller cap cut off from K by aff (x_1,...,x_d) , and F=[x_1,...,x_d] is a facet if and only if x_{d+1},...,x_n are all on one side of aff \{x_1,...,x_d\} . 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 \phi = f_{d-1} (a function that returns the amount of d-1 dimensional faces), then \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 (\R^d \times \{ 0, 1\})^m=(p_1\times i_1,\dots,p_m\times i_m)^m that is Absolutely continuous on (p_1,\dots,p_d) with respect to Lebesgue measure. Generates either 0 or 1 for the i s with probability of \frac{1}{2} each.
Assigns a measure of 0 to the set of elements in (\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 k dimensional faces on a polytope in \R^d with m constraints: 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: \lim_{m \to \infty}E_k(m) = {{d}\choose{d-k}}2^{d-k} where m>d ).
The upper bound, or worst case, for the number of vertices with m constraints is much larger: 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: \pi_{m} = 1 - \frac{2\sum_{i=0}^{d-1}{{m-1}\choose i}}{\sum_{i=0}^{d}{m\choose i}} . (Note: \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: C_d(m) = \frac{2m\sum_{i=0}^{d-1}{{m-1}\choose i}}{\sum_{i=0}^{d}{{m}\choose i}} . (Note: \lim_{m \to \infty}C_d(m) = 2d ).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373728986 under CC BY-SA 4.0; modifications have been made.