Ex. 13.2

Derive formula (13.7) for the median radius of the 1-nearest-neighborhood.

Soln. 13.2

This exercise is similar to Ex. 2.3.

Recall \(\nu_p r^p\) is the volume of the sphere of radius \(r\) in \(p\) dimension. Consider the unit cube \([-\frac{1}{2}, \frac{1}{2}]^p\), and a point \(a\) uniformly distributed in it. The probability that \(a\) falls outside of the superball \(b\) which centers at origin and has radius \(0<r<1\) is

\[\begin{equation} 1-\text{volume}(b) = 1- \nu_pr^p.\non \end{equation}\]

Now for \(N\) independently and uniformly distributed data points, the probability of the 1-nearest-neighborhood of origin (i.e., the point that is the closest to the origin) falls outside of the superball is

\[\begin{equation} (1- \nu_pr^p)^N.\non \end{equation}\]

To find the median of \(R\) (the radius of a 1-nearest-neighborhood of origin), we set above equal to \(\frac{1}{2}\):

\[\begin{equation} (1-\nu_pR^p)^N = \frac{1}{2}.\non \end{equation}\]

Solving for \(R\) we get

\[\begin{equation} R = \nu_p^{-1/p}\left(1-\frac{1}{2}^{1/N}\right)^{1/p}.\non \end{equation}\]