Maximal Minimal Spacing for Random Points

Abstract

From $N+1$ random points on a line we wish to select $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$, 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.

24 pages, 7 figures. Typos fixed and references added

References in corpus (10)

• The large deviation approach to statistical mechanics
• Universal Order Statistics of Random Walks
• Exact Statistics of the Gap and Time Interval Between the First Two Maxima of Random Walks
• Extreme gaps between eigenvalues of random matrices
• Maximal Diversity and Zipf's Law
• Generic aspects of the resource theory of quantum coherence
• Target Search Optimization by Threshold Resetting
• Volume of the set of LOCC-convertible quantum states
• First Passage Resetting Gas
• The Most Dispersed Subset of Random Points in ${\mathbb{R}}^d$