22
$\begingroup$

I've figured out the pattern for calculating the average distance from the centre of an n-cube; but I don't have a formula for the answer. Is there an easy way to figure this out?

Average distance of points from the centre of a unit 0-cube (point)

$$A_0 = 0$$

Average distance of points from the centre of a unit 1-cube (line)

$$A_1 = \int_{x=-\frac{1}{2}}^{x=\frac{1}{2}}{x}\; dx = 0.250000$$

Average distance of points from the centre of a unit 2-cube (square)

$$A_2 = \int_{x=-\frac{1}{2}}^{x=\frac{1}{2}}{\int_{y=-\frac{1}{2}}^{y=\frac{1}{2}}\sqrt{x^2+y^2}}\;dy \; dx \approx 0.382598$$

Average distance of points from the centre of a unit 3-cube (cube)

$$A_3 = \int_{x=-\frac{1}{2}}^{x=\frac{1}{2}}{\int_{y=-\frac{1}{2}}^{y=\frac{1}{2}}\int_{z=-\frac{1}{2}}^{z=\frac{1}{2}}{\sqrt{x^2+y^2+z^2}}}\;dz\;dy \; dx \approx 0.480296$$

Average distance of points from the centre of a unit 4-cube (tesseract)

$$A_4 \approx 0.560950$$

My gut instinct is that $A_n \rightarrow \infty$ as $n \rightarrow \infty$ as in my head higher dimensional cubes become more spiky and I expect the mass to become concentrated in the corners. I feel justified in saying this because the number of "corners" is $2^n$ with a potential distance of $\frac{\sqrt{n}}{2}$ If somehow it were to approach some limit, that would be cool (to me at least)

Thanks in advance for any help, advice or answers

$\endgroup$
  • $\begingroup$ But how can the average distance of points from centre of a "unit" n-cube be $\infty$? It doesn't seem intuitive $\endgroup$ – ab123 Sep 26 '17 at 15:07
  • 3
    $\begingroup$ @ab123: The distance to the corner $(1,1,\dots,1)$ is $\sqrt{n}$. $\endgroup$ – Hans Lundmark Sep 26 '17 at 15:11
  • 1
    $\begingroup$ We can try to bound it below by the sphere of radius $1/2$ and above by the sphere of radius $1$. The calculations are somewhat simpler in hyperspherical coordinates. You will have that $A_n$ is given by $$ \int_{\phi_{n-1}=0}^{2\pi} \int_{\phi_{n-2}=0}^{\pi} \dots \int_{\phi_1=0}^{\pi} \int_{R=0}^r r^n\,(\sin \phi_1)^{n-2}(\sin \phi_2)^{n-3}\dots\,(\sin \phi_{n-2}) \,dr\,d\phi_{1}\,d\phi_{2}\dots d\phi_{n-1}$$ Is this perhaps more tractible? $\endgroup$ – Fimpellizieri Sep 26 '17 at 15:23
  • 1
    $\begingroup$ @BenCrossley-hobbyist: Along those lines, consider this stunning thought: In a nine-dimensional hypercube, there is room for a single hypersphere of unit diameter in the center, and $2^9 = 512$ hyperspheres of equal size in each corner. $\endgroup$ – Brian Tung Sep 26 '17 at 21:24
  • 1
    $\begingroup$ For the record, these are called box integrals and have been studied as far back as 1976. There are bounds $$\sqrt{\frac{n}{16}}\leq A_n\leq \sqrt{\frac{n}{12}},$$ and more generally an asymptotic series $$A_n \sim \sqrt{\frac{n}{12}} \,\left(1-\frac{n}{10}+ O\left(n^2\right)\right).$$ For more info into these integrals, see for instance this link. These results expand on the previous link's. $\endgroup$ – Fimpellizieri Dec 4 '17 at 21:10
10
$\begingroup$

Consider that the space is a hypercube, so each coordinate is independently distributed. The square of that coordinate's difference from $\frac12$ has the pdf

$$ f(x) = \begin{cases} \frac{1}{\sqrt{x}} & 0 \leq x \leq \frac14 \\ 0 & \text{elsewhere} \end{cases} $$

This distribution has a mean of $\frac{1}{12}$ and a variance of $\frac{1}{180}$. As $n$ increases without bound, the squared distance of the point from the hypercube's center is the sum of $n$ independent and identically distributed (i.i.d.) variables with that same distribution, and is thus asymptotically normally distributed (by the central limit theorem) with mean $\frac{n}{12}$ and variance $\frac{n}{180}$. For instance, for $n = 180$, we would have a mean squared distance of $15$ and a variance of $1$. That variance is small enough already that you could just take the square root of the mean squared distance and probably get a very good approximation of the mean distance.

By that logic, the mean distance would be asymptotically $\sqrt{\frac{n}{12}}$, approached from below, since the square root of a nearly normal distribution with a positive mean would be skewed that way.

For $n = 1, 2, 3, 4$, this expression yields approximate mean distances of $0.289, 0.408, 0.500, 0.577$, which compares reasonably well with the more accurate values given in the OP ($0.250, 0.383, 0.480, 0.561$). These latter values appear to be approaching the asymptotic expression from below, as expected, but are already not too far off.

ETA ($2019$-$02$-$13$): A second-order analysis yields $\sqrt{\frac{5n-1}{60}}$, for which the values for $n = 1, 2, 3, 4$ are $0.258, 0.387, 0.483, 0.562$, respectively, showing even closer agreement.

$\endgroup$
  • $\begingroup$ Very nice, Brian. For anyone with Mathematica and a superior machine to mine: a[n_] := a[n] = NIntegrate[Sqrt@Sum[x[i]^2, {i, n}], Table[x[i], {i, n}]~Element~Cuboid@Table[-1/2, {i, n}]] then Table[{n, a[n], Sqrt[n/12] // N, Sqrt[n/12] - a[n], Sqrt[n/12]/a[n] - 1}, {n, 9}] // TableForm produces a table with {n, computed, asymptotic, abs. error, rel. error}. See here for results up to n = 9: $\endgroup$ – lastresort Sep 27 '17 at 17:11
  • $\begingroup$ I have added a comment to the opening question. It contains links to information about the subject, including an asymptotic expansion which validates your answer. Good job. $\endgroup$ – Fimpellizieri Dec 4 '17 at 21:27
5
$\begingroup$

This does not solve the question. This answer contains the details of an attempt that ultimately failed, but can perhaps still be of some help.

We can try to bound it below by the sphere of radius $1/2$ and above by the sphere of radius $\sqrt{n}/2$. The calculations are somewhat simpler in hyperspherical coordinates.

You will have that the bounds $B_n(R)$ are given by

$$ \int_{\phi_{n-1}=0}^{2\pi} \int_{\phi_{n-2}=0}^{\pi} \dots \int_{\phi_1=0}^{\pi} \int_{r=0}^R r^n\,(\sin \phi_1)^{n-2}(\sin \phi_2)^{n-3}\dots\,(\sin \phi_{n-2}) \,dr\,d\phi_{1}\,d\phi_{2}\dots d\phi_{n-1}$$

This is really just a product of integrals. Notice that $\rho(n,r)=\int_{r=0}^R\, r^n\, dr=\frac1{n+1}R^{n+1}$ and let

$$I(n)=\int_{\phi=0}^\pi\,(\sin\phi)^n\,d\phi$$

Then

$$B_n(R)=\frac{2\pi R^{n+1}}{n+1}\cdot \prod_{k=1}^{n-2}I(k)$$

Now, via integration by parts, one can find the following recurrence relation between the $I(k)$, which holds for $k\geq 2$:

$$I(k)=\frac{k-1}{k}\cdot I(k-2)$$

Humm, looks interesting. How do some products $P(n)=\prod_{k=1}^{n-2}I(k)$ end up, in light of this? We have:

\begin{align} P(3)&=I(1)\\ \\ P(4) &=I(1)\cdot I(2)\\ &=\frac12 \cdot I(0)\cdot I(1)\\ \\ P(5) &=\frac12 \cdot I(0)\cdot I(1) \cdot I(3)\\ &=\left[\frac12 \cdot \frac23\right]\cdot I(0)\cdot I(1)^2\\ \\ P(6) &=\left[\frac12 \cdot \frac23\right]\cdot I(0)\cdot I(1)^2 \cdot I(4)\\ &=\left[\frac12 \cdot \frac23\cdot \frac34\right]\cdot I(0)\cdot I(1)^2 \cdot I(2)\\ &=\left[\left(\frac12\right)^2 \cdot \frac23\cdot \frac34\right]\cdot I(0)^2\cdot I(1)^2\\ \\ P(7) &=\left[\left(\frac12\right)^2 \cdot \frac23\cdot \frac34\right]\cdot I(0)^2\cdot I(1)^2 \cdot I(5)\\ &=\left[\left(\frac12\right)^2 \cdot \left(\frac23\right)^2\cdot \frac34\cdot\frac45\right]\cdot I(0)^2\cdot I(1)^3\\ \\ P(8) &=\left[\left(\frac12\right)^2 \cdot \left(\frac23\right)^2\cdot \frac34\cdot\frac45\right]\cdot I(0)^2\cdot I(1)^3 \cdot I(6)\\ &=\left[\left(\frac12\right)^3 \cdot \left(\frac23\right)^2\cdot \left(\frac34\right)^2\cdot\frac45\cdot\frac56\right]\cdot I(0)^3\cdot I(1)^3\\ \end{align}

I hope the pattern shows how induction goes. Noting that $I(0)=\pi$ and $I(1)=2$ we have

$$P(n)=c_n\cdot \pi^{\lfloor\frac{n}2\rfloor-1}\cdot 2^{\lfloor\frac{n-1}2\rfloor}$$

where $c_n$ is the constant given by the product of fractions. The product is reminiscent of a telescoping product, and will feature all fractions of the form $\frac{k}{k+1}$ from $\frac12$ to $\frac{n-3}{n-2}$. The last two fractions will be raised to the power $1$, the preceding two fractions by the power $2$, and so on and so forth. With cancellations, we can recognize that

$$c_n=\frac1{(n-2)!!}$$

where $k!!$ denotes the double factorial of $k$.

Putting it all together we get:

$$B_n(R)=\frac{2^{\lfloor\frac{n+1}2\rfloor}\cdot\pi^{\lfloor\frac{n}2\rfloor}\cdot R^{n+1}}{(n+1)\cdot(n-2)!!} $$

And then $B_n(1/2)\leq A_n\leq B_n(\sqrt{n}/2)$. Would be interesting to get some asymptotic estimates here. It does not look immediately clear to me, and I'm not sure this solve the problem.


It appears one may express the double odd factorial in terms of the gamma function via

$$(2k-1)!!=\frac{2^k\cdot\Gamma\left(k+\frac12\right)}{\sqrt{\pi}}$$

Hence, for odd $n=2k+1$ we have

$$(n-2)!!=\frac{2^{\frac{n-1}2}\cdot\Gamma\left(\frac{n}2\right)}{\sqrt{\pi}}$$

It follows that

\begin{align} B_{2k+1}(R) &=\frac{2\cdot\pi^{\left(k+\frac12\right)}\cdot R^{2k+2}}{(2k+2)}\\ &=\frac{2\cdot{\left(\sqrt{\pi}\right)}^{2k+1}\cdot R^{2k+2}}{(2k+2)}\\ &=\frac{1}{(k+1)\,\sqrt{\pi}}\cdot{\left(R\,\sqrt{\pi}\right)}^{2k+2}\\ &=\frac{1}{(k+1)\,\sqrt{\pi}}\cdot{\left(R^2\,\pi\right)}^{k+1} \end{align}

It's clear that as $k\to \infty$, $B_{2k+1}(R)\to 0$ if $R^2\,\pi\leq1$ and $\to\infty$ if $R^2\,\pi>1$. In particular, for $R=1/2$ the limit of the lower bound is $0$, so it does not solve our problem.

$\endgroup$
  • $\begingroup$ A*** for effort! $\endgroup$ – Ben Crossley Sep 26 '17 at 18:04
  • $\begingroup$ Any chance you could edit your answer so that at the top you note that your working was inconclusive? I'm concerned people are noticing the amount of effort and assuming it has been solved. Also, a thought, would the lower bound not be 1/4, rather than 1/2? $\endgroup$ – Ben Crossley Sep 27 '17 at 16:30
  • $\begingroup$ Okay, will do it. If we're talking about a unit hypercube, then the largest hypersphere that fits inside it is has radius $1/2$, right? $\endgroup$ – Fimpellizieri Sep 27 '17 at 16:38
  • $\begingroup$ Yeah, Max r = 1/2, but then there is more mass inside of that than outside (in 1D and 2D for certain, maybe higher) surely the trivial lower bound is 1/4 because then there is guarenteed to be more mass on the outside $\endgroup$ – Ben Crossley Sep 27 '17 at 16:45
  • 1
    $\begingroup$ The lower bound is not $1/2$, $1/2$ is the radius for the largest sphere that fits inside the cube. This sphere provides a lower bound, which in the notation of my post would be $B_n(1/2)$. $B_n(R)$ is the integral over the $n$-sphere of radius $R$ of the distance to the sphere's center. $\endgroup$ – Fimpellizieri Sep 27 '17 at 21:12
0
$\begingroup$

Clearly the limit is infinite as half the volume of the cube lies in the region where the absolute value of the coordinates sum to something greater than n/4.

Ok let's elaborate: It is enough to consider the positive orthant. Here the map from (x_1,...,x_n) to (1/2-x_1,...,1/2-x_n) shows that exactly half the points by volume have x_1+...+x_n>n/4. The point closest to the origin with this property is (1/4,...,1/4) it is at a distance of sqrt(n)/4 from the origin...

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate at all? I don't follow. $\endgroup$ – Ben Crossley Sep 26 '17 at 18:24

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.