A STRONG LAW FOR THE LARGEST NEAREST-NEIGHBOUR LINK BETWEEN RANDOM POINTS

Abstract

Suppose that X₁, X₂, X₃, … are independent random points in R^d with common density f, having compact support Ω with smooth boundary ∂Ω, with f[mid ]_Ω continuous. Let Rⁿ_{i, k} denote the distance from X_i to its kth nearest neighbour amongst the first n points, and let M_{n, k} = max_{i[les ]n}Rⁿ_{i, k}. Let θ denote the volume of the unit ball. Then as n → ∞,

formula here

If instead the points lie in a compact smooth d-dimensional Riemannian manifold K, then nθM^d_{n, k}/ log n → (min_Kf)⁻¹, almost surely.