21
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ No time for a real answer, but I would start by looking at papers by Adamczak, Litvak, Pajor, Tomczak-Jaegermann, and their various collaborators. Their results are mostly phrased in terms of singular values of random matrices but can be interpreted in terms similar to yours (the translation is discussed in at least some of their papers). Mostly their results have direct implications for a variant of your problem in which you take the "symmetric" convex hull, but I think there are nonsymmetric versions of the results somewhere. $\endgroup$
    – Mark Meckes
    Commented Sep 9, 2013 at 12:32
  • 1
    $\begingroup$ If you care about the exponential lower bound, send me an email. $\endgroup$
    – Bill Johnson
    Commented Sep 10, 2013 at 14:03
  • 1
    $\begingroup$ The obvious reformulation is "How many random rotations does it take to cover the whole sphere by the images of a fixed spherical cap with probability about $1/2$". The obvious bounds are "at least $S^{-1}$ and at most $S^{-1}(d\log d+\log(S^{-1}))$" where $S$ is the relative area of the cap and those can be (and, most likely, have been) improved though changing $r$ just a tiny little bit has more effect on the answer than the difference in the factor at $S^{-1}$ except when $r$ is really large. $\endgroup$
    – fedja
    Commented Sep 14, 2013 at 12:52

2 Answers 2

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Question seems to be asking something more difficult than what you're answering. You're telling when the convex hull contains the origin, question asks for the convex hull containing the fixed size ball centered around the origin. $\endgroup$
    – Zsbán Ambrus
    Commented Sep 8, 2013 at 15:52
  • 1
    $\begingroup$ The OP wants the convex hull to contain the entire unit ball, not just the origin. For fixed $r>1$ the number $n$ of points must be exponential in $d$ (since e.g. for $\ell_2^d$ to well-embed into $\ell_\infty^m$ the dimension $m$ must be exponential in $d$). I think convex geometers have rather precise estimates on the dependence of $n$ on $d$ and $r$ and one of them will probably answer the question in due course. $\endgroup$
    – Bill Johnson
    Commented Sep 8, 2013 at 15:53
  • $\begingroup$ Good point, I assumed something else was asked. $\endgroup$
    – Douglas Zare
    Commented Sep 8, 2013 at 15:54
  • $\begingroup$ Thank you. As I also have a practical application in mind, is it possible to derive a reasonable lower bound? In my application $d$ is in the dozens and is fixed and I can vary $n$ and $r$. $\endgroup$
    – Simd
    Commented Sep 8, 2013 at 17:57
  • 2
    $\begingroup$ As I said, the lower bound is exponential in $d$ for any choice of points. Explicitly, $n$ is at least $\exp (d/(64r^2))$ with the only possible improvement being in the constant $64$. All this follows from standard local Banach space theory. The point is that if $\ell_2^d$ well embeds into $\ell_\infty^n$, then $n$ is exponential in $d$. Your constant $r$ defines the notion of "well". Saying that the convex symmetric hull of $n$ points can contain the unit ball is the same as saying that $\ell_2^d$ embeds into $\ell_\infty^n$ with distortion at most $r$. $\endgroup$
    – Bill Johnson
    Commented Sep 9, 2013 at 16:00
1
$\begingroup$

I hope you can find a partial answer here. At least for $n=d+2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. My interest is, for example, in understanding how large $n$ and $r$ have to be for the probability to be $1/2$ so it is a little different. $\endgroup$
    – Simd
    Commented Sep 8, 2013 at 13:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .