8
$\begingroup$

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

$\endgroup$

1 Answer 1

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ the computations are not more complicated if one computes exactly what $\mathbb{P}(D>rN^{\frac{1}{3}})$ is, right? $\endgroup$
    – Alekk
    Jul 28, 2011 at 16:44
  • $\begingroup$ They're not more complicated, but you have to keep track of factors of $N^{1/3}$ which is a bit of a nuisance. $\endgroup$ Jul 29, 2011 at 0:37
  • $\begingroup$ 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 $\endgroup$
    – Thomas
    Jul 30, 2011 at 17:30
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Jul 31, 2011 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.