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?

$\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$ Sep 9, 2013 at 12:32
  • 1
    $\begingroup$ If you care about the exponential lower bound, send me an email. $\endgroup$ 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
    Sep 14, 2013 at 12:52

2 Answers 2

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

$\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$ 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$ Sep 8, 2013 at 15:53
  • $\begingroup$ Good point, I assumed something else was asked. $\endgroup$ 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
    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$ Sep 9, 2013 at 16:00
1
$\begingroup$

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

$\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
    Sep 8, 2013 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.