# Puzzle: stars in the universe - probability of mutual nearest neighbors

If the stars are distributed randomly within the universe, what is the probability for a star to be the nearest neighbor of a star that is its nearest neighbor? What if the number of spatial dimensions is higher than 3 or even grows without limit?

PS. I am interested in the asymptotic behavior with the number of stars growing without bound.

PPS. It's a well-known problem (the "birds on a wire problem" in higher dimensions) and I know the answers. However, no idea how to solve this analytically.

-
Are you assuming something about the geometry of the universe? Might not an unexpected shape change the answer? –  Geoff Robinson Jan 6 '13 at 12:49
What I had in mind is the asymptotic behavior in the limit of the number of stars N growing without limit. Should make the problem geometry independent, isn't it? –  Johannes Jan 6 '13 at 14:23
Johannes. are you convinced that the answer is the same for a ball as for a solid torus? –  Gerry Myerson Jan 6 '13 at 14:58
I was thinking that with the number of stars growing without limit the difference in probability between a ball or a solid torus to vanish. You guys seem to suggest this is wrong. Need to think about this. If what you suggest is correct, the 1D birds problem should give different answers depending on the landing geometry being a line segment or a circle. –  Johannes Jan 6 '13 at 15:09
"Randomly" isn't usually used by probabilists or statisticians as a synonym of "uniformly" or the like, but it seems widespread among mathematicians generally. –  Michael Hardy Jan 6 '13 at 18:08

Let's assume an infinite $n$-dimensional universe with stars distributed according to a Poisson process with density $\lambda$. The probability that there is no nearest neighbour within a hypherspherical volume $V=\alpha_nr^n$ of some star $S$ is $\exp(-\lambda V)=\exp(-\lambda\alpha_nr^n)$. Thus the density for finding the nearest neighbour at distance $r$ is $\lambda\alpha_nnr^{n-1}\exp(-\lambda\alpha_nr^n)$.

Now conditional on the nearest neighbour of $S$ being at distance $r$, there is no star in the sphere around $S$ with radius $r$, and the sphere around $S$'s nearest neighbour $T$ with radius $r$ overlaps this sphere in a symmetrical lune, whose volume is proportional to $r^n$, say, $\beta_nr^n$, with $\beta_1=1$ and $\beta_2=2\pi/3-\sqrt3/2\approx1.2284$ (see MathWorld). The probability that there is no other star within distance $r$ of $T$, and hence $S$ is the nearest neighbour of $T$, is $\exp(-\lambda(\alpha_n-\beta_n)r^n)$. Thus the total probability of $S$ being the nearest neighbour of $T$ is

$$\int_0^\infty\lambda\alpha_nnr^{n-1}\exp(-\lambda\alpha_nr^n)\exp(-\lambda(\alpha_n-\beta_n)r^n)\mathrm dr=\frac{\alpha_n}{2\alpha_n-\beta_n}\;.$$

For $n=1$, we have $\alpha_1=2$ and $\beta_1=1$, so the probability is $p_1=2/3$. For $n=2$, we have $\alpha_2=\pi$ and $\beta_2=2\pi/3-\sqrt3/2$, so the probability is

$$p_2=\frac\pi{2\pi-2\pi/3+\sqrt3/2}=\frac1{4/3+\sqrt3/(2\pi)}\approx0.6215\;.$$

We can write the probability for $n$ dimensions as

$$p_n=\frac{\displaystyle\int_{-\pi/2}^{\pi/2}\cos^nx\,\mathrm dx}{2\displaystyle\int_{-\pi/2}^{\pi/6}\cos^nx\,\mathrm dx}\;,$$

the ratio of the volume of a sphere to the volume of the union of two spheres with centres on each other's surfaces. Here's a Sage worksheet that calculates these probabilities for $n$ up to $10$:

sage: t=var('t');
sage: def f(n,x): return integral (cos (t)^n,t).substitute (t=x);
sage: def g(n): return (f (n,pi/2) - f (n,-pi/2)) / (2 * (f (n,pi/6) -  f(n,-pi/2)));
sage: [g(n) for n in range (1,11)]
[2/3, 6*pi/(8*pi + 3*sqrt(3)), 16/27, 12*pi/(16*pi + 9*sqrt(3)), 256/459, 30*pi/(40*pi + 27*sqrt(3)), 2048/3807, 840*pi/(1120*pi + 837*sqrt(3)), 65536/124659, 840*pi/(1120*pi + 891*sqrt(3))]
sage: [g(n).n () for n in range (1,11)]
[0.666666666666667, 0.621504896887431, 0.592592592592593, 0.572465550279709, 0.557734204793028, 0.546588665492621, 0.537956396112425, 0.531153988127765, 0.525722170079978, 0.521339529895594]


The probability for odd $n$ is rational, and the probability for even $n$ is of the form $3/(4+q_n\sqrt3/\pi)$ with $q_n$ rational. (You can show this analytically by deriving a recurrence relation for $\int_0^x\cos^nx\,\mathrm dx$ by integrating by parts.) Here are tables for odd $n$

$$\begin{array}{r|c|c} n&p_n&p_n\\\hline 1&\frac23&0.66667\\\hline 3&\frac{16}{27}&0.59259\\\hline 5&\frac{256}{459}&0.55773\\\hline 7&\frac{2048}{3807}&0.53796\\\hline 9&\frac{65536}{124659}&0.52572\\ \end{array}$$

and even $n$:

$$\begin{array}{r|c|c} n&q_n&p_n\\\hline 2&\frac12&0.62150\\\hline 4&\frac34&0.57247\\\hline 6&\frac9{10}&0.54659\\\hline 8&\frac{279}{280}&0.53115\\\hline 10&\frac{297}{280}&0.52134\\ \end{array}$$

Thus, for stars in our three-dimensional universe the probability is $16/27\approx0.59259$. Our star, the sun, is not its nearest neighbour's nearest neighbour: Its nearest neighbour is Proxima Centauri at a distance of about $4.2$ light-years, whose nearest neighbour is the binary star system Alpha Centauri.

The ratio of the volume of the lune to the volume of the sphere goes to zero with $n\to\infty$, so the probability for a star to be the nearest neighbour of its nearest neighbour goes to $1/2$.

-
Thanks for the follow-up, joriki. –  Johannes Feb 20 '13 at 18:13