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

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

    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]

    \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_{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|}) \\

                &= \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_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_{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]

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

        &=

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

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

\end{definition}

New:

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

	Let $i\neq j\in [n]$, and let $A_1$ be any event that depends only on the sites $[i,j]$ (meaning the initialization and resamples) and similarly $A_2$ 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

	\begin{align*}

	\P^{(n)}(\mathrm{NZ}^{(i,j)}\cap A_1\cap A_2)

	&=

	\P^{[i,j]}(\mathrm{NZ}^{(i,j)}\cap A_1)

	\; \cdot \;

	\P^{[j,i]}(\mathrm{NZ}^{(i,j)}\cap A_2)/(1-p)^2 \\

	\P^{(n)}(A_1\cap A_2|\mathrm{NZ}^{(i,j)})

	&=

	\P^{[i,j]}(A_1|\mathrm{NZ}^{(i,j)})

	\; \cdot \;

	\P^{[j,i]}(A_2|\mathrm{NZ}^{(i,j)})

	\end{align*}

	up to any order in $p$.

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

\begin{lemma}\label{lemma:probIndepNew}

	$\forall n\in \mathbb{N}_+:\P^{[n]}(\Z{1})-\P^{[n+1]}(\Z{1}) = O(p^{n})$. (Should be true with $O(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+O(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]}([k]\in\mathcal{P}) \tag{the events are a partition}\\

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P}) + O(p^{n})\\

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

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

	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})/(1-p)+ O(p^{n}) \\	

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

	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ O(p^{n}) \\

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

	\end{align*}

\end{proof}

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

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

\end{corollary}

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

 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\mathcal{O}(p^{k})=\left(\P^{[k]}(\Z{1})\right)^2+\mathcal{O}(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})+\mathcal{O}(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})$$

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

 		+\mathcal{O}(p^{k})\\

 		&\overset{Lemma~\ref{lemma:eventindependenceNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

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

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

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

 		+\mathcal{O}(p^{k})\\

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

 		\P^{[\ell+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]}([r,k]\in\mathcal{P})/(1-p)^2

 		+\mathcal{O}(p^{k})\\

 		&\overset{Corrolary~\ref{cor:probIndepNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

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

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

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

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

 		+\mathcal{O}(p^{k})\\

 		&\overset{Lemma~\ref{lemma:eventindependenceNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

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

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

 		+\mathcal{O}(p^{k})\\

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

 		+\mathcal{O}(p^{k})\\

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

 		+\mathcal{O}(p^{k}).	

 		\end{align*}

 	\end{proof}

	\begin{theorem}

		$R^{(n)}-R^{(m)}=\mathcal{O}(p^{\min(n,m)})$.

	\end{theorem}

	\begin{proof}

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

		\begin{align*}

		R^{(n)} &=  \\

		&= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}t\cdot \P^{(n)}(v \text{ is resampled in }t\text{ times})\\

		&= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}t\cdot\P^{(n)}(v \text{ is resampled in }t\text{ times and }P\text{ is a patch})\\	

		&= \frac{1}{n}\sum_{P\text{ patch}}\E^{(n)}(\# \text{ resamples in }P|P\in \mathcal{P})\\			

		&= \sum_{s=1}^{n-1}\E^{(n)}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n})\tag{by translation symmetry}\\   		

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\P^{[s+1,n]}(\NZ{s+1}\cap\NZ{n})/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\   

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,n]}(\NZ{s+1})\right)^2/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\   

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,N]}(\NZ{s+1})\right)^2/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Corollary~\ref{cor:probIndepNew}}\\   			

		&= \sum_{s=1}^{n-1}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:eventindependenceNew}, Corollary~\ref{cor:probIndepNew}}\\   	

		&= \sum_{s=1}^{N}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}).

		\end{align*}

		Repeating the same calculation with $m$, and comparing the two expressions completes the proof.

	\end{proof} 	

Old:

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)$. These definitions are illustraded in Figure \ref{fig:lemmaillustration}.

	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{I'}(\Z{0}) = O(p^{I_{\max}-|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 \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^\infty_{I}(\Z{(0)})

		&=\sum_{k=1}^{\infty}\P^\infty(\Z{(0)}_k) \tag{the events are a partition}\\

        &=\sum_{k\in \mathbb{N}\setminus I}\P^\infty(\Z{(0)}_k) \tag{$\mathbb{\P^\infty}(A_k)=0$ for $k\in I$}\\

        &=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\

        &=\sum_{k\in I_{><}}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})

		\tag{$k<I_{\min}\Rightarrow \P^\infty_{I_{<k}}(\Z{(0)}_k)=0$}\\

        &=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})	

		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\

		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \left(\P^\infty_{I'_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}-k+1-|I_{>k}|})\right) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{by induction, since for $k>I_{\min}$ we have $|I_{<k}|<|I|$}\\

		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	

		\tag{as $\P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{k-|I'_{<k}|})$}\\

		&=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\

		&=\sum_{k\in\mathbb{N}\setminus I'}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\

		&=\P^\infty_{I'}(\Z{(0)}) +\mathcal{O}(p^{I_{\max}-|I'|})	\tag{analogously to the beginning}			

	\end{align*}

\end{proof}

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

	Suppose $I,J\subset\mathbb{N}_+$ are finite sets of vertices, and let $m=\min(\Delta(I,J))$.

	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{J}(\Z{0}) = O(p^{|[m]\cap I\cap J|})$.

\end{corollary}

	%The main insight that Lemma~\ref{lemma:probIndep} gives is that if we separate the slots to two halves, in order to see the cancellation of the contribution of the expected resamples on the right, we can simply pair up the left configurations by the particle filling the leftmost slot. And similarly for cancelling the left expectations we pair up right configurations based on the rightmost filling. 

	%Also this claim finally ``sees'' how many empty places are between slots. These properties make it possible to use this lemma to prove the sought linear bound. We show it for the infinite chain, but with a little care it should also translate to the cycle.

\begin{definition}[Connected patches]

	Let $\mathcal{P}\subset 2^{\mathbb{Z}}$ be a finite system of finite subsets of $\mathbb{Z}$. We say that the patch set of a resample sequence is $\mathcal{P}$,

	if the connected components of the vertices that have ever become $0$ are exactly the elements of $\mathcal{P}$. We denote by $A^{(\mathcal{P})}$ the event that the set of patches is $\mathcal{P}$. For a patch $P$ let $A^{(P)}=\bigcup_{\mathcal{P}:P\in \mathcal{P}}A^{(\mathcal{P})}$ denote the event that one of the patches is equal to $P$ but there can be other patches as well.

	As a shorthand we are going to use the notation $P\in \mathcal{P}$ for the event $A^{(P)}$.

\end{definition} 

\begin{definition}[Conditional expectations]

	Let $S\subset\mathbb{Z}$ be a finite slot configuration, and for $f\in\{0,1'\}^{|S|}$ let $I:=S(f)$ be the set of vertices filled with a particle (i.e. $1'$). 

	Then we define

	$$R_I:=\mathbb{E}[\#\{\text{resamplings when started from inital state }I\}],$$ 

	and similarly for a patch $P$ we define

	$$R^{(P)}_I:=\mathbb{E}[\#\{\text{resamplings inside }P\text{ when started from inital state }I\}|A^{(P)}].$$	

\end{definition} 

 	\begin{lemma}Suppose $I\subseteq [k]$, then on the infinite chain

		$$\P^\infty_I(\Z{1}\cap \Z{k})=\P^\infty_I(\Z{1})\P^\infty_I(\Z{k})+\mathcal{O}(p^{k-|I|}).$$

	\end{lemma}   

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

	$$\P^\infty_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1})\P^\infty_I(\NZ{k})+\mathcal{O}(p^{k-|I|}).$$

	\begin{proof}

		We proceed by induction on $|I|$. For $|I|=0$ the statement is trivial.

		Now observe that:

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

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

		Suppose we proved the statement for all $\ell< |I|$, then we proceed using induction similarly to the above (let us use the notation $>I<:=I\cap \overline{P_l}\cap \overline{P_r}$ for simplicity)

		\begin{align*}

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

		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_I(P_l,P_r\in\mathcal{P})

		+\sum_{P\text{ patch}\,:\,1,k\in P}\P^\infty_I(P\in\mathcal{P})\\

		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_I(P_l,P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{>I<}(\NZ{P_l^{\max}+1}\cap \NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{\text{induction}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{> I <}(\NZ{P_l^{\max}+1})\P^\infty_{> I <}(\NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Corrolary~\ref{cor:probIndep}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{I\setminus P_l}(\NZ{P_l^{\max}+1})\P^\infty_{I\setminus P_r}(\NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I}(P_l\in\mathcal{P})

		\P^\infty_{I}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&=\left(\sum_{P_l\text{ patch}\,:\,1\in P_l}\P^\infty_{I}(P_l\in\mathcal{P})\right)

		\left(\sum_{P_r\text{ patch}\,:\,k\in P_r}\P^\infty_{I}(P_r\in\mathcal{P})\right)

		+\mathcal{O}(p^{k-|I|})\\

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

		+\mathcal{O}(p^{k-|I|}).	

		\end{align*}

	\end{proof}

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

		Let $k>0$ and $d:=\lfloor\frac{k}{2}\rfloor$, then 

		\begin{align*}

		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

		=\left(\sum_{\underset{|S|<\infty}{S\subseteq \mathbb{N}_+}}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!\!2}

		+\mathcal{O}(p^{d}).

		\end{align*}

	\end{corollary}

	(Question: is the above is true with $d=k$?)

	\begin{proof}

		Let $[-d]:=\{k-d+1,\ldots, k\}$ and $[\pm d]:=[d]\cup [-d]$. By the above statement we know that

		\begin{align}\label{eq:intervalIndep}

		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

		=\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{k}).

		\end{align}

		Now suppose $s\in S\subseteq[k]$ such that $s\notin [\pm d]$, then 

		\begin{align*}

		&\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{k})\\

		&=\sum_{f_{\overline{s}}\in\{0,1'\}^{|S|-1}}\rho_{S\setminus\{s\}(f_{\overline{s}})} \left(p\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{k})-p\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{k})\right)\\

		&=\mathcal{O}(p^{d}). \tag{by Corollary~\ref{cor:probIndep}}

		\end{align*}

		Therefore we can see that 

		\begin{align*}

		\eqref{eq:intervalIndep}&=\sum_{S\subseteq [\pm d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{d})\\

		&=\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\sum_{S'\subseteq [d]}\sum_{f'\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\rho_{S'(f')}\P^\infty_{S'(f')}(\NZ{k})+\mathcal{O}(p^{d}) \tag{Corollary \ref{cor:probIndep}}\\