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