~

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}

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_{I}(Z^{(0)})=P_{I'}(Z^{(0)}) + O(p^{I_{\max}+1-|I|})$.

\end{lemma}

\begin{proof}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_proborders.pdf}

    \end{center}

    \caption{\label{fig:lemmaillustration} Illustration of setup of Lemma \ref{lemma:probIndep}.}

\end{figure}

	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples vertex $0$ to zero must produce at least $I_{\max}$ zeroes in-between.

    Induction step: For an event $A$ and $k>0$ let us denote $A_k = A\cap\left(\cap_{j=0}^{k-1} \mathrm{Z}^{(j)}\right)\cap \mathrm{NZ}^{(k)}$, i.e. $A_k$ is the event $A$ \emph{and} ``Each vertex in $0,1,2,\ldots, k-1$ becomes $0$ at some point before termination (either by resampling or initialisation), but vertex $k$ does not''. Observe that these events form a partition, so $Z^{(0)}=\dot{\bigcup}_{k=1}^{\infty}Z^{(0)}_k$.

    Let $I_{<k}:=I\cap[1,k-1]$ and similarly $I_{>k}:=I\setminus[1,k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$ (note that $I_{><} = \gaps{I}$ as shown in Figure \ref{fig:diametergap}). Suppose we have proven the claim up to $|I|-1$, then the induction step can be shown by

	\begin{align*}

		P_{I}(Z^{(0)})

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

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

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

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

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

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

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

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

        \left(P_{I'_{>k}}(\mathrm{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_{I'_{<k}}(Z^{(0)}_k)\cdot

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

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

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

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

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

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

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

	\end{align*}

\end{proof}

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

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

\end{definition} 

Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is \emph{exactly} $\mathcal{P}$ whereas $A^{(P)}$ is the event that one of the patches is equal to $P$ but there can be other patches as well.

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

	Then we define

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

	For a patch set $\mathcal{P}$ and some $P\in\mathcal{P}$ we define

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

	and 

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

	finally

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

\end{definition} 

    Similarly to Mario's proof I use the observation that 

    \begin{align*}

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

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} R_{S(f)}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{(\mathcal{P})}) R^{(\mathcal{P})}_{S(f)} \\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{\mathcal{P}}) \sum_{P\in\mathcal{P}} R^{(P,\mathcal{P})}_{S(f)}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} 

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{\mathcal{P}}) \sum_{P\in\mathcal{P}} R^{(P)}_{S(f)\cap P}\tag{by Claim~\ref{claim:eventindependence}}\\ 

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} 

    \sum_{P\text{ patch}} R^{(P)}_{S(f)\cap P}\sum_{\mathcal{P}:P\in\mathcal{P}}\mathbb{P}_{S(f)}(A^{\mathcal{P}})\\     

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

     \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\        

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

    \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \tag{remember Definition~\ref{def:visitingResamplings} and use Claim~\ref{claim:eventindependence}}\\    

    &= \frac{1}{n}\sum_{S\subseteq [n]} \sum_{P\text{ patch}} \sum_{f_P\in\{0,1'\}^{|S\cap P|}}

    \rho_{S(f_P)} R^{(P)}_{S(f_P)} \mathbb{P}_{S(f_P)}(A^{(P)})

    \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \\   

	&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f_P\in\{0,1'\}^{|S\cap P|}}

	\rho_{S(f_P)}

        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathcal{O}(p^{|S_{><}|}) \tag{see below} \\

	&= \frac{1}{n}\sum_{S\subseteq [n]}\mathcal{O}(p^{|S|+|S_{><}|}).

    \end{align*}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_patches.pdf}

    \end{center}

    \caption{\label{fig:patches} Illustration of last steps of the proof.}

\end{figure}

    The penultimate inequality can be seen by case separation as follows: If $S\subseteq P$ then there is no splitting into $S\cap P$ and $S\setminus P$, and we already have $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$ simply because the patch $P$ must be filled with zeroes that were not yet in $S$, so this is at least $|S_{><}|$ resampled zeroes. For the more general case, assume that $S$ is larger than $P$ on both sides of $P$. This is illustrated in Figure \ref{fig:patches}. We will focus on the following sum that was in the above equations:

    \begin{align*}

        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S \cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})

    \end{align*}

    By Lemma \ref{lemma:eventindependence} we can split this sum into two parts: the part to the left of $P$ and the part to the right of $P$. Define $S_\mathrm{left}=S\cap[S_\mathrm{min},P_{\mathrm{min}}-1]$ and $S_\mathrm{right}=S\cap[P_{\mathrm{max}}+1,S_\mathrm{max}]$, so that $S\cap\overline{P} = S_\mathrm{left} \cup S_\mathrm{right}$. These are also illustrated in Figure \ref{fig:patches}. Then we have

    \begin{align*}

        \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})

        &= \mathbb{P}_{S(f_{\mathrm{left}})}(\overline{Z^{(P_{\min}-1)}}) \;\cdot\; \mathbb{P}_{S(f_{\mathrm{right}})}(\overline{Z^{(P_{\max}+1)}})

    \end{align*}

    and hence we can split the sum. Without loss of generality we now only consider the `right' part of the sum:

    \begin{align*}

        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}} \rho_{S_\mathrm{right}(f)} \mathbb{P}_{S_\mathrm{right}(f)}(\overline{Z^{(P_{\max}+1)}})

    \end{align*}

    Now further split this sum over the value of $f$ at position $S_\mathrm{max}$:

    \begin{align*}

        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}} \sum_{f'\in\{0,1'\}}

        \rho_{S_\mathrm{right}(f\,f')} \mathbb{P}_{S_\mathrm{right}(f\,f')}(\overline{Z^{(P_{\max}+1)}})

    \end{align*}

    and we use the definition of $\rho$ for the sum over $f'$:

    \begin{align*}

         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

        \rho_{S_\mathrm{right}(f)} \left(p \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) + (-p) \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) \right)

    \end{align*}

    Now we recognize the setup of Lemma~\ref{lemma:probIndep} with $I=S_\mathrm{right}(f\,0)$ and $I'=S_\mathrm{right}(f\,1)$. The lemma yields

    \begin{align*}

        \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-(P_{\mathrm{max}}+1)+1-|S_\mathrm{right}|}) \\

        &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) .

    \end{align*}

    Entering this back into the sum gives

    \begin{align*}

         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

        \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|+1})

         = \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}}

        \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|})

    \end{align*}

    One can do the same for the `left' part, which gives a term $\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|})$. The part of $S$ that was within $P$ gives $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|})$. Combining these three factors yields

    \begin{align*}

        (\textrm{left part})(P\textrm{ part})(\textrm{right part}) &=

\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|}) \cdot \mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|}) \cdot \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) \\

        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S_\mathrm{left}\cup S_\mathrm{right}\cup (S\cap P)|})\\

        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S|})

        = \mathcal{O}(p^{|S_{><}|})

    \end{align*}

    as required. This finishes the proof.

    ~

	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.