diff --git a/main.tex b/main.tex index 4a752e8629e9bbec80f1e7de0c4a2370fbc6ca32..943d2bd865a982b579dd94ffab5d08ebc1450288 100644 --- a/main.tex +++ b/main.tex @@ -422,51 +422,51 @@ It is useful to introduce some new notation: \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} @@ -528,10 +528,16 @@ Consider the chain (instead of the cycle) for simplicity with vertices identifie 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$.