About a density property of the Nearest Neighbor algorithm: part 2.

Question

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and $(\mathcal{X},d)$ be metric space. Suppose that $X,X_1,X_2,X_3,... : \Omega\to\mathcal{X}$ are $\mathbb{P}$-i.i.d. random variables.

Get a closed set $K$ of $(\mathcal{X},d)$ and $x\in\partial K$.

Suppose that: $$\exists \delta_x \in(0,1], \frac{\mathbb{P}(X\in \partial K\cap B_r (x))}{\mathbb{P}(X\in B_r (x))}\to \delta_x, r\to 0^+$$ and $$\frac{\mathbb{P}(X\in K^c\cap B_r (x))}{{\mathbb{P}(X\in B_r (x))}}\to0, r\to 0^+$$ where $B_r(x)$ is the open ball centered in $x$ of radius $r$ in $(\mathcal{X},d)$.

Define: $$\forall m\in\mathbb{N}, \pi_m^x: \mathcal{X}^m\to\{1,...,m\}, (x_1,...,x_m)\mapsto \min\left(\operatorname{argmin}_{k\in\{1,...,m\}}\left\{d\left(x,x_k\right)\right\}\right).$$

Define: $$\forall m\in\mathbb{N}, Z_m^x:\Omega\to\mathcal{X}, \omega\mapsto X_{\pi_m^x\left((X_1(\omega),...,X_m(\omega)\right)}(\omega).$$

Is it true that $\mathbb{P}(Z_m^x\in K^c)\to 0, m\to\infty?$

This is a version with stronger hypothesis of this other question that has a negative answer: About a density property of the Nearest Neighbor algorithm

Answer 1

It turns out that the strategy outlined in edit 7 actually works without further assumptions (Lemma 0 takes care of what was missing in edit 7). Details follow.

---

Proposition 1. If $\mathbb{P}(X=x)>0$ then $\mathbb{P}(Z_m^x\in K^c)\to0, m\to+\infty$

Proof. Since $x\notin K$ we have that $$\mathbb{P}(Z_m^x\in K^c)\le \mathbb{P}\left(\bigcap_{k=1}^m X_k\neq x\right) = \left(1-\mathbb{P}(X=x)\right)^m \to 0, m\to\infty.$$

---

Proposition 2. If there exists $r>0$ such that $\mathbb{P}(X\in K^c \cap B_r(x))=0$ then $\mathbb{P}(Z_m^x\in K^c)\to0, m\to+\infty$.

Proof. Since $\mathbb{P}(X\in B_r(x))>0$ and $\mathbb{P}(X\in K^c \cap B_r(x))=0$ we have that: $$\mathbb{P}(Z_m^x\in K^c)\le \mathbb{P}\left(\bigcap_{k=1}^m X_k\notin B_r(x)\right) = \left(1-\mathbb{P}(X\in B_r(x))\right)^m \to 0, m\to\infty.$$

---

Thanks to Proposition 1 and Proposition 2, we can (and will) assume from now on that $\mathbb{P}(X=x)=0$ and $\forall r>0, \mathbb{P}(X\in K^c \cap B_r(x))>0$

---

Lemma 0. $\lim_{r\to0^+} \frac{\mathbb{P}(X\in K^c\cap \bar B_r(x))}{\mathbb{P}( X\in \bar B_r(x))} =0.$

Proof. We know that $\lim_{r\to0^+} \frac{\mathbb{P}(X\in K^c\cap B_r(x))}{\mathbb{P}(X\in B_r(x))} =0.$ Since the set $$\mathcal{Q}:=\{r>0 : \left(\mathbb{P}(X\in K^c\cap \partial B_r(x))>0\right) \lor \left(\mathbb{P}(X\in \partial B_r(x))>0\right) \}$$ is countable, and since $$\frac{\mathbb{P}(X\in K^c\cap B_s(x))}{\mathbb{P}(X\in B_s(x))}\to\frac{\mathbb{P}(X\in K^c\cap \bar B_r(x))}{\mathbb{P}(X\in \bar B_r(x))}, s\downarrow r$$ for each sequence $r_n \downarrow 0$ we can select $s_n>r_n$ such that $s_n \downarrow 0$ and $$\forall n\in\mathbb{N}, \left|\frac{\mathbb{P}(X\in K^c\cap B_{s_n}(x))}{\mathbb{P}(X\in B_{s_n}(x))}-\frac{\mathbb{P}(X\in K^c\cap \bar B_{r_n}(x))}{\mathbb{P}(X\in \bar B_{r_n}(x))}\right|\le \frac{1}{n}.$$ Then $$\frac{\mathbb{P}(X\in K^c\cap \bar B_{r_n}(x))}{\mathbb{P}(X\in \bar B_{r_n}(x))}\le \frac{1}{n}+\frac{\mathbb{P}(X\in K^c\cap B_{s_n}(x))}{\mathbb{P}(X\in B_{s_n}(x))}\to 0, n\to+\infty.$$ Since $(r_n)_{n\in\mathbb{N}}$ was arbitrary, Lemma 0 follows.

---

Lemma 1. There exist $M>0$ and $(r_m)_{m\in\mathbb{N}, m\ge M}$ such that $0<r_m\to0, m\to+\infty$ and $$\forall m\in\mathbb{N}, (m\ge M)\implies \frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r_m}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r_m}(x))}} \\ \le m \le \frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap B_{r_m}(x))}\sqrt{\mathbb{P}(X \in B_{r_m}(x))}}.$$

Proof. Since $0<\mathbb{P}(X\in \bar B_r)\downarrow \mathbb{P}(X= x) =0, r\downarrow0$ and $\forall r>0, \mathbb{P}(X\in K^c \cap \bar B_r(x))>0$ we have that for each $r>0$ it is well defined $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}}$$ and increases to $+\infty$ as $r\downarrow 0$.

Define $M:=\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{1}(x))}\sqrt{\mathbb{P}(X \in \bar B_{1}(x))}}.$

Now, get $m\in\mathbb{N}$ such that $m\ge M$. Define $$r_m:= \sup\left\{r>0 : \frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}}\ge m\right\}.$$ Notice that for each $r>r_m$ we have that $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}}<m$$ and since $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}} \uparrow \frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r_m}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r_m}(x))}}, r\downarrow r_m$$ we have that $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r_m}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r_m}(x))}} \le m.$$ On the other hand, for each $r\in(0,r_m)$ we have that $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}}\ge m$$ and since $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap \bar B_{r}(x))}\sqrt{\mathbb{P}(X \in \bar B_{r}(x))}} \downarrow \frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap B_{r_m}(x))}\sqrt{\mathbb{P}(X \in B_{r_m}(x))}}, r\uparrow r_m$$ we have that $$\frac{1}{\sqrt{\mathbb{P}(X \in K^c\cap B_{r_m}(x))}\sqrt{\mathbb{P}(X \in B_{r_m}(x))}}\ge m.$$ Since $m$ was arbitrary, Lemma 1 follows.

---

Notation. From now on, $M>0$ and $(r_m)_{m\in\mathbb{N}, m\ge M}$ will be as in Lemma 1 and, to get the notation simpler, we assume that $M=1$ (since we are interested in the behavior for $m$ big this isn't a problem) so that $(r_m)_{m\in\mathbb{N}, m\ge M} = (r_m)_{m\in\mathbb{N}}.$

---

Proposition 3. $\mathbb{P}(Z_m^x\in K^c \cap B_{r_m}(x)) \to 0, m\to+\infty.$

Proof. $$\mathbb{P}(Z_{m}^x \in K^c \cap B_{r_m}(x))\le \mathbb{P}\left(\bigcup_{j=1}^{m} X_j \in K^c \cap B_{r_m}(x)\right) \le \sum_{j=1}^{m} \mathbb{P}(X_j\in K^c\cap B_{r_m}(x)) \\ = m\mathbb{P}(X\in K^c\cap B_{r_m}(x)) \le \left(\frac{\mathbb{P}(X\in K^c\cap B_{r_m}(x))}{\mathbb{P}(X\in B_{r_m}(x))}\right)^{1/2} \to 0, m\to\infty$$

---

Proposition 4. $\mathbb{P}(Z_m^x\in (\bar B_{r_m}(x))^c) \to 0, m\to+\infty.$

Proof. $$\mathbb{P}(Z_{m}^x \in (\bar B_{r_m}(x))^c)\le \mathbb{P}\left(\bigcap_{j=1}^{m} X_j \notin \bar B_{r_m}(x)\right) = \prod_{j=1}^{m} \mathbb{P} (X_j \notin \bar B_{r_m}(x)) \\ = \left(1-\mathbb{P}(X\in \bar B_{r_m}(x))\right)^{m} \le \exp(-m \mathbb{P}(X\in \bar B_{r_m}(x))) \\ \le \exp\left(-\left(\frac{\mathbb{P}(X\in \bar B_{r_m}(x))}{\mathbb{P}(X\in K^c \cap \bar B_{r_m}(x))}\right)^{1/2} \right) \to 0, m\to +\infty.$$

---

Lemma 2. Suppose that $r>0$ and $m\in\mathbb{N}$ are such that $\mathbb{P}(Z_m^x\in\partial B_{r}(x))>0$. Then $$\mathbb{P}(Z_m^x\in K^c | Z_m^x\in\partial B_r(x)) = \mathbb{P}(X\in K^c | X\in \partial B_r(x))$$ and so in particular $$\mathbb{P}(Z_m^x\in K^c \cap \partial B_r(x)) \le \mathbb{P}(X\in K^c | X\in \partial B_r(x)).$$

Proof. Define: $$R:=d(x,X),R_1:=d(x,X_1),...,R_m:=d(x,X_m)$$ and notice that $R,R_1,...,R_m$ are i.i.d. and that $\mathbb{P}(R=r)>0$. Define: $$\forall m\in\mathbb{N}, \sigma_m^x: [0,+\infty)^m\to\{1,...,m\}, (r_1,...,r_m)\mapsto \min\left(\operatorname{argmin}_{k\in\{1,...,m\}}\left\{r_k\right\}\right).$$ Then: $$\pi_m ^x(X_1,...,X_m)= \sigma_m^x(R_1,...,R_m).$$ So: $$\mathbb{P}(Z_m^x\in K^c | Z_m^x\in\partial B_r(x)) = \frac{ \mathbb{P}(Z_m^x\in K^c \cap Z_m^x\in\partial B_r(x))}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(Z_m^x\in K^c \cap Z_m^x\in\partial B_r(x) \cap \sigma_m^x(R_1,...,R_m) = k )}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(X_k\in (K^c\cap \partial B_r(x)) \cap \sigma_m^x(R_1,...,R_{k-1},r,R_{k+1},...,R_m) = k )}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(X_k\in (K^c\cap \partial B_r(x)))\mathbb{P}(\sigma_m^x(R_1,...,R_{k-1},r,R_{k+1},...,R_m) = k )}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(X\in K^c | X\in \partial B_r(x))\mathbb{P}(R_k=r)\mathbb{P}(\sigma_m^x(R_1,...,R_{k-1},r,R_{k+1},...,R_m) = k )}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(X\in K^c | X\in \partial B_r(x))\mathbb{P}(\sigma_m^x(R_1,...,R_m) = k \cap R_k=r)}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \frac{ \sum_{k=1}^m\mathbb{P}(X\in K^c | X\in \partial B_r(x))\mathbb{P}(\sigma_m^x(R_1,...,R_m) = k \cap Z_m^x\in \partial B_r(x))}{\mathbb{P}(Z_m^x\in\partial B_r(x))} = \\ = \mathbb{P}(X\in K^c | X\in \partial B_r(x)) \frac{ \sum_{k=1}^m\mathbb{P}(\sigma_m^x(R_1,...,R_m) = k \cap Z_m^x\in \partial B_r(x))}{\mathbb{P}(Z_m^x\in\partial B_r(x))} \\ = \mathbb{P}(X\in K^c | X\in \partial B_r(x)).$$ Finally: $$\mathbb{P}(Z_m^x\in K^c \cap \partial B_r(x)) = \mathbb{P}(Z_m^x\in K^c | Z_m^x\in\partial B_r(x))\mathbb{P}(Z_m^x\in\partial B_r(x)) \\ = \mathbb{P}(X\in K^c | X\in \partial B_r(x)) \mathbb{P}(Z_m^x\in\partial B_r(x)) \le \mathbb{P}(X\in K^c | X\in \partial B_r(x)).$$

---

Lemma 3. If $m:\mathbb{N}\to \mathbb{N}$ is strictly increasing and such that $$\exists \varepsilon >0, \forall k \in \mathbb{N}, \mathbb{P}(X\in K^c | X\in \partial B_{r_{m_k}}(x))\ge \varepsilon$$ then $$\frac{\mathbb{P}(X\in\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in B_{r_{m_k}}(x))} \to 0, k\to \infty$$ and so $$\mathbb{P}(Z_{m_k}^x \in \partial B_{r_{m_k}})\to 0, k\to +\infty$$

Proof. We have that $$ \varepsilon \mathbb{P}(X\in\partial B_{r_{m_k}}(x)) \le \mathbb{P}(X\in K | X\in\partial B_{r_{m_k}}(x)) \mathbb{P}(X\in\partial B_{r_{m_k}}(x)) = \mathbb{P}(X\in K \cap \partial B_{r_{m_k}}(x)) $$ and so $$\frac{\mathbb{P}(X\in\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in \bar B_{r_{m_k}}(x))} \le\frac{1}{\varepsilon} \frac{\mathbb{P}(X\in K\cap\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in \bar B_{r_{m_k}}(x))} \le \frac{1}{\varepsilon} \frac{\mathbb{P}(X\in K\cap\bar B_{r_{m_k}}(x))}{\mathbb{P}(X\in \bar B_{r_{m_k}}(x))} \to 0 , k\to \infty$$ and since $$\frac{\mathbb{P}(X\in\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in \bar B_{r_{m_k}}(x))} = \frac{\mathbb{P}(X\in\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in B_{r_{m_k}}(x))+\mathbb{P}(X\in \partial B_{r_{m_k}}(x))}$$ it is also clear that $$\gamma(k):=\frac{\mathbb{P}(X\in\partial B_{r_{m_k}}(x))}{\mathbb{P}(X\in B_{r_{m_k}}(x))}\to 0, k\to\infty.$$ Now: $$\mathbb{P}(Z^x_{m_k}\in\partial B_{r_{m_k}}(x)) \le \mathbb{P}\left(\bigcup_{j=1}^{m_k}\left(X_j\in\partial B_{r_{m_k}}(x) \cap \bigcap_{i=1, i\neq j} ^{m_k} X_i\in (B_{r_{m_k}}(x))^c\right)\right)\\ \le m_k\mathbb{P}(X\in\partial B_{r_{m_k}}(x))(1-\mathbb{P}(X\in B_{r_{m_k}}(x)))^{m_k-1}=(*)$$ and: $$(1-\mathbb{P}(X\in B_{r_{m_k}}(x)))^{m_k-1} \le \exp(-(m_k-1)\mathbb{P}(X\in B_{r_{m_k}}(x))) \\ = \exp\left(-\frac{m_k-1}{\gamma(k)}\mathbb{P}(X\in \partial B_{r_{m_k}}(x))\right) $$ so: $$(*)=m_k\mathbb{P}(X\in\partial B_{r_{m_k}}(x)) \exp\left(-\frac{m_k-1}{\gamma(k)}\mathbb{P}(X\in \partial B_{r_{m_k}}(x))\right) \to 0, k\to+\infty.$$

---

Lemma 4. Let $m:\mathbb{N}\to \mathbb{N}$ be strictly increasing. Suppose that $$\mathbb{P}(X\in K^c | X\in \partial B_{r_m}(x)) \nrightarrow 0, m\to\infty.$$ Then there exists a strictly increasing function $k:\mathbb{N}\to \mathbb{N}$ such that $$\mathbb{P}(Z_{m_{k_j}}^x\in K^c \cap \partial B_{r_{m_{k_j}}}(x)) \to 0, j\to \infty $$ Proof: easy consequence of Lemma 3.

---

Proposition 5. $\mathbb{P}(Z_m^x\in K^c \cap \partial B_{r_m}(x)) \to 0, m\to+\infty.$

Proof. If for just a finite number of indexes $m$ we have that $\mathbb{P}(Z_m^x\in K^c \cap \partial B_{r_m}(x))>0$ there's nothing to prove. Otherwise, get all the indexes for which $\mathbb{P}(Z_m^x\in K^c \cap \partial B_{r_m}(x))>0$ and organize them in an strictly increasing sequence. Now, get a subsequence of this sequence, say $(m_k)_{k\in\mathbb{N}}$. If $\mathbb{P}(X\in K^c | X\in \partial B_{r_{m_k}}(x))\to0, k\to\infty$ by Lemma 2 we are done. Otherwise, by Lemma 4 we can find a sub-subsequence $(m_{k_j})_{j\in\mathbb{N}}$ such that $$\mathbb{P}(Z_{m_{k_j}}^x\in K^c \cap \partial B_{r_{m_{k_j}}}(x)) \to 0, j\to \infty.$$ Since every subsequence has a subsequence that converges to zero, we are done.

---

Theorem. $\mathbb{P}(Z_m^x\in K^c) \to 0, m\to+\infty.$

Proof. Thanks to Proposition 3, 4 and 5 we have that $$\mathbb{P}(Z_m^x\in K^c)\\ \le \mathbb{P}(Z_m^x\in K^c \cap B_{r_m}(x)) + \mathbb{P}(Z_m^x\in K^c \cap \partial B_{r_m}(x)) + \mathbb{P}(Z_m^x\in (\bar B_{r_m}(x))^c) \to 0 , m\to +\infty.$$

---

Answer 2

Here's a critical obstruction to many methods of proof.

Let's say we're in $\mathbb{R}^2$, $x$ is the origin, and $\mu$ is supported on countably many concentric circles around the origin. The radii of these circles are $r_n = 10^{10^{-n}}$, and $\mu$ has total mass $2\pi r_n$ on each and is uniformly distributed (Lebesgue measure) on each. (I guess you have to normalize $\mu$ to be a probability measure, so just do that). Let $(K^c)^{(n)}$ be open an arc of proportion $\frac{1}{n}$ on the circle of radius $r_n$, and let $K^c = \cup_{n \ge 1} (K^c)^{(n)}$. Then for all intermediate values of $m$, i.e., those for which it is very probably that at least one point will be on the circle with radius $r_n$ but very improbably that at least one point will be on the circle with radius $r_{n+1}$, the reason that $Z^x_m$ will be in $K$ will not be because it is unlikely that some point will be in $K^c$, but rather, because the first point chosen on the circle with radius $r_n$ will, with probability going to $1$, not be in $K^c$.

My point is that you definitely have to use that $Z^x_m$ cares about the first closest point. It seems that none of your attempts utilize this fact. For example, with respect to edit 5 / the answer below, it will actually be true that $P(\cup_{j=1}^m X_j \in K^c \cap B_r(x))$ is large for any of the smart choices of $r$.

If we change definitions and say that "$Z^x_m$ is in $K$ if at least one of the closest points to $x$ is in $K$", then it will be false that $P(Z^x_m) \to 0$ as $m \to \infty$.

---

Actually, you have done all of the hard work (in edit 5). It seems that you are saying that once you have chosen $s_1 > s_2 > \dots$, it might not be the case that the intervals $(I_j)_j$ overlap enough. This could be true, but why choose $s_1 > s_2 > \dots$ arbitrarily to begin with? You can just consider all $r > 0$ at once. I provide a proof below (which will also make me make sure that your main argument in edit 5 is correct). Below the second fold, I will give some more comments about this problem, to make myself not feel bad about getting the bounty (if I didn't make any mistakes about anything).

---

I will use $\mu$ to denote the measure induced on $\mathcal{X}$ by $P$ (i.e. $\mu(E) = P(X \in E)$).

Theorem: Let $(\mathcal{X},d)$ be a metric space and $\mu$ be a probability distribution on $\mathcal{X}$. Take $x \in \mathcal{X}$ with $\mu(B_r(x)) > 0$ for each $r > 0$. Suppose that $\lim_{r \downarrow 0} \frac{\mu(K^c\cap B_r(x))}{\mu(B_r(x))} = 0$. Then, $P(Z^x_m \in K^c) \to 0$ as $m \to \infty$, where $Z^x_m$ is the nearest neighbor function relative to $x$ (with $m$ samples).

Proof: We can, of course, assume $\mu(K^c \cap B_r(x)) > 0$ for each $r > 0$. Take $\epsilon > 0$. Take $r_0 > 0$ so that $\frac{\mu(K^c \cap B_r(x))}{\mu(B_r(x))} < \epsilon$ for each $0 < r < r_0$. The map $(\frac{1}{3},\frac{2}{3})\times(0,r_0) \to (0,\infty)$, $(\alpha,r) \mapsto \frac{1}{\mu(B_r(x))}\frac{1}{[\frac{\mu(K^c\cap B_r(x))}{\mu(B_r(x))}]^\alpha}$ is continuous; its image has the form $(\eta,\infty)$, since $r$ going to $0$ makes the function blow up. Take any $m \in \mathbb{N}$ with $m \ge \eta$. Take $\alpha \in (\frac{1}{3},\frac{2}{3})$ and $0 < r < r_0$ with $m = \frac{1}{\mu(B_r(x))}\frac{1}{[\frac{\mu(K^c\cap B_r(x))}{\mu(B_r(x))}]^\alpha}$. Then, $$P(Z^x_m \in K^c \cap B_r(x)) \le P(\cup_{j=1}^m X_j \in K^c \cap B_r(x)) \le \sum_{j=1}^m P(X_j \in K^c \cap B_r(x))$$ $$= m\mu(K^c \cap B_r(x)) = (\frac{\mu(K^c \cap B_r(x))}{\mu(B_r(x))})^{1-\alpha} \le \epsilon^{1/3}.$$ And, $$P(Z^x_m \in B_r(x))^c = \mu(B_r(x)^c)^m = (1-\mu(B_r(x)))^m \le \exp(-m\mu(B_r(x)))$$ $$= \exp(-(\frac{\mu(K^c\cap B_r(x))}{\mu(B_r(x))})^{-\alpha}) \le \exp(-\epsilon^{-1/3}).$$ Therefore, $$P(Z^x_m \in K^c) \le P(Z^x_m \in K^c \cap B_r(x))+P(Z^x_m \in B_r(x))^c) \le \epsilon^{1/3}+\exp(-\epsilon^{-1/3}),$$ which can be made arbitrarily small by taking $\epsilon$ arbitrarily small. $\square$

---

Claim: The theorem above is false if we only insist that $\frac{\mu(K^c \cap B_r(x))}{\mu(B_r(x))}$ goes to $0$ along a subsequence of $r$.

Proof: Take $\mathcal{X} = \{z \in \mathbb{R}^2 : |z| < 1\}$, $d$ to be standard Euclidean metric, and $\mu$ to be Lebesgue measure (uniform distribution). Let $K^c = \cup_{k \ge 1} \{\frac{1}{2^{10^{2k+1}}} < |z| < \frac{1}{2^{10^{2k}}}\}$. Clearly, for $x$ the origin, $\frac{\mu(K^c \cap B_r(x))}{\mu(B_r(x))}$ goes to $0$ along $(r_k)_k = (2^{10^{2k+1}})_{k \ge 1}$. Finally, $$P(|Z^x_m| \in [\frac{1}{2^{10^{2k+1}}},\frac{1}{2^{10^{2k}}}]) \ge 1-P(|Z^x_m| < \frac{1}{2^{10^{2k+1}}})-P(|Z^x_m| > \frac{1}{2^{10^{2k}}})$$ $$\ge 1-m\frac{\pi}{(2^{10^{2k+1}})^2}-(1-\frac{\pi}{(2^{10^{2k}})^2})^m,$$ so we can take $m = 2^{3\cdot 10^{2k}}$ to see that $P(Z^x_m)$ is exponentially close to $1$. $\square$