User:Bongilles/sandbox/Random convex hull

Random convex hulls form one of the most classical models of random polytopes, along with typical and zero cells of random tessellations.

Historical example : Sylvester's Four-point problem

In 1864 Sylvester posed the following question in the Educational time.

Show that the chance of four points forming the apices of a reentrant quadrilateral is 1/4 if they are taken in an indefinite plane...

With the modern eye of the probability theory it is clear that the problem is ill posed since the distribution of the points is not specified. Different assumptions lead to different answers. See for more information.

Model

They are build as the convex hull of a random discrete set of points in the Euclidean space $\mathbb {R} ^{d}$. The set of points is typically a collection of $n$ i.i.d. points or a Poisson point process. On this page the following notation is used. For a probability measure $\mu$ on $\mathbb {R} ^{d}$ the convex hull of $n\in \mathbb {N}$ independent points $X_{1},X_{2},\ldots$ distributed according to $\mu$ is denoted by

$$P_{n,d}^{\mu }=\operatorname {conv} (X_{1},\ldots ,X_{n}).$$

For a measure $\mu$ on $\mathbb {R} ^{d}$ and real number $\gamma >0$ the convex hull of a Poisson point process $Po(\gamma \mu )$ of intensity measure $\gamma \mu$ is denoted by

$$P_{\gamma ,d}^{\mu }=\operatorname {conv} (Po(\gamma \mu )).$$

In both of these cases the underlying measure is often the uniform distribution either inside a convex body or on its boundary, the normal distribution or more generally a log concave distribution.

The distribution of random polytopes are often studied through a number of their most common functionals such as the volume, number of faces or Hausdorff distance to a reference body. These functionals are described by statistics such as expectation and variance, asymptotic limit theorems (in most instances central limit theorem) or concentration bounds.

Probability that a point is in the convex hull

Wendel's theorem gives the probability that, under certain symmetry assumptions, the convex hull of i.i.d. points does not contain the origin.

Theorem (Wendel, 1962) — Let $1\leq d<n$ be integers. Assume that $\mu$ is rotationally invariant and assign measure $0$ to any linear hyperplane. Then

$$\mathbb {P} \left(0\not \in P_{n,d}^{\mu }\right)={\frac {1}{2^{n-1}}}\sum _{k=0}^{d-1}{\binom {n-1}{k}}.$$

A generalization by Wagner and Welzl says that if the symmetry assumption is dropped then the equality is replaced by an inequality.

Theorem (Wagner and Welzl, 2001) — Let $1\leq d<n$ be integers. Assume that $\mu$ is absolutely continuous with respect to the Lebesgue measure. Then

$$\mathbb {P} \left(0\not \in P_{n,d}^{\mu }\right)\geq {\frac {1}{2^{n-1}}}\sum _{k=0}^{d-1}{\binom {n-1}{k}}.$$

Equality holds if and only if the measure of any measurable cone $C$ is equal to the measure of its symmetry $-C$, equivalently

$$\mu (tx:x\in B,t\geq 0)=\mu (tx:x\in B,t\leq 0),$$

for any Borel set $B\subset \mathbb {R} ^{d}$.

Random simplices

If $n\leq d$ then $P_{n+1,d}^{\mu }$ is a random simplex. This simplex has dimension $n$ almost surely (assuming that $\mu (A)=0$ for any $(n-1)$-dimensional affine space). The expectation and higher moments of the volume $V_{n}(P_{n+1,d}^{\mu })$ have been computed explicitly when the points are distributed uniformly in a Euclidean ball or sphere.

Volume moments of random simplex (vertices uniformly distributed in a ball). — Let $d,n,k$ be integers with $1\leq n\leq d$ and $k\geq 0$. The convex hull of $n+1$ independent points uniformly distributed either in unit ball $B^{d}$ or the unit sphere $S^{d-1}$ of the $d$-dimensional Euclidean is almost surely a $n$-dimensional simplex. Its volume has $k$-th moment

$$\mathbb {E} \left(V_{n}(P_{n+1,d}^{\mathrm {Unif} (B^{d})})\right)^{k}={\frac {1}{(n!)^{k}}}\left({\frac {\kappa _{d+k}}{\kappa _{d}}}\right)^{n+1}{\frac {\kappa _{n(d+k)+d}}{\kappa _{(n+1)(d+k)}}}{\frac {b_{dn}}{b_{(d+k)n}}}$$

if all the points are distributed in the ball, and

$$\mathbb {E} \left(V_{n}(P_{n+1,d}^{\mathrm {Unif} (S^{d-1})})\right)^{k}={\frac {1}{(n!)^{k}}}\left({\frac {\omega _{d+k}}{\omega _{d}}}\right)^{n+1}{\frac {\kappa _{n(d+k-2)+d-2}}{\kappa _{(n+1)(d+k-2)}}}{\frac {b_{dn}}{b_{(d+k)n}}}$$

if all the points are distributed in the sphere, where $\kappa _{m}=V_{m}(B^{m})={\frac {\pi ^{\frac {m}{2}}}{\Gamma (1+{\frac {m}{2}})}}$ denotes the volume of the $m$-dimensional Euclidean unit ball, $\omega _{m}=\sigma _{m-1}(S^{m-1})=m\kappa _{m}={\frac {2\pi ^{\frac {m}{2}}}{\Gamma ({\frac {m}{2}})}}$ the surface area of its boundary, and $b_{dq}={\frac {\omega _{d-q+1}\cdots \omega _{d}}{\omega _{1}\cdots \omega _{q}}}.$

External links

• www.example.com