8
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$P(M>m)$ is, by symmetry, equal to $n!$ times $P(M>m\text{ and } U_1<U_2<\dots<U_n)$, and the probability of the latter is 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=2,\dots,n-1\} $$ The volume of $S'$ is, by symmetry of permuting the $y_i$, equal to $1/n!$ times the volume of $Q'$, which is just $(1-(n-1)m)^n$. Putting this all together, $$ P(M>m)=n!\cdot \text{Vol}(S)=n!\cdot \frac1{n!}(1-(n-1)m)^n=(1-(n-1)m)^n $$ 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\\ &=\frac{1}{n-1}\frac{(1-(n-1)m)^{n+1}}{n+1}\Big|_{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$.

$\endgroup$
5
  • $\begingroup$ Do you think your proof can be adapted to the case when we put $n$ points uniformly on shall of the two-dimensional ball? $\endgroup$ – Boby Nov 7 '16 at 16:46
  • 1
    $\begingroup$ @Boby Probably not. This question might be related. $\endgroup$ – Mike Earnest Nov 7 '16 at 18:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Nap D. Lover Nov 18 '16 at 12:10
  • 1
    $\begingroup$ @LoveTooNap29 See "continuous distribution taking nonnegative values" in en.m.wikipedia.org/wiki/… $\endgroup$ – Mike Earnest Nov 18 '16 at 15:57
  • $\begingroup$ @MikeEarnest How do you come up with this idea. In which course i can learn proof like this. $\endgroup$ – Huy Nguyen Apr 27 '20 at 3:49

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.