30
$\begingroup$

Let $P$ be a set of $n$ random points uniformly distributed inside a unit-radius sphere centered on the origin. Orthogonally project $P$ to a random plane through the origin; call the projected points $P_{\bot}$. Let $A$ be the distance matrix for $P$, and $B$ the distance matrix for $P_{\bot}$, where an $n \times n$ distance matrix records the Euclidean distance between pairs of points. So these matrices are symmetric across a diagonal of zeros.

Finally, define the distance between matrices $A$ and $B$ as $$ d(A, B) = \frac{\sqrt{\sum_{i=1}^n \sum_{j=1}^n (a_{ij} - b_{ij})^2}}{n} \;. $$ (This matrix distance likely has a name, but I don't know it.)

Simulations suggest that $d(A,B)$ is close to $\frac{1}{3}$, independent of $n$. For example, for $n{=}200$, $50$ random trials led to $0.332$.

Q1. Is it true $d(A,B) = \frac{1}{3}$ exactly?

Q2. If so, is there some intuitive way to see this without calculation?


          SphereProj200
          $n=200$ points $P$ (blue) in $\mathbb{R}^3$ projected to $P_{\bot}$ (red).
Update 1. Following @Henry.L's suggestion in the comments, for a sphere of radius $r{=}2$, I find $d(A,B) \approx \frac{2}{3}$. This suggests the matrix distance might be $\frac{r}{3}$.

Update 2. A histogram of $d(A,B)$ for $n{=}100$, $5000$ random trials:


Histogram


$\endgroup$
  • 2
    $\begingroup$ What happens in other dimensions? $\endgroup$ – Noam D. Elkies Apr 9 '17 at 14:32
  • 3
    $\begingroup$ @NoamD.Elkies: That is the natural next question. $\endgroup$ – Joseph O'Rourke Apr 9 '17 at 14:34
  • 2
    $\begingroup$ @JosephO'Rourke I will suggest that you try simulation with different radii to make sure 1/3 always hold before you try higher dimension. You are right, the hyperbolic integration is almost not possible to calculate(by hand). $\endgroup$ – Henry.L Apr 9 '17 at 15:34
  • 3
    $\begingroup$ I think you want to normalise by dividing by $\sqrt{n(n-1)}$, not $n$: the former gives you the square-root of the expected squared distance reduction for two randomly-chosen points (which is clearly independent of $n$). This may explain why you arrived at 0.332 rather than 0.333. $\endgroup$ – Adam P. Goucher Apr 9 '17 at 16:33
  • 2
    $\begingroup$ @JosephO'Rourke Set $n = 5$ instead of $200$, maybe? $\endgroup$ – Adam P. Goucher Apr 9 '17 at 18:42
23
$\begingroup$

No. In the large $n$ limit, this is equivalent to asking whether the expected value of $(a_{ij}-b_{ij})^2$ is $(1/3)^2$, but in fact the expected value is $2-\frac{3\pi}{5} \approx .115$.

We can compute the expectation as follows: $a_{ij}^2 = r_i^2 + r_j^2 + 2 r_i r_j \cos \theta_{ij}$, where $\theta_{ij}$ is the angle between the vectors from the origin to points $i$ and $j$. The variable $\theta_{ij}$ is independent of $r_i,r_j$ and $\cos \theta_{ij}$ has expected value zero. So $$E[a_{ij}^2]=2E[r_i^2]=2\frac{\int_0^1 r^2 \cdot r^2\,dr}{\int_0^1 r^2 \,dr} = \frac{6}{5}$$ We have $b_{ij}=a_{ij} \sin \phi_{ij}$, where $\phi_{ij}$ is the angle between the vector from $i$ to $j$ and the vertical. Furthermore, $\phi_{ij}$ is independent of $a_{ij}$. So $E[(a_{ij}-b_{ij})^2]=E[a_{ij}^2] E[(1-\sin \phi_{ij})^2]$. We can compute $$ E[(1-\sin \phi_{ij})^2]=\frac{\int_0^{\pi} (1-\sin \phi)^2 \sin \phi\, d\phi}{\int_0^{\pi} \sin \phi\, d\phi}=\frac{5}{3}-\frac{\pi}{2}$$ Putting these together gives $E[(a_{ij}-b_{ij})^2]=2-\frac{3\pi}{5}$.

$\endgroup$
  • 4
    $\begingroup$ And note: $\sqrt{2-\frac{3 \pi }{5}} \approx 0.339$. $\endgroup$ – Joseph O'Rourke Apr 9 '17 at 19:12
  • 1
    $\begingroup$ @ChristianRemling For large $n$, I would expect that $d(A,B)$ is usually very close to its expectation value. Since $(a_{ij}-b_{ij})^2$ and $(a_{kl}-b_{kl})^2$ are independent if $i,j,k,l$ are all different, the variance of $d(A,B)^2$ is $O(n^{-1})$. $\endgroup$ – dgulotta Apr 9 '17 at 19:33
  • 2
    $\begingroup$ The OP did not say in what sense $d=1/3$, so I assumed that the question was about whether the probability distribution for $d$ converges to the Dirac delta distribution at $1/3$ as $n \to \infty$. I will edit my answer to clarify. $\endgroup$ – dgulotta Apr 10 '17 at 0:12

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.