Maximal Minimal Spacing for Random Points

Abstract

Abstract From $$N+1$$ N + 1 random points on a line we wish to select $$M+1$$ M + 1 points so as to maximize the minimal spacing between them. We consider an initial configuration with independent and identically distributed spacings. Equivalently, the points are arrival times of a generic renewal process. For general spacing distributions, and for all $$M\le N$$ M ≤ N , we derive exact distributional identities for the maximal minimal spacing and obtain its asymptotic behavior. The problem admits a reformulation in terms of a threshold-resetting random walk. The walk advances by successive random increments and is reset to the origin upon exceeding a fixed threshold. The probability that the optimal spacing exceeds a given value coincides with the probability that the walk completes at least M reset cycles within N steps. This yields an exact representation in terms of first-passage functionals of the walk. The same mapping suggests a numerical scheme for the max-min spacing problem in the regime of large N and M , whose accuracy is tested against the exact results obtained here.