A disc contains $n$ independent uniformly random 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}$.
What does the average cluster size approach as $n\to\infty$ ?
My attempt:
I made a random point generator that generates $20$ random points. The average cluster size is usually approximately $3$.
I considered what happens when we add a new random point to a large set of random points. Adding the point either causes no change in the number of clusters, or it causes the number of clusters to increase by $1$ (Edit: this is not true, as noted by @TonyK in the comments). The probability that adding a new point increases the number of clusters by $1$, is the reciprocal of the answer to my question. (Analogy: Imagine guests arriving to a party; if 25% of guests bring a bottle of wine, then the expectation of the average number of guests per bottle of wine is $4$.) But I haven't worked out this probability.
Context:
This question was inspired by the question Stars in the universe – probability of mutual nearest neighbors.
Edit: Postd on MO.
Best Answer
This is Stars in the universe - probability of mutual nearest neighbors in disguise. If there are $k$ pairs of mutual nearest neighbours, then there are $n-k$ edges (since $n$ edges are drawn and $k$ of them occur twice). There can’t be any cycles (unless it’s an Escher disk) because the distances would have to decrease all along the cycle. So the graph is a forest of $n-(n-k)=k$ trees. For $n\to\infty$, the fraction of points that are their nearest neighbour’s nearest neighbour goes to the probability for that to happen; $\frac kn$ is half that fraction, and the expected average cluster size is the reciprocal of that. In two dimensions, that yields
$$ 2\left(\frac43+\frac{\sqrt3}{2\pi}\right)\approx3.218\;. $$