[Math] Probability that a convex shape contains the unit ball

mg.metric-geometrypr.probability

This probability problem seems interesting and I don't know if it has been solved before.

If you pick $n$ points uniformly at random from the surface of a $d$ dimensional sphere of radius $r>1$ with center at the origin, what is the probability that the convex hull of these points contains the unit ball (of dimension $d$) centered at the origin?

Best Answer

I misread the problem as that you just wanted the origin in the convex hull. This is a nice problem whose solution deserves to be better known, and this provides an upper bound for the probability that the convex hull contains the unit ball, and the limiting behavior as $r \to \infty$.

J. G. Wendel; "A Problem in Geometric Probability," Mathematica Scandinavica 11 (1962) 109-111. Zbl 108.31603

http://www.oeis.org/A008949

A special case ($4$ points on the $2$-sphere) was A6 on the 1992 Putnam exam.

You say both $d$-dimensional sphere and $d$-dimensional ball, though I would say the unit $3$-dimensional ball is bounded by a $2$-sphere. I'll assume you mean the ball in $\mathbb{R}^d$.

Consider the kernel of the map $\mathbb{R}^n \to \mathbb{R}^{d}$ of linear combinations of the points. Generically, this kernel has dimension $n-d$. The origin is contained in the convex hull precisely when this kernel intersects the positive orthant, since then some linear combination can be rescaled to have total weight $1$.

By symmetry, all orthants are hit equally often. (Negating a point reflects the kernel, and the action this generates is transitive on the orthants.) A generic $a$-dimensional subspace of $\mathbb{R}^{n}$ hits $2\sum_{i=0}^{a-1} {n-1 \choose i}$ out of $2^{n}$ orthants, so the probability that the convex hull of $n$ random points contains the origin is

$$2^{-n+1}\sum_{i=0}^{n-d-1} {n-1\choose i}. $$

This is an upper bound for the probability that the unit ball is contained in the convex hull.

The origin is contained in the convex hull with probability $1/2$ when the kernel and its orthogonal complement have the same dimension, when $n=2d$.