# For 1-NN (Next Neighbor), what is the expectation of the largest probability of being the nearest neighbor?

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

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