Explanation of formula for median closest point to origin of N samples from unit ball

Question

In Elements of Statistical Learning, a problem is introduced to highlight issues with k-nn in high dimensional spaces. There are $N$ data points that are uniformly distributed in a $p$-dimensional unit ball.

The median distance from the origin to the closest data point is given by the expression:

$$d(p,N) = \left(1-\left(\frac{1}{2}\right)^\frac{1}{N}\right)^\frac{1}{p}$$

When $N=1$, the formula breaks down to half the radius of the ball, and I can see how the closest point approaches the border as $p \rightarrow \infty$, thus making the intuition behind knn break down in high dimensions. But I can't grasp why the formula has a dependence on N. Could someone please clarify?

Also the book addresses this issue further by stating: "...prediction is much more difficult near the edges of the training sample. One must extrapolate from neighboring sample points rather than interpolate between them". This seems like a profound statement, but I can't seem to grasp what it means. Could anyone reword?

Answer 1

The volume of an $p$-dimensional hyperball of radius $r$ has a volume proportional to $r^p$.

So the proportion of the volume more than a distance $kr$ from the origin is $\frac{r^p-(kr)^p}{r^p}=1-k^p$.

The probability that all $N$ randomly chosen points are more than a distance $kr$ from the origin is $\left(1-k^p\right)^N$. To get the median distance to the nearest random point, set this probability equal to $\frac12$. So $$\left(1-k^p\right)^N=\tfrac12 $$ $$\implies k=\left(1-\tfrac1{2^{1/N}}\right)^{1/p}.$$

Intuitively this makes some sort of sense: the more random points there are, the closer you expect the nearest one to the origin to be, so you should expect $k$ to be a decreasing function of $N$. Here $2^{1/N}$ is a decreasing function of $N$, so $\tfrac1{2^{1/N}}$ is an increasing function of $N$, and thus $1-\tfrac1{2^{1/N}}$ is a decreasing function of $N$ as is its $p$th root.

Answer 2

And now without hand waving

1. For any sequence of i.i.d rv's, $$P( \min_{1\le i\le N} Y_i > y ) = (1-F(y))^N,$$ where $F$ is the common CDF

2. Thus if we have $N$ i.i.d uniformly distributed $X_i$ in the unit ball in $p$ dimensions, then $$P( \min_{1\le i\le N} ||X_i|| > r ) = (1-F(r))^N,$$ where $F$ is the common CDF of the distances, $||X_i||, i=1,2,\ldots,N$. Finally, what is the CDF, $F$, for a uniformly distributed point in the unit ball in $R^p$? The probability that the point lies in the ball of radius r within the ball of unit radius equal the ratio of volumes:

$$F(r) = P ( ||X_i|| \le r ) = C r^p/( C 1^p) = r^p$$

Thus the solution to

$$1/2 = P( \min_{1\le i\le N} ||X_i|| > r ) = (1- r^p)^N$$

is

$$r = (1 - (1/2)^{1/N})^{1/p}.$$

Also your question about dependence on the sample size, $N$. For $p$ fixed, as the ball fills up with more points, naturally the minimum distance to the origin should become smaller.

Finally, there is something amiss in your ratio of volumes. It looks like $k$ should be the volume of the unit ball in $R^p$.

Answer 3

As concise but in words:

We want to find the median distance of the closest point to the origin in $N$ uniformly distributed points in the ball at the origin of unit radius in $p$ dimensions. The probability that the smallest distance exceeds $r$, (call this quantity expression [1]) is the $N^{th}$ power of the probability that a single uniformly distributed point exceeds $r$, because of statistical independence. The latter is one minus the probability that a single uniformly distributed point is less than $r$. The latter is the ratio of volumes of the ball of radius $r$ to the ball of unit radius, or $r^p$. We can now write expression [1] as

$$ P( \min_{1\le i\le N} ||X_i|| > r ) = (1- r^p)^N.$$

To find the median of the distribution of the minimum of the distances, set the above probability to $1/2$ and solve for $r$, obtaining the answer.