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.

Thanks!

• 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 Aug 31 '16 at 14:41
• @whuber I agree -- Acronyms are a terrible hashing scheme. – Sycorax Aug 31 '16 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. – Nick Cox Aug 31 '16 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. – Mark L. Stone Aug 31 '16 at 15:42
• If we are going to have ELI5 spelled out what about ESL? – mdewey Aug 31 '16 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. – Mark L. Stone Aug 31 '16 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.) – GeoMatt22 Aug 31 '16 at 22:45