36
$\begingroup$

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.

$\endgroup$

2 Answers 2

61
$\begingroup$

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)}$.

$\endgroup$
5
  • $\begingroup$ George, thanks for your response, and I agree with your argument. I also just ran a simulation and the results match nicely. $\endgroup$
    – Mensen
    Oct 19, 2009 at 23:37
  • $\begingroup$ George, your card shuffling formulation makes the problem very intuitive, and I enjoyed reading it. $\endgroup$
    – Mensen
    Oct 20, 2009 at 19:36
  • $\begingroup$ An excellent restatement of the problem in a very intuitive manner. $\endgroup$
    – Sparr
    Feb 27, 2010 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – dfrankow
    Dec 2, 2014 at 16:59
  • $\begingroup$ The answer is wrong—the stated value is just an approximation of the probability. For the exact value, see jstor.org/stable/2681879 and doi.org/10.1016/j.ipl.2020.105939 $\endgroup$
    – seba
    Apr 27, 2021 at 13:53
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.