Ex. 2.3

Ex. 2.3

Derive equation (2.24).

Soln. 2.3

Let \(\nu_p\cdot r^p\) be the volume of the sphere of radius \(r\) in \(p\) dimension. Consider the unit ball and a point \(a\) uniformly sampled from it. The probability that \(a\) falls outside of the superball \(b\) which centers at origin and has radius \(0<r<1\) is

\[\begin{equation} \frac{\nu_p\cdot 1^p-\nu_p\cdot r^p}{\nu_p\cdot 1^p} = 1-r^p.\nonumber \end{equation}\]

Now for \(N\) independently and uniformly distributed data points, the probability of the point that is the closest to the origin falls outside of the superball \(b\) is

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

To find the median of the radius of the closest point of origin, we set the probability above equal to \(\frac{1}{2}\):

\[\begin{equation} (1-d(p,N)^p)^N = \frac{1}{2}.\nonumber \end{equation}\]

Solving for \(d(p,N)\) we get

\[\begin{equation} d(p, N) = \left(1-\frac{1}{2}^{1/N}\right)^{1/p}.\nonumber \end{equation}\]