0

I'm attempting to use the nearest neighbour distribution to understand the separation between uniformly distributed points in a high-dimensional space. I find that there is discrepancy between empirical results and the analytic distribution and density functions when I look at high-dimension.

  • How do I modify the analytic derivation to accurately reflect the empirical observations shown below?
  • Am I violating some assumption in the empirical setup?

Nearest neighbour distribution derivation

  • Consider a homogeneous point point process with constant rate $\lambda$, then the Lebesgue measure of a point falling in a spherical shell $(r,r + \mathrm{d}r)$ is,

\begin{align} \mu(r) = \lambda S(r)\mathrm{d}r \end{align} where $S(r) = V'(r)$ is the surface area of the hyper-sphere of radius $r$.

The probability of a nearest neighbour (NN) falling in $(r, r+\mathrm{d}r)$ is the probability of a point falling in $(r, r+\mathrm{d}r)$ and no points falling in $(0, r)$,

\begin{align} P(NN \in (r, r+\mathrm{d}r)) \mathrm{d}r = (\lambda S(r)\mathrm{d}r) \left(1 - \int_0^r P(NN \in (r, r+\mathrm{d}r)) \mathrm{d}r \right) \end{align}

The second factor is the probability of no points falling in $(0, r)$, and is one minus the probability of a point falling in $(0, r)$. Differentiate both sides, and then it becomes simple to arrive at,

\begin{align} \log P(NN \in (r, r+\mathrm{d}r)) = -\lambda V(r) + \log S(r). \end{align}

From this we can solve, and arrive at, \begin{align} P(NN \in (r, r+\mathrm{d}r)) = \lambda S(r) e^{-\lambda V(r)} \end{align} and the cummulative distribution function, \begin{align} P(NN \in (0, r)) = 1 - e^{-\lambda V(r)}. \end{align}

This cumulative distribution function is the nearest neighbour distribution function.

Comparing to empirical results

One of the most powerful tools in statistics is that we can often cheaply simulate the results and see if our analytic results are correct.

  • I simulate $N$ points in $\mathcal{U}[0,1]^n$, so that $\lambda = N$.
  • Then I compute the nearest neighbours and plot the histogram.
  • For low dimensions I find a good agreement.
  • For high dimensions I find a large discrepancy.

agreement on low dimension

enter image description hereenter image description here

discrepancy on high dimension

enter image description hereenter image description here

KCd
  • 46,062
Josh Albert
  • 191
  • 2
    I am no expert on this topic, but my main concern would be related to the curse of dimensionality. For high dimensions, it can be shown that most of the volume lies within a narrow shell at the boundary. From this, I would expect the NN distribution to underestimate the distance needed. For this reason, there may be a better way to simulate the process. I don't believe the analytical NN distribution is incorrect. – Gregory Mar 15 '21 at 01:39
  • I also don't think NN distribution is incorrect. How might one either modify the assumptions of the NN distribution derivation, or modify the simulation process to account for the discrepancy? – Josh Albert Mar 15 '21 at 20:30
  • This may help, but I am not sure... https://en.wikipedia.org/wiki/Latin_hypercube_sampling – Gregory Mar 16 '21 at 00:02
  • So it seems the answer to my first question is that I need to simulate with toroidal boundary conditions. This is because the derivation assumes a point process over an infinite extent volume, i.e. a ball placed around any point in the process never intersects with the boundary. The integral term in the derivation would need to be modified to account for a boundary, which is non-trivial to do. – Josh Albert Mar 16 '21 at 13:40

0 Answers0