The combinatorial structure of random polytopes

Choose n random points in Rd, let Pn be their convex hull, and denote by fi(Pn) the number of i-dimensional faces of Pn. A general method for computing the expectation of fi(Pn), i=0,…,d−1, is presented. This generalizes classical results of Efron (in the case i=0) and Rényi and Sulanke (in the case i=d−1) to arbitrary i. For random points chosen in a smooth convex body a limit law for fi(Pn) is proved as n→∞. For random points chosen in a polytope the expectation of fi(Pn) is determined as n→∞. This implies an extremal property for random points chosen in a simplex.