1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Basically the same as the expected distance between two objects placed in a cube of volume $V$, if your definitions are the same as mine (otherwise you'd better state them). Not voting to close yet because in certain regimes it can be made into a rather meaningful question... $\endgroup$ – fedja Sep 19 '16 at 17:50
  • $\begingroup$ Sorry, I meant to ask what's the expected minimum distance between 2 points, not the average between all points which is quite straight forward. $\endgroup$ – RazvanD Sep 19 '16 at 17:53
  • 1
    $\begingroup$ You should also specify the dimension and, since the question is rather intractable if you want an exact answer (meaning you can write a multiple integral and stare at it for a long while, but what use is that?), the precision that would be satisfactory for you. $\endgroup$ – fedja Sep 19 '16 at 17:56
  • $\begingroup$ Well, I'm not given the size of the cube, all I know is that there are 2,25 * 10^26 objects within a volume of 1 m^3 $\endgroup$ – RazvanD Sep 19 '16 at 18:00
  • 1
    $\begingroup$ For the case of a square see mathoverflow.net/questions/124579/…. $\endgroup$ – user111 Sep 20 '16 at 6:09
6
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ See the OP's update mathoverflow.net/questions/250266/… $\endgroup$ – Willie Wong Sep 19 '16 at 17:59
  • 1
    $\begingroup$ @WillieWong - well in that case of course one could write down the expression a la en.wikipedia.org/wiki/… but of course as fedja points out it this makes the problem harder still. Surely for $n$ large one would have to resort to approximations. $\endgroup$ – Steve Huntsman Sep 19 '16 at 18:10
  • 1
    $\begingroup$ I do not disagree. I merely point out the comment on the assumption that as your answer was posted very soon after it was made, you may have not seen the comment. $\endgroup$ – Willie Wong Sep 19 '16 at 19: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.