= Nearest neighbour distance
{title2=$\rho_{(k)}(x)$}
For observations $X_1,\ldots,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)\leq 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)\leq r)$, their count in that ball is <binomial distribution>[binomial]. Hence
$$
\mathbb P(\rho_{(k)}(x)\leq r)=\sum_{j=k}^n\binom nj p_x(r)^j(1-p_x(r))^{n-j}.
$$
This 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 distance>[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 <measurement calibration>[calibration] when the distance law is continuous.
Back to article page
