AENC/resampling_chain Changeset - 53e0f54cd945 · Centrum Wiskunde & Informatica (CWI)

Changeset - 53e0f54cd945

Parent rev.

Child rev.

[Not reviewed]

0 1 2

Tom Bannink - 8 years ago 2017-06-13 16:49:19
tom.bannink@cwi.nl

Add diagrams and proof of 'last part'

3 files changed with 129 insertions and 10 deletions:

diagram_patches.pdf

bin+new file

diagram_patches.tex

main.tex

0 comments (0 inline, 0 general)

diagram_patches.pdf

➞

Show inline comments

		new file 100644
		binary diff not shown

diagram_patches.tex

➞

Show inline comments

@@ new file 100644 @@
 \documentclass{standalone}
 \usepackage[T1]{fontenc}
 \usepackage{amsmath}
 \usepackage{amsfonts}
 \usepackage{parskip}
 \usepackage{marvosym} %Lightning symbol
 \usepackage[usenames,dvipsnames]{color}
 \usepackage[hidelinks]{hyperref}
 \renewcommand*{\familydefault}{\sfdefault}
 \usepackage{bbm} %For \mathbbm{1}
 %\usepackage{bbold}
 \usepackage{tikz}
 \begin{document}
 \begin{tikzpicture}
     % Cirlce
     \draw[gray] (0,0) -- (10,0);
     \draw[dotted] (0,2) -- (10,2);
     \draw[gray] (0,2) arc (90:270:1);
     \draw[gray] (10,0) arc (-90:90:1);
     \foreach \x in {0,...,20} {
         \draw ({0.5*\x},0) circle (0.04);
+    }
     \foreach \a in {-3,...,3} {
         \draw (10,1)+({\a*20}:1) circle (0.04);
         \draw (0,1)+({180+\a*20}:1) circle (0.04);
+    }
     % Numbers
     \foreach \x in {0,...,20} {
         \draw ({0.5*\x},0.3) node {$\x$};
+    }
     % Patch P
     \draw[red] (0.5*6,-0.5) -- (0.5*14,-0.5);
     \foreach \x in {6,...,14} {
         \draw[fill,red]  ({0.5*\x},-0.5) circle (0.05);
+    }
     % S cap P
     \foreach \x in {7,8,10,11,13} {
         \draw[fill,blue] ({0.5*\x},-1.0)+(-0.05,-0.05) rectangle +(0.05,0.05);
+    }
     % S \ P
     \foreach \x in {1,2,4,16,17,19} {
         \draw ({0.5*\x},-1.0) circle (0.07);
+    }
     \draw (3,1) node {$P_\mathrm{min}$};
     \draw (7,1) node {$P_\mathrm{max}$};
     \draw (0.5*1,1) node {$S_\mathrm{min}$};
     \draw (0.5*19,1) node {$S_\mathrm{max}$};
     \draw[->] (3,0.8) -- +(0,-0.3);
     \draw[->] (7,0.8) -- +(0,-0.3);
     \draw[->] (0.5*1,0.8) -- +(0,-0.3);
     \draw[->] (0.5*19,0.8) -- +(0,-0.3);
     \draw (0.5*2.5,-1.5) node {$\leftarrow S_\mathrm{left} \rightarrow$};
     \draw (0.5*17.5,-1.5) node {$\leftarrow S_\mathrm{right} \rightarrow$};
     % Rectangle around legend
     \draw (10.7,-0.2) rectangle (12.3,-1.8);
     \draw[fill,red] (11,-0.5) circle (0.05);
     \draw (11.1,-0.5) node[anchor=west] {$P$};
     \draw[fill,blue] (11,-1.0)+(-0.05,-0.05) rectangle +(0.05,0.05);
     \draw (11.1,-1.0) node[anchor=west] {$S\cap P$};
     \draw (11,-1.5) circle (0.07);
     \draw (11.1,-1.5) node[anchor=west] {$S\cap\overline{P}$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

      \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\
     &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}
     \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \tag{remember Definition~\ref{def:visitingResamplings} and use Claim~\ref{claim:eventindependence}}\\
     &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f_P\in\{0,1'\}^{|S\cap P|}}
     \rho_{S(f_P)}  R^{(P)}_{S(f_P)}\mathbb{P}_{S(f_P)}(A^{(P)})
     \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \\
     &= \frac{1}{n}\sum_{S\subseteq [n]} \sum_{P\text{ patch}} \sum_{f_P\in\{0,1'\}^{|S\cap P|}}
     \rho_{S(f_P)} R^{(P)}_{S(f_P)} \mathbb{P}_{S(f_P)}(A^{(P)})
     \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \\
 	&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f_P\in\{0,1'\}^{|S\cap P|}}
 	\rho_{S(f_P)}
-	\sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathcal{O}(p^{|S_{><}|}) \\
+        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathcal{O}(p^{|S_{><}|}) \tag{see below} \\
 	&= \frac{1}{n}\sum_{S\subseteq [n]}\mathcal{O}(p^{|S|+|S_{><}|}).
     \end{align*}
    	The penultimate inequality can be seen by case separation.
    	If $S_{><}\subseteq P$ then already $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$.
    	Otherwise if all elements of $S_{><}\setminus P$ are larger than $P_{\max}$ then we view the last summation as $\sum_{f'_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}\setminus\{S_{\max}\}|}}\sum_{f''_{\overline{P}}\in\{0,1'\}^{1}}$ and use Lemma~\ref{lemma:probIndep} to conclude the cancellations pairwise regarding the filling of $S_{\max}$, i.e., the value of $f''_{\overline{P}}$. We proceed similarly when
    	all elements of $S_{><}\setminus P$ are smaller than $P_{\min}$. In the last case we again proceed similarly, but now the cancellations will come from the interplay of $4$ fillings, corresponding to the possible filling of $S_{\min}$ and $S_{\max}$ simultaneously.
 \begin{figure}
 	\begin{center}
     	\includegraphics{diagram_patches.pdf}
     \end{center}
     \caption{\label{fig:patches} Illustration of last steps of the proof.}
 \end{figure}
     The penultimate inequality can be seen by case separation as follows: If $S\subseteq P$ then there is no splitting into $S\cap P$ and $S\setminus P$, and we already have $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$ simply because the patch $P$ must be filled with zeroes that were not yet in $S$, so this is at least $|S_{><}|$ resampled zeroes. For the more general case, assume that $S$ is larger than $P$ on both sides of $P$. This is illustrated in Figure \ref{fig:patches}. We will focus on the following sum that was in the above equations:
     \begin{align*}
         \sum_{f_{\overline{P}}\in\{0,1'\}^{|S \cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})
     \end{align*}
     By Lemma \ref{lemma:eventindependence} we can split this sum into two parts: the part to the left of $P$ and the part to the right of $P$. Define $S_\mathrm{left}=S\cap[S_\mathrm{min},P_{\mathrm{min}}-1]$ and $S_\mathrm{right}=S\cap[P_{\mathrm{max}}+1,S_\mathrm{max}]$, so that $S\cap\overline{P} = S_\mathrm{left} \cup S_\mathrm{right}$. These are also illustrated in Figure \ref{fig:patches}. Then we have
     \begin{align*}
         \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})
         &= \mathbb{P}_{S(f_{\mathrm{left}})}(\overline{Z^{(P_{\min}-1)}}) \;\cdot\; \mathbb{P}_{S(f_{\mathrm{right}})}(\overline{Z^{(P_{\max}+1)}})
     \end{align*}
     and hence we can split the sum. Without loss of generality we now only consider the `right' part of the sum:
     \begin{align*}
         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}} \rho_{S_\mathrm{right}(f)} \mathbb{P}_{S_\mathrm{right}(f)}(\overline{Z^{(P_{\max}+1)}})
     \end{align*}
     Now further split this sum over the value of $f$ at position $S_\mathrm{max}$:
     \begin{align*}
         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}} \sum_{f'\in\{0,1'\}}
         \rho_{S_\mathrm{right}(f\,f')} \mathbb{P}_{S_\mathrm{right}(f\,f')}(\overline{Z^{(P_{\max}+1)}})
     \end{align*}
     and we use the definition of $\rho$ for the sum over $f'$:
     \begin{align*}
          \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}
         \rho_{S_\mathrm{right}(f)} \left(p \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) + (-p) \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) \right)
     \end{align*}
     Now we recognize the setup of Lemma~\ref{lemma:probIndep} with $I=S_\mathrm{right}(f\,0)$ and $I'=S_\mathrm{right}(f\,1)$. The lemma yields
     \begin{align*}
         \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-(P_{\mathrm{max}}+1)+1-|S_\mathrm{right}|}) \\
         &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) .
     \end{align*}
     Entering this back into the sum gives
     \begin{align*}
          \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}
         \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|+1})
          = \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}}
         \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|})
     \end{align*}
     One can do the same for the `left' part, which gives a term $\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|})$. The part of $S$ that was within $P$ gives $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|})$. Combining these three factors yields
     \begin{align*}
         (\textrm{left part})(P\textrm{ part})(\textrm{right part}) &=
 \mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|}) \cdot \mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|}) \cdot \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) \\
         &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S_\mathrm{left}\cup S_\mathrm{right}\cup (S\cap P)|})\\
         &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S|})
         = \mathcal{O}(p^{|S_{><}|})
     \end{align*}
     as required. This finishes the proof.
+    ~
 	I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.
     Questions:

0 comments (0 inline, 0 general)