Suppose we sample $n$ points $X_1,X_2,...,X_n$ independently from a distribution $P_X$ on $[0,1]^d$. For a new point $X$ independently from $P_X$, we find its nearest neighbor in $X_1,X_2,...,X_n$. Each of $X_1,...,X_n$ has a probability of being the nearest neighbor, and let $p_j$ be the probability of $X_j$ being the nearest neighbor. What is an upper bound for the largest $p_j$,. i.e., $E[\max_{1\leq j\leq n} p_j]$?

For example, if $d=1$ and $P_X$ is uniform on $[0,1]$, $2H(n)/n$ is a good upper bound; the $n$ points divide $[0,1]$ into $n+1$ segments. The longest segment is of length $H(n)/n$, and the largest probability of being NN is no larger than twice the longest segment.

What is a good bound for general $d$?

  • 1
    $\begingroup$ I think your question can be rephrased as asking for the expected volume of the largest Voronoi cell. $\endgroup$ – Anthony Quas Jan 12 '18 at 16:57
  • $\begingroup$ Yes I just found that - is there any existing results? $\endgroup$ – Yichong Xu Jan 13 '18 at 3:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.