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. Depending on use the construction and definition, random polytopes may differ.

Definition

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:

Properties definition 1

Let be the set of convex bodies in. Assume and consider a set of uniformly distributed points in. The convex hull of these points,, is called a random polytope inscribed in. where the set stands for the convex hull of the set. We define to be the expected volume of. For a large enough and given.
  • vol vol
  • * Note: One can determine the volume of the wet part to obtain the order of the magnitude of, instead of determining.
  • For the unit ball, the wet part is the annulus where h is of order : vol
Given we have is the volume of a smaller cap cut off from by aff, and is a facet if and only if are all on one side of aff.
  • .
  • * Note: If, then and formula can be evaluated for smooth convex sets and for polygons in the plane.

Properties definition 2

Assume we are given a multivariate probability distribution on that is
  1. Absolutely continuous on with respect to Lebesgue measure.
  2. Generates either 0 or 1 for the s with probability of each.
  3. Assigns a measure of 0 to the set of elements in that correspond to empty polytopes.
Given this distribution, and our assumptions, the following properties hold:
  • A formula is derived for the expected number of dimensional faces on a polytope in with constraints:.. The upper bound, or worst case, for the number of vertices with constraints is much larger:.
  • The probability that a new constraint is redundant is:..
  • The expected number of non-redundant constraints is:..

Example uses