A problem on rate of decay of fill distance?

Question

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

Answer 1

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