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.

  • 1
    $\begingroup$ Are you assuming something about the geometry of the universe? Might not an unexpected shape change the answer? $\endgroup$ Jan 6, 2013 at 12:49
  • $\begingroup$ 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? $\endgroup$
    – Johannes
    Jan 6, 2013 at 14:23
  • $\begingroup$ Johannes. are you convinced that the answer is the same for a ball as for a solid torus? $\endgroup$ Jan 6, 2013 at 14:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Johannes
    Jan 6, 2013 at 15:09
  • 2
    $\begingroup$ "Randomly" isn't usually used by probabilists or statisticians as a synonym of "uniformly" or the like, but it seems widespread among mathematicians generally. $\endgroup$ Jan 6, 2013 at 18:08

1 Answer 1


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

  • $\begingroup$ Thanks for the follow-up, joriki. $\endgroup$
    – Johannes
    Feb 20, 2013 at 18:13

You must log in to answer this question.

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