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

Changeset - fd8b2cc696df

Parent rev.

Child rev.

[Not reviewed]

0 1 2

Tom Bannink - 8 years ago 2017-06-01 22:35:43
tombannink@gmail.com

Add diagram for lemma 12

3 files changed with 89 insertions and 24 deletions:

diagram_proborders.pdf

bin+new file

diagram_proborders.tex

main.tex

0 comments (0 inline, 0 general)

diagram_proborders.pdf

➞

Show inline comments

		new file 100644
		binary diff not shown

diagram_proborders.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}
     \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,...,10} {
         \draw (\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);
+    }
     \foreach \x in {0,...,10} {
         \draw (\x,0.3) node {$\x$};
+    }
     \foreach \x in {2,4,6,7} {
         \draw[fill,red]  (\x,-0.5) circle (0.05);
         \draw[fill,blue] (\x,-1.0)+(-0.05,-0.05) rectangle +(0.05,0.05);
+    }
     \foreach \x in {3,5,8} {
         \draw (\x,-1.5) circle (0.07);
+    }
     \draw[fill,red] (9,-0.5) circle (0.05);
     \draw (2,1) node {$I_\mathrm{min}$};
     \draw (9,1) node {$I_\mathrm{max}$};
     \draw (10.7,-0.2) rectangle (12.0,-1.8);
     \draw[fill,red] (11,-0.5) circle (0.05);
     \draw (11.5,-0.5) node {$I$};
     \draw[fill,blue] (11,-1.0)+(-0.05,-0.05) rectangle +(0.05,0.05);
     \draw (11.5,-1.0) node {$I'$};
     \draw (11,-1.5) circle (0.07);
     \draw (11.6,-1.5) node {$I_{><}$};
     \draw (5,1) node {$k$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

@@ @@ -419,57 +419,57 @@ It is useful to introduce some new notation: @@
 	\begin{center}
     	\includegraphics{diagram_groups.pdf}
     \end{center}
     \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependence}. Here $b_1,b_2\in\{0,1\}^n$ are bitstrings such that all zeroes of $b_1$ and all zeroes of $b_2$ are separated by two indices $j_1,j_2$.}
 \end{figure}
 \begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}
-    Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes that are separated as in Figure \ref{fig:separatedgroups}. Let $j_1$, $j_2$ be any indices `inbetween' the groups as shown in the figure. Then we have
+    Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. Let $j_1$, $j_2$ be any indices inbetween the groups, such that $b_1$ lies on one side of them and $b_2$ on the other, as shown in the figure. Furthermore, let $A_1$ be any event that depends only on the sites ``on the $b_1$ side of $j_1,j_2$'', and similar for $A_2$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2})
+        \mathbb{P}_b(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_1, A_2)
         &=
         \mathbb{P}_{b_1}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2})
+        \mathbb{P}_{b_1}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_1)
         \; \cdot \;
         \mathbb{P}_{b_2}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}) \\
         R_{b,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2}}
         \mathbb{P}_{b_2}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_2) \\
         R_{b,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_1,A_2}
         &=
         R_{b_1,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2}}
+        R_{b_1,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_1}
         \; + \;
         R_{b_2,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2}}
+        R_{b_2,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_2}
     \end{align*}
     up to any order in $p$.
 \end{lemma}
 The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two halves of the circle are independent.
+The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two halves of the circle are independent.
 \begin{proof}
     For clarity we do the proof for the infinite line, when there is only one index. Simply replace $\mathrm{NZ}_j$ by $\mathrm{NZ}_{j_1}\cap\mathrm{NZ}_{j_2}$ for the case of the circle.
-    Note that any path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ can be split into paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$. This can be done by taking all resampling positions $r_i$ in $\xi$ and if its ``on the $b_1$ side of $j_1,j_2$'' then add it to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add it to $\xi_2$. Vice versa, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ by simply concatenating the resampling positions. By the same reasoning as in the proof of claim \ref{claim:expectationsum}, we obtain
+    Note that any path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ can be split into paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$. This can be done by taking all resampling positions $r_i$ in $\xi$ and if $r_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add it to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add it to $\xi_2$. Note that now $\xi_1$ is a path from $b_1$ to $\mathbf{1}$, because in the original path $\xi$, all zeroes ``on the $b_1$ side'' have been resampled by resamplings ``on the $b_1$ side''. Since the sites $j_1,j_2$ inbetween never become zero, there can not be any zero ``on the $b_1$ side'' that was resampled by a resampling ``on the $b_2$ side''.  Vice versa, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ by simply concatenating the resampling positions. By the same reasoning as in the proof of claim \ref{claim:expectationsum}, we obtain
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}_j)
         = \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi]
         &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}}
           \sum_{\substack{\xi_2\in\paths{b_1}\\\xi_2 \in \mathrm{NZ}_j}}
         \mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2)
         = \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j\cap A_1\cap A_2}} \mathbb{P}[\xi]
         &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j\cap A_1}}
           \sum_{\substack{\xi_2\in\paths{b_1}\\\xi_2 \in \mathrm{NZ}_j\cap A_2}}
         \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\
         &=
         \mathbb{P}_{b_1}(\mathrm{NZ}_j)
+        \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1)
         \; \cdot \;
         \mathbb{P}_{b_2}(\mathrm{NZ}_j).
+        \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2).
     \end{align*}
     For the second equality, note that again by the same reasoning as in the proof of claim \ref{claim:expectationsum} we have
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}_j) R_{b,\mathrm{NZ}_j}
         := \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi] |\xi|
         &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}}
           \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}_j}}
         \mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2) R_{b,\mathrm{NZ}_j,A_1,A_2}
         &:= \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\
         &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j\cap A_1}}
           \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}_j\cap A_2}}
         \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\
         &=
         \mathbb{P}_{b_2}(\mathrm{NZ}_j) \mathbb{P}_{b_1}(\mathrm{NZ}_j) R_{b_1,\mathrm{NZ}_j}
         \; + \;
         \mathbb{P}_{b_1}(\mathrm{NZ}_j) \mathbb{P}_{b_2}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} .
         \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2) \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1) R_{b_1,\mathrm{NZ}_j,A_1} \\
         &\quad +
         \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1) \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2) R_{b_2,\mathrm{NZ}_j,A_2} .
     \end{align*}
     Dividing by $\mathbb{P}_b(\mathrm{NZ}_j)$ and using the first equality gives the desired result.
+    Dividing by $\mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2)$ and using the first equality gives the desired result.
 \end{proof}
 \begin{comment}
 TEST: Although a proof of claim \ref{claim:expectationsum} was already given, I'm trying to prove it in an alternate way using claim \ref{claim:eventindependence}.
+~
     Let $b_I$ be the initial state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $P_I(A)=P_{b_I}(A)$ where the latter is defined in Definition \ref{def:conditionedevents}, i.e. the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$.
 \end{definition}
 The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.
 \begin{lemma}\label{lemma:probIndep}
 	Suppose we have a finite set $I\subset\mathbb{N}_+$ of vertices.
-	Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$.
+    Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$. These definitions are illustraded in Figure \ref{fig:lemmaillustration}.
 	Then $P_{I}(Z^{(0)})=P_{I'}(Z^{(0)}) + O(p^{I_{\max}+1-|I|})$.
 \end{lemma}
 \begin{proof}
 \begin{figure}
 	\begin{center}
     	\includegraphics{diagram_proborders.pdf}
     \end{center}
     \caption{\label{fig:lemmaillustration} Illustration of setup of Lemma \ref{lemma:probIndep}.}
 \end{figure}
 	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples vertex $0$ to zero must produce at least $I_{\max}$ zeroes in-between.
     Induction step: For an event $A$ and $k>0$ let us denote $A_k = A\cap\left(\cap_{j=0}^{k-1} \mathrm{Z}^{(j)}\right)\cap \mathrm{NZ}^{(k)}$, i.e. $A_k$ is the event $A$ \emph{and} ``Each vertex in $0,1,2,\ldots, k-1$ becomes $0$ at some point before termination (either by resampling or initialisation), but vertex $k$ does not''. Observe that these events form a partition, so $Z^{(0)}=\dot{\bigcup}_{k=1}^{\infty}Z^{(0)}_k$.
     Let $I_{<k}:=I\cap[1,k-1]$ and similarly $I_{>k}:=I\setminus[1,k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$ (note that $I_{><} = \gaps{I}$ as shown in Figure \ref{fig:diametergap}). Suppose we have proven the claim up to $|I|-1$, then the induction step can be shown by
 	\begin{align*}
 		P_{I}(Z^{(0)})

0 comments (0 inline, 0 general)