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

Changeset - 604c0595b81c

Parent rev.

Child rev.

[Not reviewed]

Merge

0 3 0

Andras Gilyen - 8 years ago 2017-09-07 15:53:45
gilyen@clayoquot.swat.cwi.nl

nicer proof

3 files changed with 85 insertions and 236 deletions:

diagram_groups.pdf

bin+mod

diagram_groups.tex

main.tex

228

0 comments (0 inline, 0 general)

diagram_groups.pdf

➞

Show inline comments

binary diff not shown

diagram_groups.tex

➞

Show inline comments

@@ @@ -15,7 +15,7 @@ @@
 \begin{document}
 \begin{tikzpicture}[scale=0.8]
-    \def\r{4};
+    \def\r{2.5};
     % Line and circles
     \foreach \a in {0,...,23} {
@@ @@ -25,26 +25,26 @@ @@
     % Red dots
     \foreach \a in {-3,0,2,3,4,5,6} {
-        \draw[fill,red] ({\a*15}:\r) circle (0.07);
+        \draw[fill,red] ({\a*15}:\r) circle (0.12);
+    }
     % Red label
     \draw [fill,red] ({1*15}:\r/2) circle (0.07);
     \draw ({1*15}:\r/2) +(0,-0.3) node {zeroes of $b_2$};
     \draw [fill,red] ({2*15}:\r/2) circle (0.12);
     \draw ({2*15}:\r/2) +(0,-0.3) node {zeroes of $b_2$};
     % Blue squares
     \foreach \a in {9,10,11,14,16,17} {
         \draw[fill,blue] ({\a*15}:\r) +(-0.15,-0.1) -- +(0.15,-0.1) -- +(0,0.15);
+    }
     % Blue label
     \draw[fill,blue] ({11*15}:\r/2) +(-0.15,-0.1) -- +(0.15,-0.1) -- +(0,0.15);
     \draw ({11*15}:\r/2) +(0,-0.3) node {zeroes of $b_1$};
     \draw[fill,blue] ({12*15}:\r/2) +(-0.15,-0.1) -- +(0.15,-0.1) -- +(0,0.15);
     \draw ({12*15}:\r/2) +(0,-0.3) node {zeroes of $b_1$};
     % Arrows
     \draw[->] ({7*15}:\r-1) -- ({7*15}:\r-0.2);
     \draw[->] ({20*15}:\r-1) -- ({20*15}:\r-0.2);
     % Labels j1 j2
     \draw ({7*15}:\r-1) +(0,-0.2) node {$j_1$};
     \draw ({20*15}:\r-1) +(0,+0.2) node {$j_2$};
     \draw ({7*15}:\r-1) +(0,-0.2) node {$v$};
     \draw ({20*15}:\r-1) +(0,+0.2) node {$w$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

@@ @@ -59,6 +59,7 @@ @@
 \newcommand{\diam}[1]{\mathcal{D}\left(#1\right)}
 \newcommand{\paths}[1]{\mathcal{P}\left(#1\to\mathbf{1}\right)}
 \newcommand{\start}[1]{\textsc{start}\left(#1\right)}
 \newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}
 \newcommand{\gaps}[1]{#1_{\mathrm{gaps}}}
 \renewcommand{\P}{\mathbb{P}}
 where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$.
 \newpage
 \subsection{Proving the strong cancellation claim}
 It is useful to introduce some new notation. Note that an \emph{event} is a subset of all possible paths of the Markov Chain.
 \section{Proving the strong cancellation claim}
 It is useful to introduce some new notation. We will consider variations of the Markov Chains:
 \begin{itemize}
     \item $\P^{(n)}$ refers to the original process on the length-$n$ cycle.
     \item $\P^{[a,b]}$ or $\P^{[n]}$ refers to a similar Markov Chain but on a finite chain ($[a,b]$ or $[1,n]$).
 \end{itemize}
 The process on the finite chain has the following modification at the boundary: if a boundary site is resampled, it can not resample one of its neighbors so it ignores it and only draws two new bits.
 %Note that an \emph{event} is a subset of all possible paths of the Markov Chain.
 \begin{definition}[Events conditioned on starting state] \label{def:conditionedevents}
     For any state $b\in\{0,1\}^n$, define $\textsc{start}(b)$ as the event that the starting state of the chain is the state $b$. For any event $A$, define
     \begin{align*}
         \mathbb{P}_b(A) &= \mathbb{P}(A \;|\; \textsc{start}(b)) \\
         R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b))
         \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \textsc{start}(b)) %\\
         %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b))
     \end{align*}
     Furthermore, for the Markov Chain on the finite chain, define
     \begin{align*}
         \P^{[n]}_{\partial=1}(A) &= \P^{[n]}(A \;|\; \text{boundary is initialized to }1)
     \end{align*}
     where the boundary of $[n]$ is site $1$ and site $n$, and the boundary of $[a,b]$ are $a$ and $b$.
 \end{definition}
 %Note that we have $\P^{(n)}(\textsc{start}(b)) = (1-p)^{|b|}p^{n-|b|}$ by definition of our Markov Chain.
 \begin{definition}[Vertex visiting event] \label{def:visitingResamplings}
-    Denote by $\mathrm{Z}^{(j)}$ the event that site $j$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(j)}$, i.e. the event that site $j$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(j_1,j_2)} := \mathrm{NZ}^{(j_1)} \cap \mathrm{NZ}^{(j_2)}$, i.e. the event that \emph{both} $j_1$ and $j_2$ do not become zero before termination.
+    Denote by $\mathrm{Z}^{(v)}$ the event that site $v$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(v)}$, i.e. the event that site $v$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(v,w)} := \mathrm{NZ}^{(v)} \cap \mathrm{NZ}^{(w)}$, i.e. the event that \emph{both} $v$ and $w$ do not become zero before termination.
 \end{definition}
 \begin{figure}
 	\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$.}
+    \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 $v,w$.}
 \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 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
+    Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. Let $v$, $w$ 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 $v,w$'', 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,j_2)}, A_1, A_2)
+        \P^{(n)}_b(\mathrm{NZ}^{(v,w)}, A_1, A_2)
         &=
-        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)}, A_1)
+        \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)}, A_1)
         \; \cdot \;
         \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)}, A_2) \\
         \mathbb{P}_b(A_1, A_2 \mid \mathrm{NZ}^{(j_1,j_2)})
         \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)}, A_2) \\
         \P^{(n)}_b(A_1, A_2 \mid \mathrm{NZ}^{(v,w)})
         &=
-        \mathbb{P}_{b_1}(A_1 \mid \mathrm{NZ}^{(j_1,j_2)})
+        \P^{(n)}_{b_1}(A_1 \mid \mathrm{NZ}^{(v,w)})
         \; \cdot \;
         \mathbb{P}_{b_2}(A_2 \mid \mathrm{NZ}^{(j_1,j_2)}) \\
         R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}
         &=
         R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1}
         \; + \;
         R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2}
         \P^{(n)}_{b_2}(A_2 \mid \mathrm{NZ}^{(v,w)}) .%\\
         %R_{b,\mathrm{NZ}^{(v,w)},A_1,A_2}
         %&=
         %R_{b_1,\mathrm{NZ}^{(v,w)},A_1}
         %\; + \;
         %R_{b_2,\mathrm{NZ}^{(v,w)},A_2}
     \end{align*}
     up to any order in $p$.
+    %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 cycle are independent.
+The lemma says that conditioned on $v$ and $w$ not being crossed, the two halves of the cycle are independent.
 \begin{proof}
     From any path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ we can construct paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ as follows. Let us write the path $\xi$ as
     $$\xi=\left( (z_1, s_1, r_1), (z_2, s_2, r_2), ..., (z_{|\xi|}, s_{|\xi|}, r_{|\xi|}) \right)$$
     From any path $\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)}$ we can construct paths $\xi_1\in\start{b_1}\cap \mathrm{NZ}^{(v,w)}$ and $\xi_2\in\start{b_2}\cap\mathrm{NZ}^{(v,w)}$ as follows. Let us write the path $\xi$ as
     $$\xi=\left( (\text{initialize }b), (z_1, s_1, r_1), (z_2, s_2, r_2), ..., (z_{|\xi|}, s_{|\xi|}, r_{|\xi|}) \right)$$
     where $z_i\in[n]$ denotes the number of zeroes in the state before the $i$th step, $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. We have
     \begin{align*}
-        \P_b[\xi] &= \P(\text{pick }s_1) \P(r_1) \P(\text{pick }s_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi|}) \P(r_{|\xi|}) \\
+        \P^{(n)}_b[\xi] &= \P(\text{pick }s_1 | z_1) \P(r_1) \P(\text{pick }s_2 | z_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi|} | z_{|\xi|}) \P(r_{|\xi|}) \\
                 &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi|}} \P(r_{|\xi|}) .
     \end{align*}
-    To construct $\xi_1$ and $\xi_2$, start with empty sequences $\xi_1,\xi_2$ and for each step $(z_i,s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add $(z^{(1)}_i,s_i,r_i)$ to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add $(z^{(2)}_i,s_i,r_i)$ to $\xi_2$. Here $z^{(1)}_i$ is the number of zeroes that were on the $b_1$ side and $z^{(2)}_i$ is the number of zeroes on the $b_2$ side so we have $z_i = z^{(1)}_i + z^{(2)}_i$.
+    To construct $\xi_1$ and $\xi_2$, start with $\xi_1 = \left( (\text{initialize }b_1) \right)$ and $\xi_2 = \left( (\text{initialize }b_2) \right)$. For each step $(z_i,s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $v,w$'' then append $(z^{(1)}_i,s_i,r_i)$ to $\xi_1$ and if its ``on the $b_2$ side of $v,w$'' then append $(z^{(2)}_i,s_i,r_i)$ to $\xi_2$. Here $z^{(1)}_i$ is the number of zeroes that were on the $b_1$ side and $z^{(2)}_i$ is the number of zeroes on the $b_2$ side so we have $z_i = z^{(1)}_i + z^{(2)}_i$.
     %Let the resulting paths be
     %\begin{align*}
     %    \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\
     %    \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right)
     %\end{align*}
     Now $\xi_1$ is a valid (terminating) 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, any two paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$.
     Now $\xi_1$ is a valid (terminating) 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 $v,w$ 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, any two paths $\xi_1\in\start{b_1}\cap \mathrm{NZ}^{(v,w)}$ and $\xi_2\in\start{b_2}\cap\mathrm{NZ}^{(v,w)}$ also induce a path $\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$.
     For a fixed $\xi_1,\xi_2$ we will now show the following:
     \begin{align*}
         \sum_{\substack{\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P_b[\xi] &=
         \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2] \\
         &= \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2]
         \sum_{\substack{\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P^{(n)}_b[\xi] &=
         \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2] \\
         &= \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2]
     \end{align*}
     where both sums are over $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ terms.
     This is best explained by an example. Lets consider the following fixed $\xi_1,\xi_2$ and an example interleaving where we choose steps from $\xi_2,\xi_1,\xi_1,\xi_2,\cdots$:
     \end{align*}
     The probability of $\xi_1$, started from $b_1$, is given by
     \begin{align*}
-        \P_{b_1}[\xi_1] &= \P(\text{pick }s_1) \P(r_1) \P(\text{pick }s_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi_1|}) \P(r_{|\xi_1|}) \\
+        \P^{(n)}_{b_1}[\xi_1] &= \P(\text{pick }s_1|z_1) \P(r_1) \P(\text{pick }s_2|z_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi_1|}|z_{|\xi_1|}) \P(r_{|\xi_1|}) \\
                 &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi_1|}} \P(r_{|\xi_1|}) .
     \end{align*}
     and similar for $\xi_2$ but with primes.
     For the labels shown within the grid, define $p_{ij} = \frac{z_i}{z_i + z_j'}$.
     The probability of $\xi$ is given by
     \begin{align*}
-        \P_b[\xi] &= \frac{1}{z_1+z_1'} \P(r_1') \frac{1}{z_1+z_2'} \P(r_1) \frac{1}{z_2+z_2'} \P(r_2) \frac{1}{z_3+z_2'} \P(r_2') \cdots \tag{by definition}\\
+        \P^{(n)}_b[\xi] &= \frac{1}{z_1+z_1'} \P(r_1') \frac{1}{z_1+z_2'} \P(r_1) \frac{1}{z_2+z_2'} \P(r_2) \frac{1}{z_3+z_2'} \P(r_2') \cdots \tag{by definition}\\
         &=
         \frac{z_1'}{z_1+z_1'} \frac{1}{z_1'} \P(r_1') \;
         \frac{z_1 }{z_1+z_2'} \frac{1}{z_1 } \P(r_1 ) \;
         \frac{z_2 }{z_2+z_2'} \;
         \frac{z_2'}{z_3+z_2'}
         \cdots
         \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $\P_{b_i}[\xi_i]$} \\
         &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $p_{i,j}$} \\
         &= \P(\text{path in grid}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2]
         \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2] \tag{definition of $\P^{(n)}_{b_i}[\xi_i]$} \\
         &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2] \tag{definition of $p_{i,j}$} \\
         &= \P(\text{path in grid}) \; \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2]
     \end{align*}
     In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This proves the required equality.
     We obtain
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2)
         &= \sum_{\substack{\xi\in\paths{b} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] \\
         &= \sum_{\substack{\xi_1\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1}} \;\;
           \sum_{\substack{\xi_2\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
         \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\
         \P^{(n)}_b(\mathrm{NZ}^{(v,w)},A_1,A_2)
         &= \sum_{\substack{\xi\in\start{b} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_1\cap A_2}} \P^{(n)}_b(\xi) \\
         &= \sum_{\substack{\xi_1\in\start{b_1} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_1}} \;\;
           \sum_{\substack{\xi_2\in\start{b_1} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_2}}
         \P^{(n)}_{b_1}(\xi_1)\cdot\P^{(n)}_{b_2}(\xi_2) \\
         &=
-        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)
+        \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1)
         \; \cdot \;
-        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).
+        \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2).
     \end{align*}
     The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.
     For the third equality, by the same reasoning we can decompose the paths
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}
         &\equiv \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\
         &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}
           \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
         \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\
         &=
         \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1} \\
         &\quad +
         \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2} .
     \end{align*}
     Dividing by $\mathbb{P}_b(\mathrm{NZ}_{(j_1,j_2)},A_1,A_2)$ and using the first equality gives the desired result.
     %For the third equality, by the same reasoning we can decompose the paths
     %\begin{align*}
     %    \P^{(n)}_b(\mathrm{NZ}^{(v,w)},A_1,A_2) R_{b,\mathrm{NZ}^{(v,w)},A_1,A_2}
     %    &\equiv \sum_{\substack{\xi\in\start{b}\\\xi \in \mathrm{NZ}^{(v,w)}\cap A_1\cap A_2}} \P^{(n)}[\xi] |\xi| \\
     %    &= \sum_{\substack{\xi_1\in\start{b_1}\\\xi_1 \in \mathrm{NZ}^{(v,w)}\cap A_1}}
     %      \sum_{\substack{\xi_2\in\start{b_2}\\\xi_2 \in \mathrm{NZ}^{(v,w)}\cap A_2}}
     %    \P^{(n)}[\xi_1]\P^{(n)}[\xi_2] (|\xi_1| + |\xi_2|) \\
     %    &=
     %    \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2) \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1) R_{b_1,\mathrm{NZ}^{(v,w)},A_1} \\
     %    &\quad +
     %    \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1) \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2) R_{b_2,\mathrm{NZ}^{(v,w)},A_2} .
     %\end{align*}
     %Dividing by $\P^{(n)}_b(\mathrm{NZ}_{(v,w)},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}.
+~
 Assume that $b_1$ ranges up to site $0$, the gap ranges from sites $1,...,k$ and $b_2$ ranges from site $k+1$ and onwards. For $j=1,...,k$ define the ``partial-zeros'' event $\mathrm{PZ}_j = \mathrm{Z}_1 \cap \mathrm{Z}_2 \cap ... \cap \mathrm{Z}_{j-1} \cap \mathrm{NZ}_j$ i.e. the first $j-1$ sites of the gap become zero and site $j$ does not become zero. Also define the ``all-zeros'' event $\mathrm{AZ} = \mathrm{Z}_1 \cap ... \cap \mathrm{Z}_k$, where all sites of the gap become zero. Note that these events partition the space, so we have for all $b$ that $\sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) = 1 - \mathbb{P}_b(\mathrm{AZ}) = 1 - \mathcal{O}(p^k)$.
+~
 Furthermore, if site $j$ becomes zero when starting from $b_1$ it means all sites to the left of $j$ become zero as well. Similarly, from $b_2$ it implies all the sites to the right of $j$ become zero.
 Because of that, we have
 \begin{align*}
     \mathbb{P}_{b_1}(\mathrm{PZ}_j) &= \mathbb{P}_{b_1}(\mathrm{Z}_{j-1} \cap \mathrm{NZ}_j) = \mathcal{O}(p^{j-1}) \\
     \mathbb{P}_{b_2}(\mathrm{NZ}_j) &= 1 - \mathbb{P}_{b_2}(\mathrm{Z}_j) = 1 - \mathcal{O}(p^{k-j+1})
 \end{align*}
 Following the proof of claim \ref{claim:eventindependence} we also have
 \begin{align*}
     \mathbb{P}_b(\mathrm{PZ}_{j})
     &=
     \mathbb{P}_{b_1}(\mathrm{PZ}_{j})
     \; \cdot \;
     \mathbb{P}_{b_2}(\mathrm{NZ}_{j}) \\
     R_{b,\mathrm{PZ}_{j}}
     &=
     R_{b_1,\mathrm{PZ}_{j}}
     \; + \;
     R_{b_2,\mathrm{NZ}_{j}}
 \end{align*}
 Now observe that
 \begin{align*}
     R_b &= \sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) R_{b,\mathrm{PZ}_j} + \mathbb{P}_b(\mathrm{AZ}) R_{b,\mathrm{AZ}} \\
         &= \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{NZ}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}
         + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}
         + \mathcal{O}(p^k) \\
         &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}
         - \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{Z}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}
         + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}
         + \mathcal{O}(p^k) \\
         &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}
         + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}
         + \mathcal{O}(p^k) \\
         &= R_{b_1}
         + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}
         + \mathcal{O}(p^k) \\
         &\overset{???}{=} R_{b_1} + R_{b_2} + \mathcal{O}(p^k)
 \end{align*}
 \end{comment}
 Consider the chain (instead of the cycle) for simplicity with vertices identified by $\mathbb{Z}$.
 \begin{definition}[Starting state dependent probability distribution.]
 	Let $I\subset\mathbb{Z}$ be a finite set of vertices.
-    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$.
+    Let $b_I$ be the state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $\P^{(n)}_I(A)=\P^{(n)}_{b_I}(A)$ which is defined in Definition \ref{def:conditionedevents}.
 \end{definition}
 New:
 \begin{lemma}[Conditional independence] \label{lemma:eventindependenceNew}
-	Let $i,j \in [n]$, and let $A$ be any event that depends only on the sites $[i,j]$ (meaning the initialization and resamples) and similarly $B$ an event that depends only on the sites $[j,i]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have
+	Let $v,w \in [n]$, and let $A$ be any event that depends only on the sites $[v,w]$ (meaning the initialization and resamples) and similarly $B$ an event that depends only on the sites $[w,v]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have
 	\begin{align*}
-		\P^{(n)}(\mathrm{NZ}^{(i,j)}\cap A\cap B)
+		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)
+		=
-		\P_{b_i=b_j=1}^{[i,j]}(\mathrm{NZ}^{(i,j)}\cap A)
+		\P_{b_v=b_w=1}^{[v,w]}(\mathrm{NZ}^{(v,w)}\cap A)
 		\; \cdot \;
-		\P^{[j,i]}(\mathrm{NZ}^{(i,j)}\cap B),
+		\P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B),
 	\end{align*}
 	and similarly
 	\begin{align*}
-		\P^{[n]}(\mathrm{NZ}^{(i)}\cap A\cap B)
+		\P^{[n]}(\mathrm{NZ}^{(v)}\cap A\cap B)
+		=
-		\P_{b_i=1}^{[i]}(\mathrm{NZ}^{(i)}\cap A)
+		\P_{b_v=1}^{[v]}(\mathrm{NZ}^{(v)}\cap A)
 		\; \cdot \;
-		\P^{[i,n]}(\mathrm{NZ}^{(i)}\cap B)
+		\P^{[v,n]}(\mathrm{NZ}^{(v)}\cap B)
 	\end{align*}
-	up to any order in $p$.
+	where there is no longer a condition on the starting state.
 \end{lemma}
 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.
     To actually go below $2k$ one needs to be careful, because there are periodic configurations that are invariant under some rotations causing double counting issues. This can be probably resolved by showing that when a pattern becomes periodic for some $n$ it actually produces periodicity times more expectation due to symmetry. But this is all just speculation.
 \end{comment}
 \newpage
 \textbf{test:} Rewrite of lemma and proof
 \begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}
     Let $b=b_L\land b_R\in\{0,1\}^n$ be a state with two groups ($b_L\lor b_R = 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_L$ lies on one side of them (left) and $b_R$ on the other (right), as shown in the figure. Furthermore, let $A_L$ be any event that depends only on the sites ``on the $b_L$ side of $j_1,j_2$'', and similar for $A_R$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)}, A_L, A_R)
         &=
         \mathbb{P}_{b_L}(\mathrm{NZ}^{(j_1,j_2)}, A_L)
         \; \cdot \;
         \mathbb{P}_{b_R}(\mathrm{NZ}^{(j_1,j_2)}, A_R) \\
         \mathbb{P}_b(A_L, A_R \mid \mathrm{NZ}^{(j_1,j_2)})
         &=
         \mathbb{P}_{b_L}(A_L \mid \mathrm{NZ}^{(j_1,j_2)})
         \; \cdot \;
         \mathbb{P}_{b_R}(A_R \mid \mathrm{NZ}^{(j_1,j_2)}) \\
         R_{b,\mathrm{NZ}^{(j_1,j_2)},A_L,A_R}
         &=
         R_{b_L,\mathrm{NZ}^{(j_1,j_2)},A_L}
         \; + \;
         R_{b_R,\mathrm{NZ}^{(j_1,j_2)},A_R}
     \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 cycle are independent.
 \begin{proof}
     From any path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ we can construct paths $\xi_L\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_R\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ as follows. Let us write the path $\xi$ as
     $$\xi=\left( (s_1, r_1), (s_2, r_2), ..., (s_{|\xi|}, r_{|\xi|}) \right)$$
     where $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. Denote by $\textsc{state}_i \in \{0,1\}^n$ the state of the system at the start of step $i$. We have
     \begin{align*}
         \P_b[\xi] &= \P(\text{pick }s_1 | \textsc{state}_1 ) \P(r_1) \P(\text{pick }s_2 | \textsc{state}_2 ) \P(r_2) \cdots \P(\text{pick }s_{|\xi|} | \textsc{state}_{|\xi|} ) \P(r_{|\xi|})
     \end{align*}
     To construct $\xi_L$ and $\xi_R$, start with empty sequences $\xi_L,\xi_R$ and for each step $(s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add $(s_i,r_i)$ to $\xi_L$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add $(s_i,r_i)$ to $\xi_R$.
     %Let the resulting paths be
     %\begin{align*}
     %    \xi_L &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_L|}}, s_{a_{|\xi_L|}}, r_{a_{|\xi_L|}}) \right) \\
     %    \xi_R &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_L|}}, s_{b_{|\xi_L|}}, r_{b_{|\xi_L|}}) \right)
     %\end{align*}
     Now $\xi_L$ is a valid (terminating) 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, any two paths $\xi_L\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_R\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply interleaving the resampling positions. Note that $\xi_L,\xi_R$ actually induce $\binom{|\xi_L|+|\xi_R|}{|\xi_L|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_L$ and $\xi_R$.
     For a fixed $\xi_L,\xi_R$ we will now show the following:
     \begin{align*}
         \sum_{\substack{\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_L,\xi_R }} \P_b[\xi] &=
         \sum_{\text{interleavings of }\xi_L,\xi_R} \P(\text{interleaving}) \cdot \P_{b_1}[\xi_L] \cdot \P_{b_2}[\xi_R] \\
         &= \P_{b_1}[\xi_L] \cdot \P_{b_2}[\xi_R]
     \end{align*}
     where both sums are over $\binom{|\xi_L|+|\xi_R|}{|\xi_L|}$ terms.
     This is best explained by an example. Lets consider the following fixed $\xi_L,\xi_R$ and an example interleaving where we choose steps from $\xi_R,\xi_L,\xi_L,\xi_R,\cdots$:
     \begin{align*}
         \xi_L &= \left( (s_1, r_1), (s_2, r_2), (s_3, r_3), (s_4, r_4),\cdots  \right) \\
         \xi_R &= \left( (s_1', r_1'), (s_2', r_2'), (s_3', r_3'), (s_4', r_4'),\cdots  \right) \\
         \xi   &= \left( (s_1', r_1'), (s_1, r_1), (s_2, r_2), (s_2', r_2'), \cdots \right)
     \end{align*}
     Denote by $\textsc{state}^{L}_i\in\{0,1\}^n$ the state of the system at the start of step $i$ of $\xi_L$ and similar for $\xi_R$. Denote by $\textsc{state}^{L+R}_i$ the state at the start of step $i$ for this particular interleaving $\xi$.
     The probability of $\xi_L$, started from $b_1$, is given by
     \begin{align*}
         \P_{b_L}[\xi_L] &= \P(\text{pick }s_1 | \textsc{state}^{L}_1 ) \P(r_1) \P(\text{pick }s_2 | \textsc{state}^{L}_2 ) \P(r_2) \cdots \P(\text{pick }s_{|\xi_L|} | \textsc{state}^{L}_{|\xi_L|} ) \P(r_{|\xi_L|})
     \end{align*}
     and similar for $\xi_R$.
     The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $\xi$ in the example above.
     \begin{center}
         \includegraphics{diagram_paths2.pdf}
     \end{center}
     For the labels shown within the grid, define $p_{ij} = \frac{z_i}{z_i + z_j'}$.
     The probability of $\xi$ is given by
     \begin{align*}
         \P_b[\xi]
         &=
         \P(\text{pick }s_1' | \textsc{state}^{L+R}_1 ) \P(r_1')
         \P(\text{pick }s_1  | \textsc{state}^{L+R}_2 ) \P(r_1 ) \\
  &\qquad\P(\text{pick }s_2  | \textsc{state}^{L+R}_3 ) \P(r_2 )
         \P(\text{pick }s_2' | \textsc{state}^{L+R}_4 ) \P(r_2') \\
         &=
         \P(\text{pick right}) \P(\text{pick }s_1' | \textsc{state}^{R}_1 ) \P(r_1')
         \P(\text{pick left} ) \P(\text{pick }s_1  | \textsc{state}^{L}_1 ) \P(r_1 ) \\
  &\qquad\P(\text{pick left} ) \P(\text{pick }s_2  | \textsc{state}^{L}_2 ) \P(r_2 )
         \P(\text{pick right}) \P(\text{pick }s_2' | \textsc{state}^{R}_2 ) \P(r_2') \\
         &= \P(\text{path in grid}) \; \P_{b_1}[\xi_L] \; \P_{b_2}[\xi_R]
     \end{align*}
     In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This proves the required equality.
     We obtain
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2)
         &= \sum_{\substack{\xi\in\paths{b} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] \\
         &= \sum_{\substack{\xi_L\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1}} \;\;
           \sum_{\substack{\xi_R\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
         \mathbb{P}[\xi_L]\cdot\mathbb{P}[\xi_R] \\
         &=
         \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)
         \; \cdot \;
         \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).
     \end{align*}
     The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.
     For the third equality, by the same reasoning we can decompose the paths
     \begin{align*}
         \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}
         &\equiv \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\
         &= \sum_{\substack{\xi_L\in\paths{b_1}\\\xi_L \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}
           \sum_{\substack{\xi_R\in\paths{b_2}\\\xi_R \in \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
         \mathbb{P}[\xi_L]\mathbb{P}[\xi_R] (|\xi_L| + |\xi_R|) \\
         &=
         \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1} \\
         &\quad +
         \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2} .
     \end{align*}
     Dividing by $\mathbb{P}_b(\mathrm{NZ}_{(j_1,j_2)},A_1,A_2)$ and using the first equality gives the desired result.
 \end{proof}
 	\bibliographystyle{alpha}
 	\bibliography{Resample.bib}

0 comments (0 inline, 0 general)