Return to Answer

5 added 33 characters in body

The following paper:

Bhattacharyya, P., and B. K. Chakrabarti. The mean distance to the nth neighbour in a uniform distribution of random points: an application of probability theory. Eur J. Phys. 29, pp. 639-645.

Claims to provide exact, approximate, and handwaving estimates for the mean 'k'th nearest neighbor distance in a uniform distribution of points over a D-dimensional Euclidean space (or a D-dimensional hypersphere of unit volume)volume) when one ignores certain boundary conditions.

However, Wadim's response is making me feel some concern that the exact problem is much more complex. Please see the paper for the full derivation (and approximate methods), but I'll write the exact expression they converge on using two different method of absolute probability and conditional probability.

Let $D$ be the dimension of the Euclidean space, let $N$ be the number of points randomly and uniformly distributed over the space, and let $MeanDist(D, N, k)$ be the mean distance to a given points $kth$ nearest-neighbor. This yields:

$MeanDist(D, N, k) = \frac{(\Gamma(\frac{D}{2}+1))^{\frac{1}{D}}}{\pi^{\frac{1}{2}}} \frac{(\Gamma(k + \frac{1}{D}))}{\Gamma(k)} \frac{\Gamma(N)}{\Gamma(N + \frac{1}{D})}$

Where $\Gamma(...)$ is the complete Gamma function.

Wadim - might it be possible for you to provide some feedback about the connection between the derivations here and vs. the method of box integrals you described in your comment?

4 deleted 104 characters in body

The following paper:

Bhattacharyya, P., and B. K. Chakrabarti. The mean distance to the nth neighbour in a uniform distribution of random points: an application of probability theory. Eur J. Phys. 29, pp. 639-645.

Should

Claims to provide exact, approximate, and handwaving estimates for the mean 'k'th nearest neighbor distance in a uniform distribution of points over a D-dimensional Euclidean space (or a D-dimensional hypersphere of unit volume).

However, Wadim's response is making me feel some concern that the problem is more complex. Please see the paper for the full derivation (and approximate methods), but I'll write the exact expression they converge on using two different method of absolute probability and conditional probability.

Let $D$ be the dimension of the Euclidean space, let $N$ be the number of points randomly and uniformly distributed over the space, and let $MeanDist(D, N, k)$ be the mean distance to a given points $kth$ nearest-neighbor. This yields:

$MeanDist(D, N, k) = \frac{(\Gamma(\frac{D}{2}+1))^{\frac{1}{D}}}{\pi^{\frac{1}{2}}} \frac{(\Gamma(k + \frac{1}{D}))}{\Gamma(k)} \frac{\Gamma(N)}{\Gamma(N + \frac{1}{D})}$

Where $\Gamma(...)$ is the complete Gamma function.

Wadim - might it be possible for you to provide some feedback about the connection between the derivations here and the method of box integrals you described in your comment?

Also, is there a nice analytical expression for the variance/standard deviation around this mean value?

3 added 4 characters in body

The following paper:

Bhattacharyya, P., and B. K. Chakrabarti. The mean distance to the nth neighbour in a uniform distribution of random points: an application of probability theory. Eur J. Phys. 29, pp. 639-645.

Should provide exact, approximate, and handwaving estimates for the mean 'k'th nearest neighbor distance in a uniform distribution of points over a D-dimensional Euclidean space (or a D-dimensional hypersphere of unit volume).

However, Wadim's response is making me feel some concern that the problem is more complex. Please see the paper for the full derivation (and approximate methods), but I'll write the exact expression they converge on using two different method of absolute probability and conditional probability.

Let $D$ be the dimension of the Euclidean space, let $N$ be the number of points randomly and uniformly distributed over the space, and let $MeanDist(D, N, k)$ be the mean distance to a given points $kth$ nearest-neighbor. This yields:

$MeanDist(D, N, k) = \frac{(\Gamma(\frac{D}{2}+1))^{\frac{1}{D}}}{\pi^{\frac{1}{2}}} \frac{(\Gamma(k + \frac{1}{D}))}{\Gamma(k)} \frac{\Gamma(N)}{\Gamma(N + \frac{1}{D})}$

Where $\Gamma(...)$ is the complete Gamma function.

Wadim - might it be possible for you to provide some feedback about the connection between the derivations here and the method of box integrals you described in your comment?

Also, is there a nice analytical expression for the variance/standard deviation around this mean value?

2 edited body
1