# 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:

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

• Any hints or directions are also appreciated. Apr 23 at 15:31
• cross posted here: math.stackexchange.com/q/4118031/2987 Apr 27 at 5:39

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

• @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. May 20 at 9:16
• @RajeshD : I have added details. May 20 at 14:20
• 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. May 20 at 14:38
• @RajeshD : You can get such a bound but only with an extra log factor, as is now detailed. May 20 at 15:32
• Thank you very much Losif. It is helpful. May 20 at 15:48