2
$\begingroup$

Take the unit interval cube in $m$-dimensions.

  1. If you pick two points in then cube $m$-dimensions independently uniformly what is the expected distance between them?

Partition into $k^m$ little cubes of equal size.

  1. If you pick two little cubes independently uniformly what is the expected distance between them?
$\endgroup$
1
  • $\begingroup$ In the second part, do you mean the expected distance of the centres of the little cubes? $\endgroup$
    – Chris
    Nov 5, 2018 at 12:34

1 Answer 1

3
$\begingroup$

In regards to the first part of your question, no closed formula is known for this, though approximations for small values of $m$ are given here.

Given that this question does not have a closed form answer, and that the second question is even less analytically tractable, I think it is fairly clear that the second question also will not have a closed form answer.

A simple argument via Jensen's inequality gives an upper bound; we first note that if $X = (X_1,\ldots, X_m)$ is uniform on $[0,1]^m$ then each of the marginals $X_i \in [0,1]$ are independent and uniform. Then

$$ \begin{aligned} \mathbf E \left[ |X - Y|\right] & = \mathbf E \left[ \left( \sum_{i=1}^m(X_i - Y_i)^2 \right)^{1/2} \right] \\ & \leq \mathbf E \left[ \sum_{i=1}^m(X_i - Y_i)^2 \right]^{1/2} \\ & = \sqrt{m} \mathbf E[(X_1 - Y_1)^2]^{1/2} \\ & = \sqrt{\frac{m}6} \end{aligned} $$ To derive this, we note that in one dimension the difference between two uniform $[0,1]$ distributions $Z = X-Y$ has a triangular distribution:

$$\mathbf P(Z = z) = \begin{cases} z+1 \qquad \text{if $-1 \leq z < 0$}, \\ 1 -z \qquad \text{if $0 \leq z < 1$.} \end{cases} $$ From which you can deduce $\mathbf E[Z] = \frac13$ and $\mathbf E[Z^2] = \frac16$.

In fact, a more complex argument can be used to show that this upper bound is asymptotically tight, i.e. that in the limit the expected distance is $\sqrt{m/6}$. Details of this are given here.

Again, linking to your second question, as your small boxes become smaller the distance will also ssatisfy this asymptotic relationship, though you need to take care in ordering the limits (box size, vs $m$).

$\endgroup$

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.