up
Random Neighbors

This comes from Keith Lynch, by way of the usenet group geometry.puzzles.

The Question
If a large number of points are distributed uniformly evenly over a region,
what is the probability that a given point's nearest neighbor's nearest neighbor
is that same given point again ?

I don't know the answer,
but theres a javascript simulation (way) down the page.













































































































Simulations! Love Em!

Number of Dimensions:  
Number of points to distribute:
 

This simulation uniformly randomly distributes points over a unit "square" region.
EG, a unit line segment, a 1x1 square, a 1x1x1 cube, etc.
Then it just brute-forces it. So it's an O(n^2) thing, so watch out with large numbers!
I'm a little surprised at the results, so if anyone wants to check my code that would be swell,
just view the page source.

results. several trials.
with D > 1 the deviation is a significant, so the numbers below are my eyeball averaging of several runs.

dimensionssimulated probabilityN#trials
166% (2/3)1000a few
2~62.31% 20000a few
3~60% 1000a few
4~55% 1000a few
5   a few
6   a few
7   a few
8~49% 1000a few
9~50.1% 100003

it makes sense that higher dimension means the probability drops
(because each point can have more equidistant neighbors),
but i'm surprised the values don't drop off faster.

Peter Ralph is getting similar but not identical results with a derived solution,
but that solution itself involves simulation to calculate an integral, so there may be room for discrepency.
.. more to come!