3
$\begingroup$

Suppose I draw $n$ points in $\mathbb{R}$ from a distribution $p$. What is the expected least distance between two of the points drawn? I am particularly interested in the uniform distribution $\texttt{Unif}(a,b)$.

I'd be interested in other statistics about this random variable besides just its expectation.

$\endgroup$
  • $\begingroup$ Damn, I just wrote a quite long answer, only to realize that if I click on the first (and very obvious) related post offered by the site: math.stackexchange.com/questions/195245/… and check the comments there, then it immediately navigates me to this post: mathoverflow.net/questions/1294/… I thought the author checked such trivial sources before posting. Anyway, it was not totally in vain, my argument is a bit different. $\endgroup$ – A. Pongrácz Aug 12 '18 at 21:55
  • $\begingroup$ @A.Pongrácz Sorry to have wasted your time. I didn't check overflow, obviously. $\endgroup$ – Eric Auld Aug 12 '18 at 22:17
0
$\begingroup$

With the uniform distribution, this can be discretized nicely, and then it leads to a standard combinatorial problem. For simplicity, I am working on the interval $[0,1]$.

So divide the interval into $N$ equal subintervals ($N$ is large). Then we pick $n$ of these (the points picked are identified by the small intervals they are contained in), and imagine that the distance of points is about the distance of the midpoints of the intervals.

So by rescaling with a multiple $N$, we really have numbers $1, \ldots, N$ representing chairs, pick $n$ of them randomly (we let $n$ people sit down), and the random variable is the distance of the closest two people. Number of cases: about $\binom{N}{n}$ (people are twins; also we may assume that no two people sit in the same chair, as it doesn't make a difference for large $N$). Number of cases when minimal distance is at least $k$ for $1\leq k\leq (N-1)/(n+1)$? To obtain this, make the people stick out their left arm, so that they not only cover their own chair, but also the next $k-1$ to the left. In order for the last chairs to be available, we have to insert $k-1$ extra chairs on the left.

That means that the resulting picture after the people are seated will contain $n$ people with extended arms and $N+k-1-nk$ unoccupied chairs. So the number of possibilities is the number of choosing $n$ objects out of $N+k+n-1-nk$ ones, that is $\binom{N-(n-1)(k-1)}{n}$.

So the expected value is $$\frac{1}{\binom{N}{n}}\sum\limits_{k=1}^{(N-1)/(n+1)} \binom{N-(n-1)(k-1)}{n}= \frac{1}{\binom{N}{n}}\sum\limits_{k=0}^{(N-n-2)/(n+1)} \binom{N-k(n-1)}{n}$$

The estimation $\binom{N-k(n-1)}{n}\approx \frac{1}{n!} (N-nk)^n$ introduces little error in the relevant region. So the sum is about $\frac{n!}{N^n}\frac{1}{n!}\sum\limits_{k=0}^{(N-n-2)/(n+1)} (N-k(n-1))^n = \sum\limits_{k=0}^{(N-n-2)/(n+1)} (1-k\frac{n-1}{N})^n = \frac{N}{n-1}\sum\limits_{k=0}^{(N-n-2)/(n+1)} \frac{n-1}{N}(1-k\frac{n-1}{N})^n$.

This last summation is (close to) an upper Riemann approximation of the integral $\int\limits_{0}^{1} x^n = \frac{1}{n+1}$, so we obtain $\frac{N}{n^2-1}$. After compensation by the rescaling factor $N$ we have that the answer to the original question is $\frac{1}{n^2-1}$.

I will re-check the estimations tomorrow, it is quite late here. Maybe some errors need a bit more care, but I am sure the general argument is fine.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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