9
$\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.

Thanks!

$\endgroup$
  • 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 Aug 31 '16 at 14:41
  • 3
    $\begingroup$ @whuber I agree -- Acronyms are a terrible hashing scheme. $\endgroup$ – Sycorax Aug 31 '16 at 15:01
  • 14
    $\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 Aug 31 '16 at 15:04
  • 4
    $\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$ – Mark L. Stone Aug 31 '16 at 15:42
  • 3
    $\begingroup$ If we are going to have ELI5 spelled out what about ESL? $\endgroup$ – mdewey Aug 31 '16 at 16:01
15
+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$
  • 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$ – Mark L. Stone Aug 31 '16 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 Aug 31 '16 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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