Nearest neighbour distance (${\rho }_{(k)}(x)$)

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.

For independent and identically distributed random variables with continuous distance distribution function $p_x$, the probability integral transform makes the probability content of the order-$k$ nearest ball a uniform order statistic, with the Beta distribution $\mathrm{Beta}(k,n+1-k)$.

For a strictly positive probability density function with Lipschitz bound $L$, $p_x(r)={\int }_{x-r}^{x+r}f(y)dy$ satisfies $|p_x(r)-2rf(x)|\le L{r}^2$. If $0<s<1$ and $s\le f(x{)}^2/L$, monotonicity gives $p_x^{-1}(s)\le s/f(x)$ and hence $|2f(x)p_x^{-1}(s)-s|\le L{s}^2/f(x{)}^2$. The Lipschitz density height bound prevents extending this local argument to every $s\in (0,1)$ by assuming $f(x)\ge \sqrt{L}$ for a strictly positive density.