# Average minimum distance between $n$ points generate i.i.d. with uniform dist.

Let $U$ be distributed uniformly on $[0,a]$. Now suppose we generate $n$ independent points according to $U$.

What is the average minimum distance between these $n$ points? That is \begin{align} E\left[ \min_{i,j\in [1,n]: i\neq j} |U_i-U_j|\right] \end{align}

Is this a correct formulation of average minimum distance between?

Assume $$a=1$$ for simplicity. Let $$M$$ be the minimum distance among these $$n$$ points. Note $$M$$ is always at most $$\frac1{n-1}$$, which occurs when the points are evenly spaced. To calculate $$EM$$, we first calculate $$P(M>m)$$, for $$0\le m \le 1/(n-1)$$.

By symmetry, $$P(M>m)=n!\times P(M>m\text{ and } U_1 And the latter is equal to the volume of the below subset $$S$$ of the unit hypercube $$Q=[0,1]^n$$: $$S = \{(x_1,\dots,x_n)\in Q:x_i+m\le x_{i+1}\text{ for }i=1,\dots,n-1\}$$ Now, consider the transformation $$f:S\to [0,1]^n$$, given by $$(x_1,\dots,x_n)\mapsto (x_1,x_2-m,x_3-2m,\dots,x_n-(n-1)m)$$ A little thought shows that $$f$$ is a volume-preserving bijection from $$S$$ to the region $$S'$$ of the smaller hypercube $$Q'=[0,1-(n-1)m]^n$$ given by $$S'=\{(y_1,\dots,y_n)\in Q':y_i\le y_{i+1}\text{ for }i=1,\dots,n-1\}$$ By symmetry of permuting the $$y_i$$, we have $$\text{Vol}(S')=1/n! \ \times\text{Vol}(Q')$$. But $$\text{Vol}(Q')=(1-(n-1)m)^n$$. Putting this all together, \begin{align} P(M>m)&=n!\cdot \text{Vol}(S)\\ &=n!\cdot \frac1{n!}(1-(n-1)m)^n\\ &=(1-(n-1)m)^n \end{align} and therefore \begin{align} EM &=\int_0^{1/(n-1)}P(M>m)\,dm\\ &=\int_0^{1/(n-1)}(1-(n-1)m)^n\,dm\\ &=\left.\frac{1}{n-1}\frac{(1-(n-1)m)^{n+1}}{n+1}\right|_{0}^{1/(n-1)}\\ &=\boxed{\frac{1}{n^2-1}} \end{align} To get the answer for the interval $$[0,a]$$, simply multiply this result by $$a$$.

• Do you think your proof can be adapted to the case when we put $n$ points uniformly on shall of the two-dimensional ball?
– Boby
Nov 7, 2016 at 16:46
• @Boby Probably not. This question might be related. Nov 7, 2016 at 18:29
• Why is $E[M]=\int_0^{1/(n-1)} P[M>m]dm$ in the first place? I don't see how to obtain this expression from the usual expression of the expected value of a function of random variables. Nov 18, 2016 at 12:10
• @LoveTooNap29 See "continuous distribution taking nonnegative values" in en.m.wikipedia.org/wiki/… Nov 18, 2016 at 15:57
• @MikeEarnest How do you come up with this idea. In which course i can learn proof like this. Apr 27, 2020 at 3:49