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 18:03] rdouc [Second proof] |
world:knn [2023/11/05 18:04] (current) rdouc [Second proof] |
||
|---|---|---|---|
| Line 41: | 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 56: | Line 56: | ||
| 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. | ||
| - | ===== Second proof ===== | ||
| - | |||
| - | Consider the non-increasing sequence $n \mapsto \|X_0-X^k_{(n)}\|$. If $\lim_n X^k_{(n)}=X_0$, it 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$ doesn't hold, it implies 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 \bigcup_{(\epsilon,n) \in \bbQ^*_+ \times \nset^*} A_{\epsilon,n}, | ||
| - | \] | ||
| - | where $A_{\epsilon,n}=\{\forall m \geq n, \ \| X_0- X_{m} \| \geq \epsilon\}$. | ||
| - | |||
| - | To prove 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^*_+ \times \nset^*$. Using the fact that the $(X_m)_{m \geq 0}$ are iid, we have: | ||
| - | \begin{align*} | ||
| - | \PP(A_{\epsilon,n}) &= \PP(A_{\epsilon,1}) \\ | ||
| - | &= \PP\left(\cap_{m=1}^\infty \{\| X_0- X_{m} \| \geq \epsilon\}\right) \\ | ||
| - | &= \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}, | ||
| - | \end{align*} | ||
| - | where $h(X_0)=\PP\lr{ \| X_0- X_{1} \| \geq \epsilon | X_0 }$. | ||
| - | |||
| - | To complete the proof, we only need to show that $h(X_0) \in [0,1)$, $\PP$-a.s. Equivalently, since we already have $h(X_0) \in [0,1]$, we only need to show that | ||
| - | \begin{equation} \label{eq:h1} | ||
| - | \PP\lr{ h(X_0)=1}=0 | ||
| - | \end{equation} | ||
| - | Choose a $\epsilon/2$-net countable covering of $\rset^p$, i.e., $\rset^p \subset \cup_{n \in \nset} A_n$ where $A_n = \ball{a_n,\epsilon/2}$. | ||
| - | |||
| - | Note that on $\{h(X_0)=1\}\cap \{X_0 \in A_n\}$, | ||
| - | \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 } \\ | ||
| - | &\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). | ||
| - | \end{align*} | ||
| - | Hence, $\{h(X_0)=1\}\cap \{X_0 \in A_n\} \subset \{1=\PP(X_0 \notin A_n)\}\cap \{X_0 \in A_n\}$, which implies: | ||
| - | \[ | ||
| - | \PP\lr{h(X_0)=1,X_0 \in A_n} \leq \PP\lr{1 = \PP(X_0 \notin A_n),X_0 \in A_n} = \indiacc{1 = \PP(X_0 \notin A_n)} \PP(X_0 \in A_n) = 0. | ||
| - | \] | ||
| - | |||
| - | This implies that: | ||
| - | \[ | ||
| - | \PP\lr{ h(X_0)=1} = \PP\lr{ h(X_0)=1, X_0 \in \cup_{n \in \nset}A_n } \leq \sum_{n \in \nset} \PP\lr{h(X_0)=1,X_0 \in A_n}=0, | ||
| - | \] | ||
| - | which proves \eqref{eq:h} and completes the proof of the Proposition. | ||
world/knn.1699203794.txt.gz ยท Last modified: 2023/11/05 18:03 by rdouc
Page Tools
