\end{align*}

    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 $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\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$:

    \begin{align*}

        \xi_1 &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots  \right) \\

        \xi_2 &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots  \right) \\

        \xi   &= \left( (z_1 + z_1', s_1', r_1'), (z_1+z_2', s_1, r_1), (z_2+z_2', s_2, r_2), (z_3+z_2', s_2', r_2'), \cdots \right)

    \end{align*}

    The probability of $\xi_1$, started from $b_1$, is given by

    \begin{align*}

        \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.

    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^{(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{1}{z_2 } \P(r_2 ) \;

        \frac{z_2'}{z_3+z_2'} \frac{1}{z_2'} \P(r_2')

        \cdots \tag{rewrite fractions}\\

        &=

        \frac{z_1'}{z_1+z_1'} \;

        \frac{z_1 }{z_1+z_2'} \;

        \frac{z_2 }{z_2+z_2'} \;

        \frac{z_2'}{z_3+z_2'}

        \cdots

        \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*}

        \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) \\

        &=

        \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1)

        \; \cdot \;

        \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.

\end{proof}

\begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNew}

	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}^{(v,w)}\cap A\cap B)

		=

		\P_{b_v=b_w=1}^{[v,w]}(\mathrm{NZ}^{(v,w)}\cap A)

		\; \cdot \;

		\P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B),

	\end{align*}

	and similarly

	\begin{align*}

		\P^{[n]}(\mathrm{NZ}^{(v)}\cap A\cap B)

		=

		\P_{b_v=1}^{[v]}(\mathrm{NZ}^{(v)}\cap A)

		\; \cdot \;

		\P^{[v,n]}(\mathrm{NZ}^{(v)}\cap B)

	\end{align*}

	where there is no longer a condition on the starting state.

\end{lemma}

\begin{proof}

    We start by relating the different Markov Chains.

    If $b$ is a starting state where all the zeroes are inside an interval $[v,w]$ (not on the boundary) then we can switch between the cycle and the finite chain:

    \begin{align*}

        \P^{(n)}_{b} (\NZ{v,w} \cap A) = \P^{[v,w]}_b (\NZ{v,w}\cap A) .

    \end{align*}

    If vertex $v$ and $w$ never become zero, then the zeroes never get outside of the interval $[v,w]$ and we can ignore the entire circle and only focus on the process within $[v,w]$.

    We can apply this to the result of Lemma \ref{lemma:eventindependence}, to get

    \begin{align*}

        \P^{(n)}_b(\mathrm{NZ}^{(v,w)} \cap A \cap B)

        &=

        \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)} \cap A)

        \; \cdot \;

        \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)} \cap B)

    \end{align*}

    Note that this also holds if $b$ has zeroes on the boundary (i.e. $b_v=0$ or $b_w=0$), because then both sides of the equations are zero.

    For the starting state we have the expression $\P^{(n)}(\start{b}) = (1-p)^{|b|} p^{n-|b|}$ so it splits into a product

    \begin{align*}

        \P^{(n)}(\start{b}) = \P^{[v,w]}(\start{b|_{[v+1,w-1]}}) \;\; \P^{[w,v]}(\start{b|_{[w,v]}})

    \end{align*}

    where we have to be careful to count the boudary only once.

    We now have

    \begin{align*}

		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)

        &= \sum_{b\in\{0,1\}^n} \P^{(n)}_b(\mathrm{NZ}^{(v,w)}\cap A\cap B) \; \P^{(n)}(\start{b}) \\

        &= \sum_{b\in\{0,1\}^n}

            \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)}\cap A)

            \P^{[v,w]}(\start{b|_{[v+1,w-1]}})

            \\ &\qquad\qquad\quad\cdot

            \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)}\cap B)

            \P^{[w,v]}(\start{b|_{[w,v]}}) \\

        &= \left( \sum_{\substack{b_1\in\{0,1\}^{[v,w]}\\ b_v=b_w=1}}

            \P^{[v,w]}_{b_1}(\mathrm{NZ}^{(v,w)}\cap A)

            \P^{[v,w]}(\start{b_1}) \right)

            \\ &\qquad \cdot

           \left( \sum_{b_2\in\{0,1\}^{[w,v]}}

            \P^{[w,v]}_{b_2}(\mathrm{NZ}^{(v,w)}\cap B)

            \P^{[w,v]}(\start{b_2}) \right) \\

        &=  \P^{[v,w]}_{b_v=b_w=1}(\mathrm{NZ}^{(v,w)}\cap A) \cdot

            \P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B)

    \end{align*}

    The second equality follows in a similar way.

\end{proof}

	\begin{definition}[Connected patches]

		Let $P$ be an interval $[a,b]$. We say that $P$ is a patch of a particular run of the process if $P$ is a maximal connected component of the vertices that have ever become $0$ before termination. We denote the set of patches of a run by $\mathcal{P}$. For a patch $P$ let $P\in \mathcal{P}$ denote the event that one of the patches is equal to $P$. 

		In other words

		\begin{align*}

		P\in\mathcal{P} := \NZ{a-1} \cap \Z{a} \cap \Z{a+1} \cap \cdots \cap \Z{b-1} \cap \Z{b} \cap \NZ{b+1} .

		\end{align*}

		(In the extreme case when $P$ covers the whole cycle $[n]$, then instead $P\in\mathcal{P}:= \bigcap_{v\in[n]}\Z{v}$.)

	\end{definition} 

	We are often going to use the observation that we can partition the event $\Z{v}$ using patches:

	\begin{align*}

	\Z{v} = \dot\bigcup_{P\text{ patch } : v\in P} (P\in\mathcal{P})

	\end{align*}

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:probIndepNew}

	$\forall n\in \mathbb{N}_+:\P^{[n]}(\Z{1})-\P^{[n+1]}(\Z{1}) = \bigO{p^{n}}$. (Should be true with $\bigO{p^{n+1}}$ as well.)

\end{lemma}

\begin{proof}

	The proof uses induction on $n$. For $n=1$ the statement is easy, since $\P^{[1]}(\Z{1})=p$ and $\P^{[2]}(\Z{1})=p+p^2+\bigO{p^{3}}$.

	Induction step: suppose we proved the claim for $n-1$, then

	\begin{align*}

	\P^{[n+1]}(\Z{1})

	&=\sum_{k=1}^{n+1}\P^{[n+1]}([k]\in\mathcal{P}) \tag{the events form a partition}\\

	&=\sum_{k=1}^{n-1}\P^{[n+1]}([k]\in\mathcal{P}) + \bigO{p^{n}}\tag*{$\left(\P^{[n+1]}([k]\in\mathcal{P})=O(p^{k})\right)$}\\	

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k+1]}(\NZ{1})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \left(\P^{[n-k]}(\NZ{1})+\bigO{p^{n-k}}\right)+ \bigO{p^{n}} \tag{by induction} \\	

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})+ \bigO{p^{n}} \tag*{$\left(\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\	

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag*{$\left(\P^{[n]}([n]\in\mathcal{P})=\bigO{p^{n}}\right)$}\\	

	&=\P^{[n]}(\Z{1})	+ \bigO{p^{n}} 

	\end{align*}

\end{proof}

\begin{corollary}\label{cor:probIndepNew}

	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = \bigO{p^{\min(n,m)}}$. (Should be true with $\bigO{p^{\min(n,m)+1}}$ too.)

\end{corollary}

	The intuition of the following lemma is simmilar to the previous. The events on the two sides should be independent unless an interaction chain is forming, implying that every vertex gets resampled to $0$ at least once.

 	\begin{lemma}\label{lemma:independenetSidesNew}	

 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\bigO{p^{k}}=\left(\P^{[k]}(\Z{1})\right)^2+\bigO{p^{k}}.$$

 	\end{lemma}   

 	Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:

 	$$\P^{[k]}(\NZ{1}\cap \NZ{k})=\P^{[k]}(\NZ{1})\P^{[k]}(\NZ{k})+\bigO{p^{k}}.$$

 	\begin{proof}

 		We proceed by induction on $k$. For $k=1,2$ the statement is trivial.

 		Now observe that:

 		$$\P^{[k]}(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^{[k]}(P\in\mathcal{P})$$

 		$$\P^{[k]}(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^{[k]}(P\in\mathcal{P})$$

 		Suppose we proved the statement up to $k-1$, then we proceed using induction similarly to the above

 		\begin{align*}

 		&\P^{[k]}(\Z{1}\cap \Z{k})=\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\P^{[k]}([k]\in\mathcal{P})\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\	

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\P^{[\ell+1,r-1]}(\NZ{\ell+1}\cap \NZ{r-1})

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,r-1]}(\NZ{\ell+1})

		\P^{[\ell+1,r-1]}(\NZ{r-1})\right)

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by induction}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,k]}(\NZ{\ell+1})

 		\P^{[1,r-1]}_{b_{r-1}=1}(\NZ{r-1})\right)

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Corrolary~\ref{cor:probIndepNew}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[k]}([\ell]\in\mathcal{P})

 		\P^{[k]}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

 		&=\left(\sum_{\ell\in [k]}\P^{[k]}([\ell]\in\mathcal{P})\right)

 		\left(\sum_{r\in [k]}\P^{[k]}([r,k]\in\mathcal{P})\right)

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([\ell]\in\mathcal{P})=\bigO{p^{\ell}}\right)$}\\	

 		&=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})

 		+\bigO{p^{k}}.	

 		\end{align*}

 	\end{proof}

	Again the intuition of the final theorem is simmilar to the previous lemmas. A site can only realise the length of the cycle after an interaction chain was formed around the cycle, implying that every vertex was resampled to $0$ at least once.

	\begin{theorem} $R^{(n)}=\E^{[-m,m]}(\Res{0})+\bigO{p^{n}}$ for all $m\geq n \geq 3$, thus

		$R^{(n)}-R^{(m)}=\bigO{p^{n}}$.

	\end{theorem}

	\begin{proof} In the proof we identify the sites of the $n$-cycle with the$\mod n$ remainder classes.

		\vskip-3mm

		\begin{align*}

			R^{(n)}

			&= \E^{(n)}(\Res{0}) \tag{by translation invariance}\\

			&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{0}\!\geq\! k) \\		

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n+1}{v,w\in [n]}}\P^{(n)}(\Res{0}\!\geq\! k\,\&\, \underset{P_{v,w}:=}{\underbrace{[-v\!+\!1,w\!-\!1]}}\in\mathcal{P}) \tag{partition}\\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n}{v,w\in [n]}}\P^{(n)}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) +\bigO{p^{n}}\\[-1mm]

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) \P^{[w,n-v]}(\NZ{w,n-v}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P})  \left(\left(\P^{[w,n-v]}(\NZ{w})\right)^{\!\!2}\!+\!\bigO{p^{n-v-w+1}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P})  \left(\P^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\NZ{w})\!+\!\bigO{p^{n-v-w+1}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\	

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) \P^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\NZ{w}) +\bigO{p^{n}} \tag{$|P_{v,w}|=v+w-1$}\\

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n}{v,w\in [n]}}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{\underset{|P|<n}{P\text{ patch}:0\in P}}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:0\in P}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\

			&= \E^{[-m,m]}(\Res{0})+\bigO{p^{n}}.\\[-3mm]										

		\end{align*}  

		\noindent Repeating the same argument with $m$ and comparing the results completes the proof.

	\end{proof} 	

\begin{comment}

		Let $N\geq \max(2n,2m)$, then

		\begin{align*}

		R^{(n)}

		&= \E^{(n)}(\Res{1}) \tag{by translation invariance}\\

		&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{1}\geq k) \\

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r-1}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P}) \tag{partition}\\

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P})  +\bigO{p^{n}} \\	

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{[l,r]}_{b_{\ell}=b_{r}=1}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P}) \P^{[r,\ell]}(\NZ{\ell,r}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\				

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{(n)}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \tag{partition}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{(n)}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \P^{[\overline{P}]}(\NZ{\partial P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \left(\left(\P^{[|\overline{P}|]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \left(\left(\P^{[N]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Corollary~\ref{cor:probIndepNew}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[-N,N]}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{[-N,N]}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

		&= \E^{[-N,N]}(\Res{1})+\bigO{p^{n}}.

		\end{align*}	

\end{comment}			

~

Questions:

\begin{itemize}

	\item Can we generalise the proof to other translationally invariant spaces, like the torus?

	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?

	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

\end{itemize} 

	%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.

\newpage

\section{General graphs proof}

We consider the following generalization of the Markov Chain.

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain and $\E^G$ to denote expectation values.

\begin{definition}[Events and notation] \label{def:events}

    Let $G=(V,E)$ be a graph. Let $S\subseteq V$ be any subset of vertices.

    \begin{itemize}

        \item Define $\Z{S}$ as the event that \emph{all} vertices in $S$ become zero at any point in time before the Markov Chain terminates.

        \item Define $\NZ{S}$ as the event that \emph{none} of the vertices in $S$ become zero at any point in time before the Markov Chain terminates.

        \item Define for any event $A$:

            \begin{align*}

                \P^{G}_S(A) &= \P^{G}(A \mid \text{All vertices in $S$ get initialized to }1)

            \end{align*}

            The condition does not apply to subsequent resamplings of vertices in $S$, it only specifies the initial assignment.

        \item Define $G\setminus S$ as the graph obtained by removing from $G$ all vertices in $S$ and edges adjacent to $S$.

        \item Define the $d$-neighbourhood $B^G(S;d)$ of $S$ as the set of vertices reachable from $S$ within $d$ steps.

        \item Define the boundary $\overline{\partial} S$ of $S$ as the set of vertices adjacent to $S$, excluding $S$ itself. In other words $\overline{\partial} S = B(S;1) \setminus S$.

    \end{itemize}

\end{definition}

The following Lemma says that if a set $S$ splits the graph in two, then those two parts become independent if the vertices in $S$ never become zero.

\begin{center}

    \includegraphics[scale=0.8]{diagram_splittinglemma.pdf}

\end{center}

\begin{lemma}[Splitting lemma] \label{lemma:splitting}

    Let $G=(V,E)$ be a graph. Let $S,X,Y\subseteq V$ be a partition of the vertices, such that $X$ and $Y$ are disconnected in the graph $G\setminus S$. Furthermore, let $A^X$ and $A^Y$ be any events that depends only on the sites in $X$ and $Y$ respectively. Then we have

    \begin{align*}

        \P^{G}_S(\NZ{S} \cap A^X \cap A^Y)

        &=

        \P^{G\setminus Y}_S(\NZ{S} \cap A^X)

        \; \cdot \;

        \P^{G\setminus X}_S(\NZ{S} \cap A^Y)

    \end{align*}

\end{lemma}

%\newcommand{\initone}[1]{\textsc{InitOne}_#1}

\begin{proof}

    We are considering three different Markov Chains, and the events $\NZ{S}$ in the different parts of the equation are events on different probability spaces. We will keep using the same notation for these events because it should be clear from the context which Markov Chain is being considered. We will consider paths (i.e. resampling sequences) and we will use a superscript to denote to which Markov Chain a path belongs. Let $\xi^G \in \NZ{S}$ be a path of the Markov Chain associated to the resample process on the graph $G$, that satisfies the event $\NZ{S}$. 

    From $\xi^G$ we will now construct paths $\xi^{G\setminus Y} \in \NZ{S}$ and $\xi^{G \setminus X} \in \NZ{S}$ of the other Markov Chains satisfying the corresponding events on those Markov Chains.

    Let us write the path $\xi^G$ as an initialization and a sequence of resamplings:

    \begin{align*}

        \xi^G=\left( (\text{initialize to }b), (z_1, v_1, r_1), (z_2, v_2, r_2), ..., (z_{|\xi^G|}, v_{|\xi^G|}, r_{|\xi^G|}) \right)

    \end{align*}

    where $b\in\{0,1\}^V$ is the initial state, $1 \leq z_i \leq |V|$ denotes the number of zeroes in the state before the $i$th step, $v_i\in V$ denotes the site that was resampled and $r_i\in \{0,1\}^{d(v_i)+1}$ is the result of the resampled bits. Here $d(v_i)$ is the degree of vertex $v_i$. By definition of the resample process, we have

    \begin{align*}

        \P^{G}_S(\xi^G) &=

        \P(\text{initialize }b \mid \text{initialize $S$ to }1)

        \P(\text{pick }v_1 \mid z_1) \P(r_1)

        \P(\text{pick }v_2 \mid z_2) \P(r_2) \cdots \\ 

        &= \frac{(1-p)^{|b|} p^{|V|-|b|}}{(1-p)^{|S|}} \cdot

        \frac{1}{z_1} \P(r_1) \cdot

        \frac{1}{z_2} \P(r_2) \cdots

        \frac{1}{z_{|\xi^G|}} \P(r_{|\xi^G|}) .

    \end{align*}

    Let $b|_{G\setminus X}$ be the restriction of $b$ to $G\setminus X$ and similar for $b|_{G\setminus Y}$.

    To construct $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$, start with $\xi^{G\setminus Y} = \left( (\text{initialize }b|_{G\setminus Y}) \right)$ and $\xi^{G\setminus X} = \left( (\text{initialize }b|_{G\setminus X}) \right)$. For each step $(z_i,v_i,r_i)$ in $\xi^G$ do the following: if $v_i \in X$ then append $(z^{X}_i,v_i,r_i)$ to $\xi^{G\setminus Y}$ and if $v_i \in Y$ then append $(z^{Y}_i,v_i,r_i)$ to $\xi^{G\setminus X}$.

    Here $z^{X}_i$ is the number of zeroes that were in $X$ and $z^{Y}_i$ is the number of zeroes in $Y$. We have $z_i = z^{X}_i + z^{Y}_i$ because $\xi^G\in\NZ{S}$ so there can not be any zero in $S$; they all have to be in $X$ or $Y$. Furthermore, this also makes sure that we always have either $v_i\in X$ or $v_i\in Y$ since only vertices that are zero can be chosen to resample.

    Now $\xi^{G\setminus Y}$ is a valid path of the Markov Chain associated to the graph $G\setminus Y$ (i.e. with vertices $X\cup S$), because in the original path $\xi^G$, all zeroes in $X$ have been resampled by resamplings in $X$. There can not be a vertex $v\in Y$ such that the resampling of $v$ changed a vertex in $X$, since $X$ and $Y$ are only connected through $S$ and we know $\xi^G\in\NZ{S}$.

    Vice versa, any two paths $\xi^{G\setminus Y}\in\NZ{S}$ and $\xi^{G\setminus X}\in\NZ{S}$ also induce a path $\xi^G\in\NZ{S}$ by simply interleaving the resampling positions. Note that $\xi^{G\setminus Y},\xi^{G\setminus X}$ actually induce $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ paths $\xi^G$ because of the possible orderings of interleaving the resamplings in $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$.

    For a fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ we will now show the following:

    \begin{align*}

        \sum_{\substack{\xi^G\in\NZ{S} \text{ s.t.}\\ \xi^G \text{ decomposes into } \xi^{G\setminus Y},\xi^{G\setminus X} }} \P^{G}_S(\xi^G) &=

        \sum_{\text{interleavings of }\xi^{G\setminus Y},\xi^{G\setminus X}} \P(\text{interleaving}) \cdot \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) \\

        &= \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) 

    \end{align*}

    where both sums are over $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ terms.

    This is best explained by an example. Lets consider the following fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ and an example interleaving where we choose vertices from $Y,X,X,Y,\cdots$:

    \begin{align*}

        \xi^{G\setminus Y} &= \left( (\text{initialize to }b^X\;1^S),

        (z^X_1, v^X_1, r^X_1),

        (z^X_2, v^X_2, r^X_2),

        (z^X_3, v^X_3, r^X_3),

        (z^X_4, v^X_4, r^X_4),

        \cdots  \right) \\

        \xi^{G\setminus X} &= \left( (\text{initialize to }1^S\;b^Y),

        (z^Y_1, v^Y_1, r^Y_1),

        (z^Y_2, v^Y_2, r^Y_2),

        (z^Y_3, v^Y_3, r^Y_3),

        (z^Y_4, v^Y_4, r^Y_4),

        \cdots  \right) \\

        \xi^G             &= \big( (\text{initialize to }b^X \; 1^S \; b^Y),

        (z^X_1+z^Y_1, v^Y_1, r^Y_1),

        (z^X_1+z^Y_2, v^X_1, r^X_1), \\

        &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad

        (z^X_2+z^Y_2, v^X_2, r^X_2),

        (z^X_3+z^Y_2, v^Y_2, r^Y_2),

        \cdots \big)

    \end{align*}

    Here $b^X\in \{0,1\}^{X}$ and $b^Y\in\{0,1\}^Y$. Since we condition on the event that $S$ is initialized to ones, we know the initial state is of the form $b^X\;1^S$ in $\xi^{G\setminus Y}$. Similarly, since these paths satisfy the $\NZ{S}$ event, we know all the vertices $v_i$ resampled in $\xi^{G\setminus Y}$ are vertices in $X$, and the resampled bits $r_i$ are bits corresponding to vertices in $X$.

    In the newly constructed path $\xi^G$ the number of zeroes is the number of zeroes in $X$ and $Y$ together, so this starts as $z^X_1 + z^Y_1$. Then in this example, after the first step the number of zeroes is $z^X_1+z^Y_2$ since a step of $\xi^{G\setminus X}$ was done (so a vertex in $Y$ was resampled).

    The probability of $\xi^{G\setminus Y}$ is given by

    \begin{align*}

        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) &=

        \P(\text{initialize }b^X\;1^S \mid \text{initialize $S$ to }1)

        \P(\text{pick }v^X_1 \mid z^X_1) \P(r^X_1)

        \P(\text{pick }v^X_2 \mid z^X_2) \P(r^X_2) \cdots \\ 

        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot

        \frac{1}{z^X_1} \P(r^X_1) \cdot

        \frac{1}{z^X_2} \P(r^X_2) \cdots

        \frac{1}{z^X_{|\xi^{G\setminus Y}|}} \P(r^X_{|\xi^{G\setminus Y}|}) .

    \end{align*}

    and similar for $\xi^{G\setminus X}$.

    Instead of choosing a step in $Y,X,X,Y,\cdots$ we could have chosen other orderings. The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $Y,X,X,Y$ in the example above.

    \begin{center}

    \end{center}

    For the labels shown within the grid, define $p_{ij} = \frac{z^X_i}{z^X_i + z^Y_j}$.

    The probability of this particular interleaving $\xi^G$ is given by

    \begin{align*}

        \P^{G}_S(\xi^{G})

        &= (1-p)^{|b^X\; b^Y|} p^{|X\cup Y|-|b^X\;b^Y|} \quad

        \frac{1}{z^X_1+z^Y_1} \P(r^Y_1) \cdot

        \frac{1}{z^X_1+z^Y_2} \P(r^X_1) \cdots \\

        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot (1-p)^{|b^Y|} p^{|Y|-|b^Y|} \\

        &\qquad \cdot

        \frac{z^Y_1}{z^X_1+z^Y_1} \frac{1}{z^Y_1} \P(r^Y_1) \;

        \frac{z^X_1}{z^X_1+z^Y_2} \frac{1}{z^X_1} \P(r^X_1) \;

        \frac{z^X_2}{z^X_2+z^Y_2} \frac{1}{z^X_2} \P(r^X_2)

        \cdots \tag{rewrite fractions}\\

        &=

        \frac{z^Y_1}{z^X_1+z^Y_1} 

        \frac{z^X_1}{z^X_1+z^Y_2} 

        \frac{z^X_2}{z^X_2+z^Y_2} 

        \cdots

        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

        \tag{definition} \\

        &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \cdots \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

        \tag{definition of $p_{i,j}$} \\

        &= \P(\text{path in grid}) \; \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

    \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*}

        \P^{G}_S(\NZ{S} \cap A^X \cap A^Y)

        &= \sum_{\xi^G \in \NZ{S}\cap A^X \cap A^Y} \P^{G}_S(\xi^G) \\

        &= \sum_{\xi^{G\setminus Y} \in \NZ{S}\cap A^X}

           \sum_{\xi^{G\setminus X} \in \NZ{S}\cap A^Y}

            \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot

            \P^{G\setminus X}_S(\xi^{G\setminus X}) \\

        &= \P^{G\setminus Y}_S(\NZ{S} \cap A^X) \; \cdot \; \P^{G\setminus X}_S(\NZ{S} \cap A^Y)

    \end{align*}

\end{proof}

\todo{rewrite from here}

\begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNewGen}

	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}^{(v,w)}\cap A\cap B)

		=

		\P_{b_v=b_w=1}^{[v,w]}(\mathrm{NZ}^{(v,w)}\cap A)

		\; \cdot \;

		\P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B),

	\end{align*}

	and similarly

	\begin{align*}

		\P^{[n]}(\mathrm{NZ}^{(v)}\cap A\cap B)

		=

		\P_{b_v=1}^{[v]}(\mathrm{NZ}^{(v)}\cap A)

		\; \cdot \;

		\P^{[v,n]}(\mathrm{NZ}^{(v)}\cap B)

	\end{align*}

	where there is no longer a condition on the starting state.

\end{lemma}

\begin{proof}

    We start by relating the different Markov Chains.

    If $b$ is a starting state where all the zeroes are inside an interval $[v,w]$ (not on the boundary) then we can switch between the cycle and the finite chain:

    \begin{align*}

        \P^{(n)}_{b} (\NZ{v,w} \cap A) = \P^{[v,w]}_b (\NZ{v,w}\cap A) .

    \end{align*}

    If vertex $v$ and $w$ never become zero, then the zeroes never get outside of the interval $[v,w]$ and we can ignore the entire circle and only focus on the process within $[v,w]$.

    We can apply this to the result of Lemma \ref{lemma:splitting}, to get

    \begin{align*}

        \P^{(n)}_b(\mathrm{NZ}^{(v,w)} \cap A \cap B)

        &=

        \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)} \cap A)

        \; \cdot \;

        \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)} \cap B)

    \end{align*}

    Note that this also holds if $b$ has zeroes on the boundary (i.e. $b_v=0$ or $b_w=0$), because then both sides of the equations are zero.

    For the starting state we have the expression $\P^{(n)}(\start{b}) = (1-p)^{|b|} p^{n-|b|}$ so it splits into a product

    \begin{align*}

        \P^{(n)}(\start{b}) = \P^{[v,w]}(\start{b|_{[v+1,w-1]}}) \;\; \P^{[w,v]}(\start{b|_{[w,v]}})

    \end{align*}

    where we have to be careful to count the boudary only once.

    We now have

    \begin{align*}

		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)

        &= \sum_{b\in\{0,1\}^n} \P^{(n)}_b(\mathrm{NZ}^{(v,w)}\cap A\cap B) \; \P^{(n)}(\start{b}) \\

        &= \sum_{b\in\{0,1\}^n}

            \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)}\cap A)

            \P^{[v,w]}(\start{b|_{[v+1,w-1]}})

            \\ &\qquad\qquad\quad\cdot

            \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)}\cap B)

            \P^{[w,v]}(\start{b|_{[w,v]}}) \\

        &= \left( \sum_{\substack{b_1\in\{0,1\}^{[v,w]}\\ b_v=b_w=1}}

            \P^{[v,w]}_{b_1}(\mathrm{NZ}^{(v,w)}\cap A)

            \P^{[v,w]}(\start{b_1}) \right)

            \\ &\qquad \cdot

           \left( \sum_{b_2\in\{0,1\}^{[w,v]}}

            \P^{[w,v]}_{b_2}(\mathrm{NZ}^{(v,w)}\cap B)

            \P^{[w,v]}(\start{b_2}) \right) \\

        &=  \P^{[v,w]}_{b_v=b_w=1}(\mathrm{NZ}^{(v,w)}\cap A) \cdot

            \P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B)

    \end{align*}

    The second equality follows in a similar way.

\end{proof}

	\begin{definition}[Connected patches]

		Let $P\subseteq V$ be a connected component of $G$. We say that $P$ is a patch of a particular run of the process if $P$ is a maximal connected component of the vertices that have ever become $0$ before termination. We denote the set of patches of a run by $\mathcal{P}$. For a patch $P$ let $\patch{P}$ denote the event that one of the patches is equal to $P$. 

		In other words

		\begin{align*}

		\patch{P} := \NZ{\overline{\partial}P} \cap \Z{P}.

		\end{align*}

		For a set of patches $\mathcal{P}$ 	

		\begin{align*}

			\mathcal{P}'\in \mathcal{P} := \bigcup_{P\in \mathcal{P}'}\NZ{\overline{\partial}P} \cap \Z{P}.

		\end{align*}

	\end{definition} 

	We are often going to use the observation that we can partition the event $\Z{v}$ using patches:

	\begin{align*}

	\Z{v} = \dot\bigcup_{P\text{ patch } : v\in P} (P\in\mathcal{P})

	\end{align*}

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:probIndepNewGen}

	$\forall n\in \mathbb{N}_+:\P^{[n]}(\Z{1})-\P^{[n+1]}(\Z{1}) = \bigO{p^{n}}$. (Should be true with $\bigO{p^{n+1}}$ as well.)

\end{lemma}

\begin{proof}

	The proof uses induction on $n$. For $n=1$ the statement is easy, since $\P^{[1]}(\Z{1})=p$ and $\P^{[2]}(\Z{1})=p+p^2+\bigO{p^{3}}$.

	Induction step: suppose we proved the claim for $n-1$, then

	\begin{align*}

	\P^{[n+1]}(\Z{1})

	&=\sum_{k=1}^{n+1}\P^{[n+1]}([k]\in\mathcal{P}) \tag{the events form a partition}\\

	&=\sum_{k=1}^{n-1}\P^{[n+1]}([k]\in\mathcal{P}) + \bigO{p^{n}}\tag*{$\left(\P^{[n+1]}([k]\in\mathcal{P})=O(p^{k})\right)$}\\	

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k+1]}(\NZ{1})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNewGen}}\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \left(\P^{[n-k]}(\NZ{1})+\bigO{p^{n-k}}\right)+ \bigO{p^{n}} \tag{by induction} \\	

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})+ \bigO{p^{n}} \tag*{$\left(\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\	

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNewGen}}\\

	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag*{$\left(\P^{[n]}([n]\in\mathcal{P})=\bigO{p^{n}}\right)$}\\	

	&=\P^{[n]}(\Z{1})	+ \bigO{p^{n}} 

	\end{align*}

\end{proof}

\begin{corollary}\label{cor:probIndepNewGen}

	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = \bigO{p^{\min(n,m)}}$. (Should be true with $\bigO{p^{\min(n,m)+1}}$ too.)

\end{corollary}

	The intuition of the following lemma is simmilar to the previous. The events on the two sides should be independent unless an interaction chain is forming, implying that every vertex gets resampled to $0$ at least once.

 	\begin{lemma}\label{lemma:independenetSidesNewGen}	

 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\bigO{p^{k}}=\left(\P^{[k]}(\Z{1})\right)^2+\bigO{p^{k}}.$$

 	\end{lemma}   

 	Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:

 	$$\P^{[k]}(\NZ{1}\cap \NZ{k})=\P^{[k]}(\NZ{1})\P^{[k]}(\NZ{k})+\bigO{p^{k}}.$$

 	\begin{proof}

 		We proceed by induction on $k$. For $k=1,2$ the statement is trivial.

 		Now observe that:

 		$$\P^{[k]}(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^{[k]}(P\in\mathcal{P})$$

 		$$\P^{[k]}(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^{[k]}(P\in\mathcal{P})$$

 		Suppose we proved the statement up to $k-1$, then we proceed using induction similarly to the above

 		\begin{align*}

 		&\P^{[k]}(\Z{1}\cap \Z{k})=\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\P^{[k]}([k]\in\mathcal{P})\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\	

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\P^{[\ell+1,r-1]}(\NZ{\ell+1}\cap \NZ{r-1})

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,r-1]}(\NZ{\ell+1})

		\P^{[\ell+1,r-1]}(\NZ{r-1})\right)

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by induction}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,k]}(\NZ{\ell+1})

 		\P^{[1,r-1]}_{b_{r-1}=1}(\NZ{r-1})\right)

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Corrolary~\ref{cor:probIndepNewGen}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[k]}([\ell]\in\mathcal{P})

 		\P^{[k]}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

 		&=\left(\sum_{\ell\in [k]}\P^{[k]}([\ell]\in\mathcal{P})\right)

 		\left(\sum_{r\in [k]}\P^{[k]}([r,k]\in\mathcal{P})\right)

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([\ell]\in\mathcal{P})=\bigO{p^{\ell}}\right)$}\\	

 		&=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})

 		+\bigO{p^{k}}.	

 		\end{align*}

 	\end{proof}

	Again the intuition of the final theorem is simmilar to the previous lemmas. A site can only realise the length of the cycle after an interaction chain was formed around the cycle, implying that every vertex was resampled to $0$ at least once.

	\begin{theorem} $R^{(n)}=\E^{[-m,m]}(\Res{0})+\bigO{p^{n}}$ for all $m\geq n \geq 3$, thus

		$R^{(n)}-R^{(m)}=\bigO{p^{n}}$.

	\end{theorem}

	\begin{proof} In the proof we identify the sites of the $n$-cycle with the$\mod n$ remainder classes.

		\vskip-3mm

		\begin{align*}

			R^{(n)}

			&= \E^{(n)}(\Res{0}) \tag{by translation invariance}\\

			&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{0}\!\geq\! k) \\		

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n+1}{v,w\in [n]}}\P^{(n)}(\Res{0}\!\geq\! k\,\&\, \underset{P_{v,w}:=}{\underbrace{[-v\!+\!1,w\!-\!1]}}\in\mathcal{P}) \tag{partition}\\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n}{v,w\in [n]}}\P^{(n)}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) +\bigO{p^{n}}\\[-1mm]

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) \P^{[w,n-v]}(\NZ{w,n-v}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P})  \left(\left(\P^{[w,n-v]}(\NZ{w})\right)^{\!\!2}\!+\!\bigO{p^{n-v-w+1}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNewGen}}\\

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P})  \left(\P^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\NZ{w})\!+\!\bigO{p^{n-v-w+1}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNewGen}}\\	

			&= \sum_{k=1}^{\infty}\smash{\sum_{\underset{v+w\leq n}{v,w\in [n]}}}\P^{[-v,w]}_{b_{-v}=b_{w}=1}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) \P^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\NZ{w}) +\bigO{p^{n}} \tag{$|P_{v,w}|=v+w-1$}\\

			&= \sum_{k=1}^{\infty}\sum_{\underset{v+w\leq n}{v,w\in [n]}}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{\underset{|P|<n}{P\text{ patch}:0\in P}}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\[-1mm]

			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:0\in P}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\

			&= \E^{[-m,m]}(\Res{0})+\bigO{p^{n}}.\\[-3mm]										

		\end{align*}  

		\noindent Repeating the same argument with $m$ and comparing the results completes the proof.

	\end{proof} 	

\begin{comment}

		Let $N\geq \max(2n,2m)$, then

		\begin{align*}

		R^{(n)}

		&= \E^{(n)}(\Res{1}) \tag{by translation invariance}\\

		&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{1}\geq k) \\

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r-1}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P}) \tag{partition}\\

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P})  +\bigO{p^{n}} \\	

		%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{[l,r]}_{b_{\ell}=b_{r}=1}(\Res{1}\geq k\,\&\, [\ell+1,r-1]\in\mathcal{P}) \P^{[r,\ell]}(\NZ{\ell,r}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\				

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{(n)}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \tag{partition}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{(n)}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \P^{[\overline{P}]}(\NZ{\partial P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \left(\left(\P^{[|\overline{P}|]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNewGen}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) \left(\left(\P^{[N]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Corollary~\ref{cor:probIndepNewGen}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[-N,N]}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

		&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{[-N,N]}(\Res{1}\geq k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\

		&= \E^{[-N,N]}(\Res{1})+\bigO{p^{n}}.

		\end{align*}	

\end{comment}			

~

Questions:

\begin{itemize}

	\item Can we prove some upper bound of the coefficients in the difference, other than they are zero for small powers?

	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?

\end{itemize} 

\newpage

\section{Characterisation of $p_c$}

\textbf{Conjecture} for a fixed $p\in [0,1]$ the following are equivalent:

\begin{enumerate}

	\item $\lim_{n\to\infty}\P^{[-n,n]}_{\overline{\{0\}}}(\Z{\{n\}})>0$

	\item $\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Not reaching the all 1 state})>0$

	\item $\P^{[-\infty,\infty]}(\NZ{\{0\}})>0$

	\item $\P^{[0,\infty]}(\NZ{\{0\}})>0$

	\item $\lim_{n\to\infty}\P^{[0,n]}(\NZ{\{0\}})>0$		

	\item $\exists c,\lambda>0:\P^{[-\infty,\infty]}(\Z{[k]})<ce^{-\lambda k}$

	\item $\exists c,\lambda>0:\mathrm{Cov}^{[-\infty,\infty]}(A,B)<ce^{-\lambda d(A,B)}$

	\item $\exists c,\lambda>0\,\forall n\in\mathbb{N}:\mathrm{Cov}^{[n]}(A,B)<ce^{-\lambda d(A,B)}$	

	\item $R^{(\infty)}<\infty$

\end{enumerate}

\begin{proof}

	$1\Leftrightarrow 2:$

	\begin{align*}

		\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Not reaching the all 1 state})>0

		&=\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Resampling arbitrary far away})>0\\

		&=\P^{[-\infty,\infty]}_{\overline{\{0\}}}\left(\bigcap_{n=1}^{\infty}\Z{\{-n\}}\cup\Z{\{n\}}\right)>0\\

		&=\lim_{n\to\infty}\P^{[-\infty,\infty]}(\Z{\{-n\}}_{\overline{\{0\}}}\cup\Z{\{n\}})>0\\

		&=\lim_{n\to\infty}\P^{[-n,n]}_{\overline{\{0\}}}(\Z{\{-n\}}\cup\Z{\{n\}})>0

	\end{align*}

\end{proof}

\newpage

\section{Quasiprobability method}

Let us first introduce notation for paths of the Markov Chain

\begin{definition}[Paths]

	We define a \emph{path} of the Markov Chain as a sequence of states and resampling choices $\xi=((b_0,r_0),(b_1,r_1),...,(b_k,r_k)) \in (\{0,1\}^n\times[n])^k$ indicating that at time $t$ Markov Chain was in state $b_t\in\{0,1\}^n$ and then resampled site $r_t$. We denote by $|\xi|$ the length $k$ of such a path, i.e. the number of resamples that happened, and by $\mathbb{P}[\xi]$ the probability associated to this path.

	We denote by $\paths{b}$ the set of all valid paths $\xi$ that start in state $b$ and end in state $\mathbf{1} := 1^n$.

\end{definition}

We can write the expected number of resamplings per site $R^{(n)}(p)$ as

\begin{align}

R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1\}^{n}} \rho_b \; R_b(p) \label{eq:originalsum} ,

\end{align}

where $R_b(p)$ is the expected number of resamplings when starting from configuration $b$

\begin{align*}

R_b(p) &= \sum_{\xi \in \paths{b}} \mathbb{P}[\xi] \cdot |\xi| .

\end{align*}

We consider $R^{(n)}(p)$ as a power series in $p$ and show that many terms in (\ref{eq:originalsum}) cancel out if we only consider the series up to some finite order $p^k$. The main idea is that if a path samples a $0$ then $\mathbb{P}[\xi]$ gains a factor $p$ so paths that contribute to $p^k$ can't be arbitrarily long.\\

To see this, we split the sum in (\ref{eq:originalsum}) into parts that will later cancel out. The initial probabilities $\rho_b$ contain a factor $p$ for every $0$ and a factor $(1-p)$ for every $1$. When expanding this product of $p$s and $(1-p)$s, we see that the $1$s contribute a factor $1$ and a factor $(-p)$ and the $0$s only give a factor $p$. We want to expand this product explicitly and therefore we no longer consider bitstrings $b\in\{0,1\}^n$ but bitstrings $b\in\{0,1,1'\}^n$. We view this as follows: every site can have one of $\{0,1,1'\}$ with `probabilities' $p$, $1$ and $-p$ respectively. A configuration $b=101'1'101'$ now has probability $\rho_{b} = 1\cdot p\cdot(-p)\cdot(-p)\cdot 1\cdot p\cdot(-p) = -p^5$ in the starting state $\rho$. It should not be hard to see that we have

\begin{align*}

R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_{b} \; R_{\bar{b}}(p) ,

\end{align*}

where $\bar{b}$ is the bitstring obtained by changing every $1'$ in it back to a $1$. It is simply the same sum as (\ref{eq:originalsum}) but now every factor $(1-p)$ is explicitly split into $1$ and $(-p)$.