A problem on rate of decay of fill distance? 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:

*

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


*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: $\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)$.
