# Two geometric probability questions (one answered, one more to go)

1. Given $n$ independent uniformly distributed points on $S^2$, what's the distribution of the distance between two closest points?

2. Consider $n$ iid uniform points on $S^1$, $Y_1, \ldots, Y_n$, in counterclockwise order. Now let $I_1 = Y_2-Y_1, \ldots, I_n = Y_1 - Y_n$ be the spacings between consecutive points. Finally order the spacing sequence into $I_{(1)} < I_{(2)} < \ldots < I_{(n)}$. They will also generate a spacing sequence, of size $n-1$, $J_1 = I_{(2)} - I_{(1)}, \ldots, J_{n-1} = I_{(n)} - I_{(n-1)}$. What's the distribution of this last sequence? In particular, what's the mean value of the smallest $J$ and largest $J$?

-
For the first problem, I think you just fix one of the points to be the north pole, and look at surface areas of caps. – Eric Tressler Nov 11 '10 at 5:53
The answer will depend on whether you're talking about chord distance or distance on the surface, though. – Eric Tressler Nov 11 '10 at 5:55
These two are essentially the same, aren't they? – John Jiang Nov 11 '10 at 6:31
I mean there is simple formula relating the two, so the distribution of one would be a simple transform of the other. – John Jiang Nov 11 '10 at 6:32

There is an asymptotic formula for the minimal spherical distance when $n$ is large (see e.g. the PhD thesis "Random Diameters and Other U-Max-Statistics" by M. Mayer, Corollary 3.37):

Theorem. Assume that the points $\xi_1,\xi_2,...,\xi_n$ are independent and uniformly distributed on $\mathbb S^{d−1}$. Let $S_n$ be the smallest central angle formed by point pairs within the sample. Then for $t > 0$ $$P\{n^{2/(d-1)}S_n\leq t\}=1-\exp\left(-\frac{\Gamma(\frac{d}{2})}{4\pi^{1/2}\Gamma(\frac{d+1}{2})}t^{d-1} \right)+\mathcal O(n^{-1}).$$

I am not sure if there is a nice explicit formula for finite $n$.

In fact, the knowledge of the exact form of the distribution $P\{S_n\leq\theta\}$ on $\mathbb S^2$ would lead to a solution of the Tammes packing problem (which is only solved for a few values of $n$ to the best of my knowledge).

-

2) This is, of course, the same as saying about spacings between uniform points on a segment (you can say that $Y_1=0$, for example). Let it be the segment $[0,1]$.

Now the joint distribution of $I_1,\dots, I_{n}$ is the same as of $E_1/E,\dots, E_n/E$, where $E_1,\dots, E_n$ are iid exponential distributed, $E=\sum_{k=1}^n E_k$ (see Devroye Non-Uniform Random Variate Generation, p.208). So the distribution of $I_{(1)},\dots, I_{(n)}$ is the same as of $E_{(1)}/E,\dots, E_{(n)}/E$. But the joint distribution of $\{E_{(k)}-E_{(k-1)},k=1,\dots,n\}$ ($E_{(0)}:=0$) is the same as of $\{(n-k+1)^{-1} E_k,k=1,\dots,n\}$ (ibid, p.211).

So the distribution of $J_1,\dots, J_n$ is the same as of $\{(n+k-1)^{-1} E_k/E,k=1,\dots,n\}$, where $E_1,\dots, E_k$ are iid exponential rv's, $E=\sum_{k=1}^n E_k$. And this is, by the previous paragraph, equivalent to saying that the distribution is the same as of $\{(n-k+1)^{-1} I_k,k=1,\dots,n\}$.

These are not independent, but very close to be, and from here you can find the distribution of maximum and minimum (but nothing very pleasant there, as the variables in question are not identically distributed; a formula for the expectation looks extremely ugly).

How to get distribution of $J$ omitting $E$. In fact, this is simple owing to the fact that the ordering map on the simplex $\{(t_1,\dots,t_n)|t_j\ge 0,\sum_j t_j=1\}$ (the support of $I$) is picewise linear, and moreover each image has the same number of preimages due to the apparent symmetry. So the distribution of $\{I_{(1)},\dots,I_{(n)}\}$ is uniform on its support. Now we have a one-to-one linear map to $J$. So $J$ is also uniformely distributed. So it's only about finding its support, which is simple, as John Jiang noted.

-
Thank you for the great answer. I am always scared of exact formulas. – John Jiang Nov 12 '10 at 6:16
@John Jiang: You're warmly welcome. Precise formulas useless here, if you want, I can look into asymptotics. – zhoraster Nov 12 '10 at 8:01
@zhoraster: actually I was able to use the formula you gave above to compute the exact distribution of the minimum: $P(\min J_i > y) = (1-y n(n+1)/2)^{n-1}$, so it doesn't seem bad at all. What I did is a pretty geometric argument. Notice that $y$ ranges between $0$ and $2/(n(n+1))$, as expected from its being the smallest gap of gaps of $n$ points on the circle. Using that formula, we just need to integrate $P(\min J_i > y)$ for $y \in [0,2/(n(n+1))]$ to get the expected value, which is $2/((n-1)n(n+1))$. – John Jiang Nov 12 '10 at 9:26
@John Jiang: I see, I had another formula initially (from $E_k/E$), just didn't see that it can be reduced to this. I even discovered now that it is quite straightforward to go from the distribution of $I$ to the one of $J$ omitting $E$. Anyway, glad that you've found it, congratulations! – zhoraster Nov 12 '10 at 10:09
Thanks again! Your geometric ansatz really helped. I'd be glad to hear how to go directly from I to J, as I am still interested in the entire J sequence, and hopefully prove something nice about them. – John Jiang Nov 12 '10 at 16:41