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 QuasMar 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$– SkroddeMar 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 betadistributed. 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 QuasMar 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$– SkroddeMar 5, 2015 at 9:01
1 Answer
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 precomposed 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$– SkroddeMar 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$– SkroddeMar 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$– SkroddeMar 20, 2015 at 12:58