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 QuasCommented 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$– SkroddeCommented 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$– Anthony QuasCommented 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$– SkroddeCommented Mar 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 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$– SkroddeCommented 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$ Commented 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$– SkroddeCommented 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$ Commented 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$– SkroddeCommented Mar 20, 2015 at 12:58