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

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.

-

## 1 Answer

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 →∞). 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-(N-1)d/L)N.

Integrating over 0≤d≤L/(N-1) gives the expected minimum distance of L/(N2-1).

-
George, thanks for your response, and I agree with your argument. I also just ran a simulation and the results match nicely. – Mensen Oct 19 '09 at 23:37
George, your card shuffling formulation makes the problem very intuitive, and I enjoyed reading it. – Mensen Oct 20 '09 at 19:36
An excellent restatement of the problem in a very intuitive manner. – Sparr Feb 27 '10 at 20:07
Great answer. A small point for others confused as I was: I believe that since it is the probability of at least distance d, the cumulative density function (cdf) is 1-f, or 1-(1-(N-1)d/L)^N, and pdf is the derivative of the cdf, or n(n-1)(1-(n-1)d)^(N-1) for L=1. – dfrankow Dec 2 '14 at 16:59