[Math] Minimum distance distribution between N random points in a cube and the origin

ag.algebraic-geometrypr.probability

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

Best Answer

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

Related Question