We are given $X,X_1,\ldots,X_N$ independent and identically distributed $k$-dimensional vectors. For a given query point $X_q\in\mathbb{R}^k$ assume without loss of generality that $X_1,\ldots,X_m$ are its $m$ nearest neighbors from the $N$ points. Define $$S_m(X_q):=\{X\mid D(X,X_q)\leq D(X_m,X_q)\}$$ the sphere containing the $m$ nearest neighbors to $X_q$ and let $v_m(X_q)$ be the volume of this region as $$v_m(X_q)=\int_{S_m(X_q)}1\:dX.$$ The probability content of this region, i.e. the probability of $X$ falling into $S_m(X_q)$ is given by $$u_m(X_q)=\int_{S_m(X_q)}p(X)\:dX,$$ where $p(X)$ is the distribution of $X$ and the $X_i$. Now both this and this paper claim that $u_m(X_q)$ follows a beta distribution that is independent of the chosen distance $D(X,Y)$ and the given distribution $p(X)$. However, neither gives of proof of this, is there any easy way to see this?

  • $\begingroup$ Sounds much too good to be true. Is $p(X)$ meant to be the absolutely continuous density function of the distribution of the $X$'s? $\endgroup$ – Anthony Quas Mar 4 '15 at 18:10
  • $\begingroup$ Yes, $p(X)$ is to be the distribution of the random variable $X$. If you say this does not hold, are both papers wrong then, when stating it? $\endgroup$ – Skrodde Mar 4 '15 at 21:42
  • $\begingroup$ Presumably the right hand side of the inequality defining S_m(X_q) should be D(X_q, X_m). $\endgroup$ – Scott Morrison Mar 4 '15 at 22:44
  • $\begingroup$ So if the $(X_k)$ were placed at positions of a discrete distribution, then the volume would take on discrete values, and so could not possibly be beta-distributed. Now if you change the discrete distribution by spreading it out just slightly, you don't really alter the distribution of the volume of the sphere - it's still very close to a discrete distribution. This cannot be close to a beta distribution. $\endgroup$ – Anthony Quas Mar 5 '15 at 3:16
  • $\begingroup$ @scottMorrison Thanks for pointing this out, I just corrected it. $\endgroup$ – Skrodde Mar 5 '15 at 9:01

Fix the query point $X_q$, and take random variable $\xi=D(X,X_q)$ for $X$ being distributed w.r.t. your law, and let $F_{\xi}$ be its distribution function. Then, you are taking a sample of size $N$ of $\xi$, order them by increasing (obtaining $\xi_{(1)}<\dots<\xi_{(N)}$) and you evaluate $F(\xi_{(m)})$.

But for any continuous distribution of $\xi$, the random variable $F(\xi)$ follows a uniform distribution on $[0,1]$. In the same way -- as here the only things you are using are the order and the distribution function, -- the result here does not change if you make an increasing change of variable, passing to $\xi'=g(\xi)$ (as the distribution function then becomes pre-composed with $g^{-1}$). In particular, the result here will be exactly the same as if you take $\xi$ to be uniformly distributed on $[0,1]$ (this corresponds to taking $g=F_{\xi}$).

And then you are asking for the law of $\xi_{(m)}$ for $\xi\sim R([0,1])$, which is exactly the beta distribution.

  • $\begingroup$ Thank you Victor, for your answer. I see how the law of $\xi_{(m)}$ has to be the beta function. What is not yet entirely clear to me is why for a continuous distribution of $\xi$ the random variable $F(\xi)$ has to follow a uniform distribution on $[0,1]$. Could you elaborate on this or provide a source? $\endgroup$ – Skrodde Mar 8 '15 at 9:54
  • 1
    $\begingroup$ Not $\xi_{(m)}$, but $F_{\xi}(\xi_{(m)})$. For the $F_{\xi}(\xi)$: for a monotonous $g$, one has $g(\xi)\le y$ iff $\xi\le g^{-1}(y)$. Hence, the distribution function of $g(\xi)$ is $F_{\xi}\circ g^{-1}$ (with the necessary precautions concerning domains of definition/range). Apply for $g=F_{\xi}$. $\endgroup$ – Victor Kleptsyn Mar 8 '15 at 10:10
  • $\begingroup$ Okay, I think I got a little bit confused with notation. We have a random varibale $\xi=D(X,X_q)$ with distribution $F_\xi$. Then we have a sample, ordered increasingly: $\xi_{(1)}<\ldots<\xi_{(N)}$ and we want to know the distribution of $F_\xi(\xi_{(m)})$. If we know $\xi\sim R([0,1])$, then it follows that the law of $\xi_{(m)}$ is the beta distribution. Is that correct so far? Still, I don't understand why we can say that $\xi\sim R([0,1])$. $\endgroup$ – Skrodde Mar 8 '15 at 11:04
  • 1
    $\begingroup$ 1) Yes, it is correct so far. 2) Surely I do not claim that $\xi\sim R([0,1])$ 3) But I claim that the distribution of $F_\xi(\xi_{(m)})$ is the same as the one of $\eta_{(m)}$, where $\eta=F_{\xi}(\xi)\sim R([0,1])$. Simply because $F_{\xi}$ is a monotonous function. $\endgroup$ – Victor Kleptsyn Mar 8 '15 at 14:49
  • $\begingroup$ Sorry for the late reply, but I lacked the time to look into the stuff. Thanks to your hints, I was now able to figure it out! $\endgroup$ – Skrodde Mar 20 '15 at 12:58

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.