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$ Mar 4, 2015 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, 2015 at 21:42
  • $\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$ Mar 5, 2015 at 3:16
  • $\begingroup$ @AnthonyQuas I see how your argument shows that $v_m(X_q)$ does not follow a beta distribution, but I don't see how it applies to $u_m(X_q)$. $\endgroup$
    – Skrodde
    Mar 5, 2015 at 9:01

1 Answer 1


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, 2015 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$ Mar 8, 2015 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, 2015 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$ Mar 8, 2015 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, 2015 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.