Let $X$ be a random variable with values in a closed compact $\Omega \subset \mathbb{R}^m$. Assume $\Omega$ is has a Lipschitz boundary. Let $p(x)$ be the probability density function of $X$ and assume $p(x)>0\ \forall x\in\Omega$.

Now we draw two independent sets of $n$ iid copies of $X$. We denote them $A_n = \{p_1,p_2\ldots p_n\}$ and $B_n = \{q_1,q_2\ldots q_n\}$. Consider $$\ \ \ \ \zeta_n = \max\limits_{x\in B_n}(dist(x,A_n)) = \max\limits_{x\in B_n}\min\limits_{y\in A_n} \|x-y\|_2$$


  1. Does $\zeta_n$ converge to zero, in probability or in expectation?

  2. What can we say about the rate of decay of $\zeta_n$? If we consider $$\gamma_n = \sup\limits_{x\in \Omega}(dist(x,A_n)) = \sup\limits_{x\in \Omega}\min\limits_{y\in A} \|x-y\|_2$$ instead, then I think $\gamma_n \sim n^{-1/m}$. Can we say anything similar thing about $\zeta_n$?


$\newcommand\ep\varepsilon$Let $X:=\Omega$. Suppose that $|B_x(\ep)\cap X|>0$ for all $x\in X$ and all real $\ep>0$, where $|\cdot|$ is the Lebesgue measure and $B_x(\ep)$ is the open ball in $\mathbb R^m$ of radius $\ep$ centered at $x$. Then the condition $p(x)>0$ for all $x\in X$ implies that $P(p_1\in B_x(\ep)\cap X)>0$ and hence $P(p_1\notin B_x(\ep)\cap X)<1$, for all $x\in X$ and all real $\ep>0$.

On the other hand, by the compactness of $X$, for each real $\ep>0$ there is a finite set $F_\ep\subseteq X$ such that $X\subseteq\bigcup_{x\in F_\ep}B_x(\ep)$.

So, for each real $\ep>0$, $$P(\zeta_n\ge2\ep)\le P(\gamma_n\ge2\ep)\le P\Big(\bigcup_{x\in F_\ep}\bigcap_{i=1}^k\{p_i\notin B_x(\ep)\}\Big) \le\sum_{x\in F_\ep}P(p_1\notin B_x(\ep))^n\to0 \tag{1}$$ as $n\to\infty$.

Thus, $\gamma_n\to0$ and $\zeta_n\to0$ in probability, and hence in $L^q$ for all real $q>0$, since $\zeta_n\le\gamma_n\le D<\infty$, where $D$ is the diameter of the compact set $X$.

It should be straightforward to quantify this qualitative argument, in terms such as Dudley's entropy number and explicitly given lower bounds on $|B_x(\ep)\cap X|$ and density $p(x)$. E.g., if $p\ge c$ for some real constant $c>0$, then, by (1), $$P(\zeta_n\ge2\ep)\le N_\ep\,(1-c|B_0(\ep)|)^n,\tag{2}$$ where $N_\ep[\le|F_\ep|]$ is the Dudley entropy number, $|F_\ep|$ is the cardinality of the set $F_\ep$, and $|B_0(\ep)|$ is the Lebesgue measure of $B_0(\ep)$.

In particular, we have $N_\ep\le(C/\ep)^m$ and $|B_0(\ep)|\le(C\ep)^m$ for some real constant $C>0$ depending only on $X$. Using now the inequality $1-u\le e^{-u}$, we see that (2) implies that $\zeta_n=O_P(n^{-1/m}\ln^{1/m}n)$.

  • $\begingroup$ @losifPinelis: Thank you for the answer. I have understood the inequlities on probabilities that you had mentioned. But I am not able to quantify as its not apparent to me how I can use Dudley's entropy. Sorry I am new to probability theory. Appreciate some help on how I can use Dudley's. It seems to be defined for Gaussian processes. I have no clue how I can apply. $\endgroup$
    – Rajesh D
    May 20 at 9:16
  • $\begingroup$ @RajeshD : I have added details. $\endgroup$ May 20 at 14:20
  • $\begingroup$ Thank you for the valuable answer. My expectation was the asymptotic $\zeta_n \sim n^{-1/m}$. (don't know how to formulate this in terms of probability. Can this asymptote still be derived from your answer, is what I am trying to figure out. It is already known that $\gamma_n \sim n^{-1/m}$ if I am not wrong, but I don't remember the source. $\endgroup$
    – Rajesh D
    May 20 at 14:38
  • $\begingroup$ @RajeshD : You can get such a bound but only with an extra log factor, as is now detailed. $\endgroup$ May 20 at 15:32
  • $\begingroup$ Thank you very much Losif. It is helpful. $\endgroup$
    – Rajesh D
    May 20 at 15:48

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.