Mutual nearest neighbours
A very large number of points are dropped independently and uniformly on a circle. Two points are mutual nearest neighbours if each is the other's closest point. In the limit of many points, what is the expected fraction of points that belong to a mutual-nearest-neighbour pair? Give four decimals.
Show hints (2)+
- Only three consecutive gaps decide whether a point and its right neighbour are mutual.
- Those gaps are i.i.d. in the limit; what is the chance the middle one is the smallest?
Answer
Reveal answer →Final answer
0.6667 (± 0.002)
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading