Law of large numbers for nearest neighbors (proof feedback) Let $X$ be a random variable taking values in $\mathbb R^d$ and $S_n$ an iid sample of size $n$ distributed according to $X$. Let $X_{(i)}(x)$ be the $i$th nearest neighbor to $x$ in the set $S_n$ (in $\ell_2$ norm). Show that $X_{(i)}(X)$ converges to $X$ in probability for $i \leq k$ where $k$ is such that $k/n \rightarrow 0$ as $n\rightarrow \infty$.
What I've tried
Here's my attempt for $k=1$:
$$\mathbb P \left ( \left \|X_{(1)}(X) -X\right \| < \epsilon \right ) = \mathbb P \left ( \min_i \left \|X_i -X\right \| < \epsilon \right )$$
Since the $X_i \in S_n$ have the same support as $X$, there is an $N_\delta$ large enough such that for all $n \geq N$, $S_n$ contains an element within $\epsilon$ of $X$ with probability at least $1- \delta$.
For the general case we can extend the argument to requiring $N_\delta$ to be large enough such that at least $k$ elements are within $\epsilon$ of $X$.
I could use some feedback on my reasoning.
Perhaps it's also possible to show this by contradiction. If the elements of $\{X_{(i)}(X)\}^k$ don't converge to $X$ in probability, then they remain bounded away from $X$ in probability for all $n$.
 A: Below, we assume:
a) $i=i(n)\in {\mathbb N}$ satisfies $i(n)/n \to 0$;
b) Conditional on $X$, the RVs $X_1,X_2,\dots$ are IID with the same support as $X$ (note: they do not need to have the same distribution as $X$). This automatically holds if $X,X_1,X_2,\dots$ are IID.
Fix $\epsilon>0$.
If $|X_{(i)}(X) - X| > \epsilon$, then the number of the samples among the first $n$ which are farther then $\epsilon$ from $X$ is at least $n-i+1$. The latter event is contained in the event $S^{X,\epsilon} _n > n-i+1$, where for $z \in {\mathbb R}^d$, $S^{z,\epsilon}_n=\sum_{j=1}^n {\bf 1}_{\{\|X_j-z\|>\epsilon\}}$.
Let $K$ be the support of $X$. Then:

*

*For every $z\in K$, $P(\|X_1-z\|>\epsilon)<1$ and therefore by LLN,  $P(S^{z,\epsilon}_n > n-i+1) \to 0$

*$P(X \not \in K)=0$.

Thus
\begin{align*} P( |X_{(i)}(X) - X|>\epsilon) &\le P(S^{X,\epsilon}_n > n - i+1 ) \\
 & = E [ \underset{(*)}{\underbrace{P(S^{X,\epsilon}_n > n-i+1 | X)}}{\bf 1}_K(X)]
\end{align*}
By 1., $(*)\to 0$ a.s. on the event $\{X \in K\}$. Using this, bounded convergence and 2. give that the RHS tends to $0$ as $n\to\infty$, completing the proof.
