Let be a sequence of iid random vectors taking values on on the same probability space .

For any , denote by the -th nearest neighboor of among the set , that is we have the properties

• .
• .

The following proposition proves the consistency property of the kNN (kth nearest neighboor).

Note that since is non-increasing, means that for any , the open ball contains at least points among . Conversely, if does not hold, it means that for some , the ball contains at most points among . This in turn implies that for any sufficiently large . Hence, From this inclusion property, in order to show that -a.s., and hence , we only need to show that for any . Using that the are iid, where . To complete the proof, we only need to show that , -a.s. Equivalently, since we already have , we only need to show that Choose a -net countable covering of , that is where .

Note that on , Hence, This implies that

which proves \eqref{eq:h} and the proof of the Proposition is completed.