Skip to content
Get started

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)+
  1. Only three consecutive gaps decide whether a point and its right neighbour are mutual.
  2. Those gaps are i.i.d. in the limit; what is the chance the middle one is the smallest?

Answer

Reveal 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

Related questions