world:knn
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
world:knn [2023/11/05 15:10] rdouc [Statement] |
world:knn [2023/11/05 18:04] (current) rdouc [Second proof] |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| $(\Omega,\mcf, \PP)$. | $(\Omega,\mcf, \PP)$. | ||
| - | For any $k \in [1:n]$, define $X^k_{(n)}$ the $k$-th nearest neighboor of | + | For any $k \in [1:n]$, denote by $X^k_{(n)}$ the $k$-th nearest neighboor of |
| $X_0$ among the set $\set{X_k}{k \in [1:n]}$, that is we have the properties | $X_0$ among the set $\set{X_k}{k \in [1:n]}$, that is we have the properties | ||
| * $\|X_0-X^1_{(n)}\| \leq \|X_0-X^2_{(n)}\| \leq \ldots \leq \|X_0-X^n_{(n)}\|$. | * $\|X_0-X^1_{(n)}\| \leq \|X_0-X^2_{(n)}\| \leq \ldots \leq \|X_0-X^n_{(n)}\|$. | ||
| Line 15: | Line 15: | ||
| <WRAP center round tip 90%> | <WRAP center round tip 90%> | ||
| **__Proposition__** | **__Proposition__** | ||
| - | We have $\PP$-a.s., | + | |
| + | For any $k \in \nset$, we have $\PP$-a.s., | ||
| $$ | $$ | ||
| \lim_{n \to \infty} X^k_{(n)}=X_0 | \lim_{n \to \infty} X^k_{(n)}=X_0 | ||
| Line 23: | Line 24: | ||
| ===== Proof ===== | ===== Proof ===== | ||
| - | Note that since $n \mapsto \|X_0-X^k_{(n)}\|$ is non-increasing, $\lim_n X^k_{(n)}=X_0$ means that for any $\epsilon \in \bbQ_+^\star$, the open ball $\ball{X_0,\epsilon}$ contains at least $k$ points among $(X_n)_{n \geq 1}$. Conversely, if $\lim_n X^k_{(n)}=X_0$ does not hold, it means that for some $\epsilon \in \bbQ_+^\star$, the ball $\ball{X_0,\epsilon}$ contains at most $k-1$ points among $(X_n)_{n \geq 1}$. This in turn implies that $\| X_0- X_{m} \| \geq \epsilon$ for any sufficiently large $m$. Hence, | + | Note that since $n \mapsto \|X_0-X^k_{(n)}\|$ is non-increasing, $\lim_n X^k_{(n)}=X_0$ means that for any $\epsilon \in \bbQ_+^*$, the open ball $\ball{X_0,\epsilon}$ contains at least $k$ points among $(X_n)_{n \geq 1}$. Conversely, if $\lim_n X^k_{(n)}=X_0$ does not hold, it means that for some $\epsilon \in \bbQ_+^*$, the ball $\ball{X_0,\epsilon}$ contains at most $k-1$ points among $(X_n)_{n \geq 1}$. This in turn implies that $\| X_0- X_{m} \| \geq \epsilon$ for any sufficiently large $m$. Hence, |
| $$ | $$ | ||
| - | \{\lim_{n \to \infty} X^k_{(n)}=X_0\}^c \subset \cup_{(\epsilon,n) \in \bbQ^\star_+ \times \nset^*}A_{\epsilon,n} \quad \mbox{where} \quad A_{\epsilon,n}=\{\forall m \geq n, \ \| X_0- X_{m} \| \geq \epsilon\} | + | \{\lim_{n \to \infty} X^k_{(n)}=X_0\}^c \subset \cup_{(\epsilon,n) \in \bbQ^*_+ \times \nset^*}A_{\epsilon,n} \quad \mbox{where} \quad A_{\epsilon,n}=\{\forall m \geq n, \ \| X_0- X_{m} \| \geq \epsilon\} |
| $$ | $$ | ||
| From this inclusion property, in order to show that $\PP$-a.s., $\lim_{n \to \infty} X^k_{(n)}=X_0$ and hence | From this inclusion property, in order to show that $\PP$-a.s., $\lim_{n \to \infty} X^k_{(n)}=X_0$ and hence | ||
| - | $\PP\lr{\{\lim_{n \to \infty} X^k_{(n)}=X_0\}^c}=0$, we only need to show that $\PP(A_{\epsilon,n})=0$ for any $ (\epsilon,n) \in \bbQ^\star_+ \times \nset^* $. Using that the $(X_m)_{m \geq 0}$ are iid, | + | $\PP\lr{\{\lim_{n \to \infty} X^k_{(n)}=X_0\}^c}=0$, we only need to show that $\PP(A_{\epsilon,n})=0$ for any $ (\epsilon,n) \in \bbQ^*_+ \times \nset^* $. Using that the $(X_m)_{m \geq 0}$ are iid, |
| \begin{align*} | \begin{align*} | ||
| \PP(A_{\epsilon,n})&=\PP(A_{\epsilon,1})=\PP(\cap_{m=1}^\infty \{\| X_0- X_{m} \| \geq \epsilon\})=\PE\lrb{\lim_{\ell \to \infty} \PE\lrb{\left. \prod_{m=1}^\ell\indiacc{\| X_0- X_{m} \| \geq \epsilon} \right| X_0 }}= \PE\lrb{\lim_{\ell \to \infty} h(X_0)^\ell} | \PP(A_{\epsilon,n})&=\PP(A_{\epsilon,1})=\PP(\cap_{m=1}^\infty \{\| X_0- X_{m} \| \geq \epsilon\})=\PE\lrb{\lim_{\ell \to \infty} \PE\lrb{\left. \prod_{m=1}^\ell\indiacc{\| X_0- X_{m} \| \geq \epsilon} \right| X_0 }}= \PE\lrb{\lim_{\ell \to \infty} h(X_0)^\ell} | ||
| Line 40: | Line 41: | ||
| Note that on $\{h(X_0)=1\}\cap \{X_0 \in A_n\} $, | Note that on $\{h(X_0)=1\}\cap \{X_0 \in A_n\} $, | ||
| \begin{align*} | \begin{align*} | ||
| - | 1&=h(X_0)=\PP\lr{ \| X_0- X_{1} \| \geq \epsilon | X_0 } \leq \PP\lr{ \| X_0-a_n\| + \| a_n-X_{1} \| \geq \epsilon | X_0 } \\ | + | 1=h(X_0)=\PP\lr{ \| X_0- X_{1} \| \geq \epsilon | X_0 } &\leq \PP\lr{ \| X_0-a_n\| + \| a_n-X_{1} \| \geq \epsilon | X_0 } \\ |
| &\leq \PP\lr{ \epsilon/2 + \| a_n-X_{1} \| \geq \epsilon | X_0 }= \PP\lr{\| a_n-X_{1} \|\geq \epsilon/2 | X_0 }\\ | &\leq \PP\lr{ \epsilon/2 + \| a_n-X_{1} \| \geq \epsilon | X_0 }= \PP\lr{\| a_n-X_{1} \|\geq \epsilon/2 | X_0 }\\ | ||
| &=\PP\lr{\| a_n-X_{1} \| \geq \epsilon/2 }=\PP(X_1 \notin A_n)=\PP(X_0 \notin A_n) | &=\PP\lr{\| a_n-X_{1} \| \geq \epsilon/2 }=\PP(X_1 \notin A_n)=\PP(X_0 \notin A_n) | ||
| Line 54: | Line 55: | ||
| $$ | $$ | ||
| which proves \eqref{eq:h} and the proof of the Proposition is completed. | which proves \eqref{eq:h} and the proof of the Proposition is completed. | ||
| + | |||
| + | |||
world/knn.1699193445.txt.gz · Last modified: 2023/11/05 15:10 by rdouc
Page Tools
