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