1
$\begingroup$

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$?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.