Explanation of formula for median closest point to origin of N samples from unit ball 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?
 A: And now without hand waving


*

*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

*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$.
A: 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.
A: 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.
