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$$


Questions:


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$?



A problem on rate of decay of fill distance?
$\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](https://en.wikipedia.org/wiki/Dudley%27s_theorem#:%7E:text=In%20probability%20theory%2C%20Dudley%27s%20theorem,its%20entropy%20and%20covariance%20structure.) 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)$.


