32
$\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$
12
  • 2
    $\begingroup$ What happens in other dimensions? $\endgroup$ Apr 9, 2017 at 14:32
  • 3
    $\begingroup$ @NoamD.Elkies: That is the natural next question. $\endgroup$ Apr 9, 2017 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, 2017 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$ Apr 9, 2017 at 16:33
  • 2
    $\begingroup$ @JosephO'Rourke Set $n = 5$ instead of $200$, maybe? $\endgroup$ Apr 9, 2017 at 18:42

1 Answer 1

24
$\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$
3
  • 4
    $\begingroup$ And note: $\sqrt{2-\frac{3 \pi }{5}} \approx 0.339$. $\endgroup$ Apr 9, 2017 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, 2017 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, 2017 at 0:12

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.