 Nearest neighbour distance

For observations $X_1,\dots ,X_n$ in a metric space and a fixed query point $x$, the order-$k$ nearest neighbour distance ${\rho }_{(k)}(x)$ is the $k$th smallest of the distances $d(X_i,x)$, counting ties with multiplicity. Equivalently ${\rho }_{(k)}(x)\le r$ exactly when the closed radius-$r$ ball contains at least $k$ observations.

If the observations are independent and identically distributed and $p_x(r)=\mathbb{P}(d(X_i,x)\le r)$, their count in that ball is binomial. HenceThis formula also handles distance distributions with atoms. If the common distance distribution is continuous, independent observations have no tied distances almost surely. Continuity alone does not ensure this under dependence: taking every $X_i$ equal to the same continuously distributed random point forces all distances to tie.

Nearest-neighbour distances convert local sample counts into geometric scales. In density estimation, a small radius enclosing $k$ observations indicates a region with relatively high probability per unit volume. The probability content of a nearest neighbour ball gives an exact distributional calibration when the distance law is continuous.