11
$\begingroup$

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

enter image description here

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.

$\endgroup$
29
  • 4
    $\begingroup$ 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.) $\endgroup$
    – whuber
    Commented Aug 31, 2016 at 14:41
  • 3
    $\begingroup$ @whuber I agree -- Acronyms are a terrible hashing scheme. $\endgroup$
    – Sycorax
    Commented Aug 31, 2016 at 15:01
  • 16
    $\begingroup$ 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. $\endgroup$
    – Nick Cox
    Commented Aug 31, 2016 at 15:04
  • 6
    $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2016 at 15:42
  • 3
    $\begingroup$ If we are going to have ELI5 spelled out what about ESL? $\endgroup$
    – mdewey
    Commented Aug 31, 2016 at 16:01

1 Answer 1

18
+50
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2016 at 20:54
  • 1
    $\begingroup$ 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.) $\endgroup$
    – GeoMatt22
    Commented Aug 31, 2016 at 22:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.