14
$\begingroup$

A disc contains $n$ independent uniformly distributed points. Each point is connected by a line segment to its nearest neighbor, forming clusters of connected points.

For example, here are $20$ random points and $7$ clusters, with an average cluster size of $\frac{20}{7}$.

enter image description here

What is the expectation of the average cluster size, as $n\to\infty$ ?

I made a random point generator that generates $20$ random points. The expectation of the average cluster size seems to be approximately $3$.

This question was posted on Math SE. This answer provides useful context (but does not answer the question).

This question was inspired by the Math SE question Stars in the universe - probability of mutual nearest neighbors.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ The points are on the disc, not on the circle. $\endgroup$
    – YCor
    Commented Jan 15 at 22:57
  • $\begingroup$ @YCor Thanks, I have changed it to disc. $\endgroup$
    – Dan
    Commented Jan 15 at 23:03
  • 8
    $\begingroup$ The graph has no cycles, so the number of components is $n$ minus the number of edges, which is equal to the number of pairs which are mutually nearest neighbours. As $n\to\infty$, what you see locally around a typical point looks like a Poisson process. So the average number of clusters per point tends to $q_2/2$, where $q_2$ is the probability for a typical point in a 2-dimensional Poisson process to be in a mutually-nearest-neighbour pair. But isn't that already what's calculated by joriki in the "Stars in the universe" question you linked to?: $q_2/2\approx0.31075$. What am I missing...? $\endgroup$
    – James Martin
    Commented Jan 16 at 0:16
  • 3
    $\begingroup$ @DanielAsimov The description doesn't specify what happens if there is a point with two equally near nearest neighbours. But anyway, if the points are uniformly distributed in continuous space, the probability of that happening is $0$. $\endgroup$
    – James Martin
    Commented Jan 16 at 2:08
  • 2
    $\begingroup$ @DanielAsimov Suppose no two points are exactly the same distance apart. Then we have a directed graph in which every vertex has outdegree one, so each connected component of the underlying undirected graph is unicyclic (the cycle might have just 1 or 2 vertices). In such a component, consider the pair of points that are closest together; they must form a cycle of length 2. But in the underlying undirected graph, a cycle of length 2 manifests itself as a single undirected edge. $\endgroup$
    – Timothy Chow
    Commented Jan 16 at 12:18

1 Answer 1

Reset to default
12
$\begingroup$

I think the comment by @James Martin answers my question.

The number of clusters equals the number of pairs of points that are mutually nearest neighbors. The probability that a point is in a mutually nearest neighbor pair is $p=\dfrac{1}{\frac43+\frac{\sqrt3}{2\pi}}\approx0.62150$ (proof). So for $n$ points, the expected number of pairs that are mutually nearest neighbors approaches $\frac{np}{2}$. So the expected number of points per cluster approaches $\frac2p=\color{red}{\frac83+\frac{\sqrt3}{\pi}}\approx 3.218$.

Curiously, this is $(e+\frac12)\times0.99991...$ Is that just a coincidence?

(I may not be using terminology precisely enough; feel free to edit.)

Improve this answer
$\endgroup$
19
  • $\begingroup$ Experimentally I keep getting values larger than $3.218$. Actually I never got anything below $3.22$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 16 at 4:35
  • $\begingroup$ @მამუკაჯიბლაძე I could be wrong. What do your experiments suggest for the expectation? $\endgroup$
    – Dan
    Commented Jan 16 at 4:40
  • $\begingroup$ Not sure, but certainly above $3.225$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 16 at 4:42
  • 1
    $\begingroup$ Here is Mathematica code f[M_, A_] := Mean[Table[With[{pts = Select[RandomReal[{-1, 1}, {M, 2}], Norm[#] <= 1 &]}, N[Length[pts]/Length[ConnectedComponents[Graph[Table[p \[UndirectedEdge] First[SortBy[Complement[pts, {p}], EuclideanDistance[#, p] &]], {p, pts}]]]]]], {A}]] $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 16 at 4:54
  • 1
    $\begingroup$ Oh I see - you suggest that the expectations decrease monotonously with $n$. This souns very convincing indeed. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jan 16 at 5:08

You must log in to answer this question.

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