I am working through Hastie's ESL book, and I am having a tough time with Question 2.3. The question is as follows:

We are considering a nearest neighbor estimate at the origin, and the median distance from the origin to the closest data point is given by this equation. I have no idea where to begin in terms of trying to derive this.

I know that most data points are closer to the boundary of the sample space, than to any other data point (curse of dimensionality), but I am having trouble translating this into the Linear Algebra / Probability sense.

• What does the "ELI5" in the title mean? If you want to derive that equation you will need to start with a probability model for points in the ball: what is that model? (Please don't require your readers to refer to a book or some other site in order to understand your question.)
– whuber
Commented Aug 31, 2016 at 14:41
• @whuber I agree -- Acronyms are a terrible hashing scheme.
– Sycorax
Commented Aug 31, 2016 at 15:01
• You're five years old. All credit to you for wanting to understand ESL, but you'll have to wait until you're six. It's a book for big boys and girls. Commented Aug 31, 2016 at 15:04
• A five year old might start by looking at the one-dimensional case (p = 1). And once that is in hand, take it from there. Commented Aug 31, 2016 at 15:42
• If we are going to have ELI5 spelled out what about ESL? Commented Aug 31, 2016 at 16:01

Let $r$ be distance from the origin, and let $V_0[p]$ be the volume of the unit hypersphere in $p$ dimensions. Then the volume contained in a hypersphere of radius $r$ is

$$V[r]=V_0[p]r^p$$

If we let $P=V[r]/V_0[p]$ denote the fraction of the volume contained within this hypersphere, and define $R=r^p$, then

$$P[R]=R$$

If the data points are uniformly distributed within the unit ball, then for $0\leq R\leq 1$ the above formula is a cumulative distribution function (CDF) for $R$. This is equivalent to a uniform probability density for $R$ over the unit interval, i.e. $p[R]= P'[R] =1$. So, as hinted by Mark Stone in the comments, we can reduce the $p$ dimensional case to an equivalent 1D problem.

Now if we have a single point $R$, then by definition of a CDF we have $\Pr[R\leq \rho]=P[\rho]$ and $\Pr[R\geq \rho]=1-P[\rho]$. If $R_{\min}$ is the smallest value out of $n$ points, and the points are all independent, then the CDF for is given by $$\Pr[R_{\min}\geq \rho]=\Pr[R\geq \rho]^n=(1-\rho)^n$$ (this is a standard result of univariate extreme value theory).

By definition of the median, we have $$\frac{1}{2}=\Pr[(R_{\min})_{\mathrm{med}}\geq R]=(1-R)^n$$ which we can rewrite as $$(1-d^p)^n=\frac{1}{2}$$ which is equivalent to the desired result.

EDIT: Attempt at "ELI5"-style answer, in three parts.

1. For the 1D case with a single point, the distance is uniformly distributed over $[0,1]$, so the median will be $\frac{1}{2}$.

2. In 1D, the distribution for the minimum over $n$ points is the first case to the $n$-th power.

3. In $p$ dimensions, the distance $r$ is not uniformly distributed, but $r^p$ is.

• Ha ha, I gave the comment that a 5 year old might start by looking at the p = 1 case. I thought about adding a comment that a 4 year old might not only start with the p = 1 case, but also n = 1. But I figured I'd let the 5 year old figure that out. Commented Aug 31, 2016 at 20:54
• Note that when I answered the question, it was after it had been clarified by @fcop to read: "Consider N data points uniformly distributed in a p-dimensional unit ball centered at the origin. Show that the median distance from the origin to the closest data point is given by ...". So a unit-ball with respect to the $L_2$ norm in $p$ dimensional space. After this the question was rolled back to the original, which differs and is not so clear. (See comment chain under original question.) Commented Aug 31, 2016 at 22:45