# Minimum distance distribution between N random points in a cube and the origin

We have $N$ points randomly and uniformly chosen in a cube of side $1$ centered at the origin $O$. This means that the coordinates of the point $P_i$ is a vector of random variables $(X_i,Y_i,Z_i)$ where $X_i$, $Y_i$ and $Z_i$ $\sim U([-0.5,0.5])$, $i=1,\ldots, N.$ Let $D_i$ stand for the euclidean distance between $O$ and the point $P_i$, $D_i = \sqrt(X_i^2+Y_i^2+Z_i^2)$. I would like to calculate the distribution of $D = \min(D_i)$ or perhaps more simply the mean $E(D)$ of $D$.

I faced many problem by computing the convolution of these nasty square uniform variables. The involved integrals become very aggressive after a while.

Any help would greatly appreciated. Thanks

Thomas

-

I'm going to give a somewhat heuristic solution that nevertheless gives the right answers.

$E(D)$ is the distance from the origin to the closest of N points.

Let's replace $N$ with a random variable, namely the Poisson with mean $N$. Then your points form a Poisson process of rate $N$ on the unit cube.

Let's furthermore assume that $N$ is large enough that the closest point to the origin is at distance less than $0.5$ from the origin -- that is, $D < 0.5$ -- so we don't have to worry about the geometry of the cube. If there are a lot of points this is reasonable.

So, at least when $N$ is large, your question has approximately the same answer as: consider a Poisson process of rate $N$ in $R^3$. What's the distribution of the distance from the origin to the point closest to the origin?

But this scales with $N$ - a Poisson process of rate $N$ looks like a Poisson process of rate 1, shrunk by a factor of $N^{1/3}$. So it's enough to solve this problem when $N = 1$. We'll get $P(D < x) = F(x)$ when $N = 1$. For generic values of $N$ we'll get $P(D < x) = F(x N^{1/3})$.

So what's $P(D < x)$ when $N = 1$? It's easier to find $P(D > x)$; this is the probability that no point is within the sphere of radius $x$ centered at the origin. But this sphere has volume ${4 \over 3} \pi x^3$ and therefore this probability is $\exp(-4\pi x^3 /3)$. From this we find that the density of $D$ is $f(x) = 4\pi x^2 \exp(-4\pi x^3/3)$ and the expectation of $D$ is $$\int_0^\infty x f(x) \: dx = {\pi^{2/3} 2^{1/3} \over 3^{7/6} \Gamma(2/3)} = 0.5539602785$$ by using Maple. I conjecture, therefore, that $\lim_{N \to \infty} E(D) N^{1/3}$ is equal to this constant; so $E(D) \approx 0.554 N^{-1/3}$.

To check this I simulated the case N = 1000 -- picking 1000 points in each of 1000 cubes, as follows in R:

cp = function() runif(3,-.5,.5) dist = function(x) sqrt(sum(x^2)) x = rep(0, 10^3); for (i in c(1:10^3)) {m = 1; for (j in c(1:10^3)) { m = min(m,dist(cp())); x[i] = m;}}

The average distance turns out to be 0.05554898, very close to $0.554/10$. For picking 10000 points in each of 1000 cubes I get an average distance of 0.02573758 , very close to $0.554/10^{4/3}$.

-
the computations are not more complicated if one computes exactly what $\mathbb{P}(D>rN^{\frac{1}{3}})$ is, right? –  Alekk Jul 28 '11 at 16:44
They're not more complicated, but you have to keep track of factors of $N^{1/3}$ which is a bit of a nuisance. –  Michael Lugo Jul 29 '11 at 0:37
Impressive! I tried your proposition $E(D) = 0.554N^{-1/3}$ and I get almost exactly the same function as I got with my own simulations. The major error appears for small numbers. As you mentioned, for large $N$, the probability that the closest point lies at a distance $< 0.5$ is high.This is not the case for small $N$. That is why we got a little imprecision. Nevertheless, it is a very nice way of thinking the problem. Thank you very much! P.S. I finally computed the distributiion of $D_i$ but it involves nasty $\arctan$ so I think I will stick with your proposition. Thomas –  Thomas Jul 30 '11 at 17:30
In fact, your result is confirmed by a paper dealing with any dimension "The average distance of the n-th neighbour in a uniform distribution of random points" by P. Bhattacharyya, B. K. Chakrabarti and A. Chakraborti I computed it for $D=3$ and it gives almost exaclty the same result as you. –  Thomas Jul 31 '11 at 15:46