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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .