Mean minimum distance for N random points on a one-dimensional line

Question

Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long chains of conditional probabilities) of deriving the probability 'p' that the minimum distance between any pair of these points is larger than some value 'k' -i.e. if the line was an array, there would be more than 'k' slots/positions between any two point. Well that, or an expression for the mean minimum distance (MMD) for a pair of points in the set - referring to the smallest distance between any two points that can be found, not the mean minimum/shortest distance between all possible pairs of points.

I was unable to find an answer to this question after a literature search, so I was hoping someone here might have an answer or point me in the right direction with a reference. This is for recreational purposes, but maybe someone will find it interesting. If not, apologies for the spam.

Answer 1

This can answered without any complicated maths.

It can be related to the following: Imagine you have $N$ marked cards in a pack of $m$ cards and shuffle them randomly. What is the probability that they are all at least distance $d$ apart? Consider dealing the cards out, one by one, from the top of the pack. Every time you deal a marked card from the top of the deck, you then deal $d$ cards from the bottom (or just deal out the remainder if there's less than $d$ of them). Once all the cards are dealt out, they are still completely random. The dealt out cards will have distance at least d between all the marked cards if (and only if) none of the marked cards were originally in the bottom $(N-1)d$. The probability that the marked cards are all distance d apart is the same as the probability that none are in the bottom $(N-1)d$.

The points uniformly distributed on a line segment is just the same (considering the limit as $m$$\rightarrow∞$). The probability that they are all at least a distance $d$ apart is the same as the probability that none are in the left section of length $(N-1)d$. This has probability $(1-\frac{(N-1)d}{L})^N$.

Integrating over $0$$\le$$d$$\le$$\frac{L}{(N-1)}$ gives the expected minimum distance of $\frac{L}{(N^2-1)}$.

Answer 2

Let $(x_1,x_2,\cdots,x_N)$ be the position of the $N$ points on the interval $[0,1]$. We can always permute the scripts to $x_1\le x_2\cdots \le x_N$ for any ordering of the points on the interval. The original probability is then $N!$ multiple of the ordered probability. Now let $y_1:=x_1;\, y_i:=x_i-x_{i-1}-d,\,\forall i\ge2$. The required condition is then $\big\{y_i\ge0,\,\forall i \bigwedge \sum_{i=1}^N y_i\le 1-(N-1)d\big\}$. The probability of this set is $\frac1{N!}(1-(N-1)d)_+^N$. The desired probability is then $(1-(N-1)d)_+^N$.