Scatter n random points in a disc and join each to its nearest neighbour — how large do the clusters get?

And that fraction is a known quantity, which is why the limit exists.

The probability that a given point's nearest neighbour also has that point as its nearest neighbour is a constant in the limit, independent of n and of the shape of the region — it depends only on the dimension. That is exactly the scale-free property you noticed.

The reasoning is local: whether two points are mutually nearest depends only on whether any third point falls in a particular lens-shaped region between them, and that probability is determined by the ratio of areas, which does not change as you scale the whole picture up.

In two dimensions the resulting fraction gives an average cluster size somewhere around 2.7 to 3. Your twenty-point sample giving 2.9 is comfortably in that range, which is a good sign that the small case is already close to the limit.

The boundary effects — points near the edge of the disc having fewer neighbours on one side — vanish as n grows, since the fraction of points near the boundary goes to zero.

Worth adding that the same question in one dimension is a nice sanity check and is fully tractable by hand.

Points on a line, each joined to its nearest neighbour: work out the probability that two consecutive points are mutually nearest and you get an exact constant, and hence an exact expected cluster size. It is a good exercise because the geometry is trivial and the argument is identical in structure.

The general point worth taking away is that these nearest-neighbour graphs are quite rigid objects. Each vertex has out-degree one, cycles can only have length two, and every component contains exactly one cycle. That structure is what makes the counting argument above work at all, and it is the sort of thing that looks like a coincidence until you prove it.

This is also a nice one to just simulate, and simulating it is more convincing than any of the above.

Generate ten thousand points, compute nearest neighbours, count components. Repeat a few times. The average settles down quickly and you will see the constant emerge.

Doing that alongside the derivation is worthwhile, because it is easy to make an error in the mutual-pair probability and a simulation catches it immediately.

Your instinct that it settles on a constant is right, and the way in is to count edges rather than clusters.

Each of the n points draws one segment to its nearest neighbour, so n segments are drawn. But some of them are drawn twice: whenever two points are mutually nearest neighbours, both draw the same segment.

So if there are k mutual pairs, the number of distinct edges is n − k.

Now, the clusters formed this way turn out to contain exactly one cycle each, and that cycle is always a mutual pair — a point cannot be nearest to a point that is nearest to a third, and so on, without the chain terminating in a mutual pair. So the number of clusters equals the number of mutual pairs, k.

Which gives you the answer in one line: average cluster size is n / k. Everything now depends on the fraction of points that are in a mutual pair.