2
$\begingroup$

Problem. Fix a positive real $r>0$ and a positive integer $n>0$. Consider an independent, identical sample $X_1, \ldots X_n$ drawn from the uniform distribution over the unit $d$-sphere $\mathbb S^d \subset \mathbb R^{d+1}$. What is the probability that $\|X_i - X_j\| \le r$ for every $(i,j)$?

I could work out an iterated integral giving an exact formula for $d=1$, although the integral itself is quite complicated. Before proceeding further with calculations, I wanted to know if there is a prior literature on this problem. This area of mathematics seems to go by the name of geometric probability (e.g. this 1978 textbook by Solomon).

A similar, well-studied problem is the probability that spherical caps of radii $r$ centered at $X_1, \ldots X_n$ covers the whole sphere. A spherical cap here refers to sets of the form $\{ y \in \mathbb{S}^d | \|x-y\| \le r \}$ for each fixed $x \in \mathbb S^d$. For this problem, an exact solution is known for $d=1$ (Stevens 1939), and some work on upper and lower bounds of the probability are known for $d>1$ (Gilbert 1965). The $d=1$ case by Stevens is as follows. The probability that $n$ randomly chosen arcs of length $a$ from a circle of circumference $1$ is equal to: $$\sum_{k = 0}^{\lfloor 1/a \rfloor} (-1)^k \binom nk (1- ka)^{n-1} $$

$\endgroup$
6
  • 2
    $\begingroup$ I think this paper might be of help: Random Point Sets on the Sphere --- Hole Radii, Covering, and Separation (arxiv.org/abs/1512.07470). Specifically, you're asking about the "separation" part. I think the paper mainly deals with the asymptotics for large n, but might have some info for finite n. $\endgroup$ Mar 2, 2022 at 23:21
  • 2
    $\begingroup$ And arXiv's traceback helpfully reminded me I have previously linked to this paper on MO on a different question. So that question might be relevant too: mathoverflow.net/questions/245027/… $\endgroup$ Mar 2, 2022 at 23:23
  • $\begingroup$ Thanks for the reference Yoav. I think separation in that paper is the minimum of all pairwise distances, while I am considering the maximum of all pairwise distances. Do you know if this is addressed there or elsewhere? $\endgroup$
    – Uzu Lim
    Mar 6, 2022 at 20:32
  • 2
    $\begingroup$ Sorry I misread your question the first time. So it sounds like you're asking about the diameter of a random point set? I unfortunately don't recall anything helpful to point you to for that question. A quick search on Google Scholar turned up some papers looking at the diameter of a set of uniformly random point drawn from the ball and from a compact plane set. Maybe those could be helpful. (doc.rero.ch/record/311708/files/10687_2007_Article_38.pdf, doi.org/10.1239/aap/1019160946) $\endgroup$ Mar 7, 2022 at 3:14
  • $\begingroup$ @YoavKallus thanks a lot! "Diameter" is a better phrasing of the problem I posed. $\endgroup$
    – Uzu Lim
    Mar 7, 2022 at 18:32

1 Answer 1

1
$\begingroup$

Not an answer; too long for a comment:

There seem to be extensive results in the paper https://arxiv.org/abs/0712.2816 Coverage processes on spheres and condition numbers for linear programming by Bürgisser et al. I am unsure whether they will help with your problem.

From the abstract:

Let $p(n,m,\alpha)$ be the probability that $n$ spherical caps of angular radius $\alpha$ in $S^m$ do not cover the whole sphere $S^m.$ We give an exact formula for $p(n,m,α)$ in the case $\alpha \in [π/2,π]$ and an upper bound for $p(n,m,\alpha)$ in the case $\alpha \in [0,π/2]$ which tends to $p(n,m,\pi/2)$ when $\alpha \rightarrow \pi/2.$

In the case $\alpha \in [0,\pi/2]$ this yields upper bounds for the expected number of spherical caps of radius $\alpha$ that are needed to cover $S^m.$

The authors then relate the results to the condition number of a random linear program in $\mathbb{R}^{m+1}.$

$\endgroup$
1
  • $\begingroup$ Thank you. Do you know if this paper addresses the main question (tightly placing spherical caps) instead of the question of covering a sphere by spherical caps? $\endgroup$
    – Uzu Lim
    Mar 2, 2022 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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