Minimum distance between $n$ points in a cube

Question

What is the expected value for the minimum distance between $n$ points placed randomly, assuming a uniform distribution, within a cube of volume $V$?

Answer 1

This question (or at least approximations to the distribution that hold beyond lowest order in the number of points) has practical importance. The "DIEHARD" suite of tests for pseudo-random generators has as one of its tests the generation of many cases of the minimum distance of $N$ points in a 2 or 3 dimensional box, and comparison of the resulting distance distribution, via a K-S test, with the expected distribution. Most correlations between near-time randoms will tend to result in clustering along some curve in $d$-dimensional spaces, and the miminum distance test is quite sensitive to this.

Unfortunately, in the original suite, the distribution of distance squared was taken to be exponential with average distance squared of $$\alpha^2 = \frac{2}{\pi N(N-1)}$$ in 2 dimensions. This is derived by simply considering the volume taken up by the previous $k$ balls of radius $2s$ as diminishing the chance that the $k+1$-st ball will "survive" as being further than some distance $s$ from any neighbor.

The actual distribution differs from this, for two reasons: The volume excluded is not the simple sum of the volumes of $k$ balls because two of those $k$ balls whose centers are between $s$ and $2s$ apart have some overlapping volume which should not be excluded twice. There is also a boundary effect near the surface of the box.

The history is that for a while, the DIEHARD suite had used only the lowest-order exponential distribution. While this was fine for the number of trials that could be run using early computers, by the late 1990's, people were doing more strenuous tests, and documentation for this element of the suite had a statement like "you should not reject the randomness hypotheses unless the $p$-value shown by the K-S test is at least $0.99999$." Of course, that was because you were doing a powerful comparison with the wrong distribution.

The change in distribution introduced by these next-lowest-order effects can be calculated analytically; the geometric integrals dealing with 2-sphere overlaps are tractable. In the end, this change can be compensated for in comparing the distributions quite efficiently. The paper FERMILAB-TM-2120 (May 2002) "Distribution of Minimum Distance Among N Random Points in d Dimensions" presents the results.

http://digital.library.unt.edu/ark:/67531/metadc743246/m2/1/high_res_d/794005.pdf

With this next-order correction, the distributions are accurate enough even for tests using massive supercomputers.

I seriously doubt that a closed-form expression for the distribution exists, even in $2$ dimensions.

Answer 2

First, to set up notation, consider $n$ IID points $x_{(1)}, \dots, x_{(n)}$ distributed uniformly in the unit $m$-cube. The pairwise distances $d_{jk} := \|x_{(j)} - x_{(k)} \|$ are themselves random variables, and $\mathbb{E} \frac{2}{n(n-1)} \sum_{j<k} d_{jk} = \mathbb{E}d_{12}$. This expectation is in turn equal to the box integral $\Delta_m(1)$, for which see Bailey, Borwein and Crandall, "Advances in the theory of box integrals".