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$ Commented 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$ Commented 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
    Commented 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$ Commented Mar 7, 2022 at 3:14
  • $\begingroup$ @YoavKallus thanks a lot! "Diameter" is a better phrasing of the problem I posed. $\endgroup$
    – Uzu Lim
    Commented 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
    Commented Mar 2, 2022 at 21:15

You must log in to answer this question.

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