\documentclass[a4paper,11pt,english,final]{article}
\pdfoutput=1

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{fullpage}

\usepackage{graphics}
\usepackage{diagbox}
\usepackage[table]{xcolor}% http://ctan.org/pkg/xcolor
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{caption}
\captionsetup{compatibility=false}
\graphicspath{{./}}


\usepackage{tikz}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{bbm}
%\usepackage{bbold}
\usepackage{verbatim}

%for correcting large brackets spacing
\usepackage{mleftright}\mleftright

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumitem}
\usepackage{float}

%\usepackage{titling}

%\setlength{\droptitle}{-5mm}  

%\usepackage{MnSymbol}
\newcommand{\cupdot}{\overset{.}{\cup}}
\newcommand{\pvp}{\vec{p}{\kern 0.45mm}'}

\DeclarePairedDelimiter\bra{\langle}{\rvert}
\DeclarePairedDelimiter\ket{\lvert}{\rangle}
\DeclarePairedDelimiterX\braket[2]{\langle}{\rangle}{#1 \delimsize\vert #2}
\newcommand{\underflow}[2]{\underset{\kern-60mm \overbrace{#1} \kern-60mm}{#2}}

\def\Ind(#1){{{\tt Ind}({#1})}}
\def\Id{\mathrm{Id}}
\def\Pr{\mathrm{Pr}}
\def\Tr{\mathrm{Tr}}
\def\im{\mathrm{im}}
\newcommand{\bOt}[1]{\widetilde{\mathcal O}\left(#1\right)}
\newcommand{\bigO}[1]{\mathcal O\left(#1\right)}
\newcommand{\Res}[1]{\#\mathrm{Res}\left(#1\right)}

\newcommand{\QMAo}{\textsf{QMA$_1$}}
\newcommand{\BQP}{\textsf{BQP}}
\newcommand{\NP}{\textsf{NP}}
\newcommand{\SharpP}{\textsf{\# P}}

\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}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\NZ}[1]{\mathrm{NZ}^{(#1)}}
\newcommand{\Z}[1]{\mathrm{Z}^{(#1)}}
%\newcommand{\dist}[1]{d_{\!\!\not\,#1}}
\newcommand{\dist}[1]{d_{\neg #1}}

\newcommand{\todo}[1]{{\color{red}\textbf{TODO:} #1}}

\long\def\ignore#1{}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}%[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{remark}[theorem]{Remark}

\newenvironment{proof}
{\noindent {\bf Proof. }}
{{\hfill $\Box$}\\	\smallskip}

\usepackage[final]{hyperref}
\hypersetup{
	colorlinks = true,
	allcolors = {blue},
}
\usepackage{ifpdf} 
\ifpdf
	\typeout{^^J *** PDF mode *** } 
%	\input{myBiblatex.tex}
%	\addbibresource{LLL.bib}	
%\else
%	\typeout{^^J *** DVI mode ***} 
%	\hypersetup{breaklinks = true}
%	\usepackage[quadpoints=false]{hypdvips}
	\let\oldthebibliography=\thebibliography
	\let\endoldthebibliography=\endthebibliography
	\renewenvironment{thebibliography}[1]{%
		\begin{oldthebibliography}{#1}%
			\setlength{\itemsep}{-.3ex}%
	}%
	{%
		\end{oldthebibliography}%
	}
\fi 

%opening
\title{Criticality of resampling on the cycle / in the evolution model}
%\author{?\thanks{QuSoft, CWI and University of Amsterdam, the Netherlands. \texttt{?@cwi.nl} }
	%\and
	%?%
%}
%\thanksmarkseries{arabic}
%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\date{\vspace{-12mm}}

\begin{document}
	
	\maketitle

	\begin{abstract}
		The model we consider is the following~\cite{ResampleLimit}: We have a cycle of length $n\geq 3$. Initially we set each site to $0$ or $1$ independently at each site, such that we set it $0$ with probability $p$. After that in each step we select a random vertex with $0$ value and resample it together with its two neighbours assigning $0$ with probability $p$ to each vertex just as initially. The question we try to answer is what is the expected number of resamplings performed before reaching the all $1$ state. 
		
		We present strong evidence for a remarkable critical behaviour. We conjecture that there exists some $p_c\approx0.62$, such that for all $p\in[0,p_c)$ the expected number of resamplings is bounded by a $p$ dependent constant times $n$, whereas for all $p\in(p_c,1]$ the expected number of resamplings is exponentially growing in $n$.
	\end{abstract}
	%Let $R(n)$ denote this quantity for a length $n\geq 3$ cycle.
	
	We can think about the resampling procedure as a Markov chain. To describe the corresponding matrix we introduce some notation. For $b\in\{0,1\}^n$ let $r(b,i,(x_{-1},x_0,x_1))$ denote the bit string which differs form $b$ by replacing the bits at index $i-1$,$i$ and $i+1$ with the values in $x$, interpreting the indices $\!\!\!\!\mod n$. Also for $x\in\{0,1\}^k$ let $p(x)=p((x_1,\ldots,x_k))=\prod_{i=1}^{k}p^{(1-x_i)}(1-p)^{x_i}$. Now we can describe the matrix of the Markov chain. We use row vectors for the elements of the probability distribution indexed by bitstrings of length $n$. Let $M_{(n)}$ denote the matrix of the leaking Markov chain:
	$$
		M_{(n)}=\sum_{b\in\{0,1\}^n\setminus{\{1\}^n}}\sum_{i\in[n]:b_i=0}\sum_{x\in\{0,1\}^3}E_{(b,r(b,i,x))}\frac{p(x)}{n-|b|},
	$$
	where $E_{(i,j)}$ denotes the matrix that is all $0$ except $1$ at the $(i,j)$th entry.

	We want to calculate the average number of resamplings $R^{(n)}$, which we define as the expected number of resamplings divided by $n$. For this let $\rho,\mathbbm{1}\in[0,1]^{2^n}$ be indexed with elements of $\{0,1\}^n$ such that $\rho_b=p(b)$ and $\mathbbm{1}_b=1$. Then we use that the expected number of resamplings is just the hitting time of the Markov chain:
	\begin{align*}
		R^{(n)}:&=\mathbb{E}(\#\{\text{resampling before termination}\})/n\\
		&=\sum_{k=1}^{\infty}P(\text{at least } k \text{ resamplings are performed})/n\\
		&=\sum_{k=1}^{\infty}\rho M_{(n)}^k \mathbbm{1}/n\\
		&=\sum_{k=0}^{\infty}a^{(n)}_k p^k
	\end{align*}

	\begin{table}[]
	\centering
	\caption{Table of the coefficients $a^{(n)}_k$}
	\label{tab:coeffs}
	\resizebox{\columnwidth}{!}{%
		\begin{tabular}{c|ccccccccccccccccccccc}
			\backslashbox[10mm]{$n$}{$k$} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\		\hline
			3 &	0 & 1 & \cellcolor{blue!25}2 & 3+1/3 & 5.00 & 7.00 & 9.33 & 12.00 & 15.00 & 18.33 & 22.00 & 26.00 & 30.33 & 35.00 & 40.00 & 45.333 & 51.000 & 57.000 & 63.333 & 70.000 & 77.000 \\
			4 &	0 & 1 & 2 & \cellcolor{blue!25}3+2/3 & 6.16 & 9.66 & 14.3 & 20.33 & 27.83 & 37.00 & 48.00 & 61.00 & 76.16 & 93.66 & 113.6 & 136.33 & 161.83 & 190.33 & 222.00 & 257.00 & 295.50 \\
			5 &	0 & 1 & 2 & 3+2/3 & \cellcolor{blue!25}6.44 & 10.8 & 17.3 & 26.65 & 39.43 & 56.48 & 78.65 & 106.9 & 142.2 & 185.8 & 238.7 & 302.41 & 378.05 & 467.13 & 571.14 & 691.69 & 830.44 \\
			6 &	0 & 1 & 2 & 3+2/3 & 6.44 & \cellcolor{blue!25}11.0 & 18.5 & 30.02 & 47.10 & 71.68 & 106.0 & 152.9 & 215.4 & 297.4 & 403.1 & 537.21 & 705.25 & 913.31 & 1168.2 & 1477.4 & 1849.1 \\
			7 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & \cellcolor{blue!25}18.7 & 31.21 & 50.83 & 80.80 & 125.3 & 189.7 & 280.8 & 407.0 & 578.6 & 808.13 & 1110.2 & 1502.6 & 2005.6 & 2643.2 & 3443.1 \\
			8 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & \cellcolor{blue!25}31.44 & 52.08 & 84.95 & 136.0 & 213.6 & 328.9 & 496.5 & 735.6 & 1070.7 & 1532.5 & 2159.5 & 2998.8 & 4108.1 & 5556.7 \\
			9 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & \cellcolor{blue!25}52.30 & 86.27 & 140.7 & 226.3 & 358.4 & 558.4 & 855.4 & 1289.0 & 1911.5 & 2791.4 & 4017.2 & 5701.4 & 7985.9 \\
			10&	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & 52.30 & \cellcolor{blue!25}86.49 & 142.1 & 231.6 & 373.4 & 594.8 & 934.4 & 1447.1 & 2209.0 & 3324.6 & 4934.8 & 7226.9 & 10447. \\
            \vdots \\
            15& 0 & 1 & 2 & 3+2/3 & 6.44 & 11.08 & 18.76 & 31.45 & 52.31 & 86.49 & 142.33 & 233.31 & 381.17 & 621.02 & \cellcolor{blue!25}1009.38 & 1637.13 & % 2650.74 & 4285.68 & 6913.55 & 11171.2 & 18052.2
        \end{tabular}
	}
	\end{table}

	We observe that this is a power series in $p$. We discovered a very regular structure in this power series. It seems that for all $k\in\mathbb{N}$ and for all $n>k$ we have that $a^{(n)}_k$ is constant, this conjecture we verified using a computer up to $n=14$. 
	\newpage
	\noindent Based on our calculations presented in Table~\ref{tab:coeffs} and Figure~\ref{fig:coeffs_conv_radius} we make the following conjectures:
	\begin{enumerate}[label=(\roman*)]
		\item $\forall k\in\mathbb{N}, \forall n\geq 3 : a^{(n)}_k\geq 0$	\label{it:pos}	
        (A simpler version: $\forall k>0: a_k^{(3)}=(k+1)(k+2)/6$)
		\item $\forall k\in\mathbb{N}, \forall n>m\geq 3 : a^{(n)}_k\geq a^{(m)}_k$ \label{it:geq}		
		\item $\forall k\in\mathbb{N}, \forall n,m\geq \max(k,3) : a^{(n)}_k=a^{(m)}_k$ \label{it:const}		
  		\item $\exists p_c=\lim\limits_{k\rightarrow\infty}1\left/\sqrt[k]{a_{k}^{(k+1)}}\right.$ \label{it:lim}			
	\end{enumerate}
	We also conjecture that $p_c\approx0.61$, see Figure~\ref{fig:coeffs_conv_radius}.

	\begin{figure}[!htb]\centering
	\includegraphics[width=0.5\textwidth]{coeffs_conv_radius.pdf}
	%\includegraphics[width=0.5\textwidth]{log_coeffs.pdf}	
	\caption{$1\left/\sqrt[k]{a_{k}^{(k+1)}}\right.$} %$\frac{1}{\sqrt[k]{a_k^{(k+1)}}}$
	\label{fig:coeffs_conv_radius}
	\end{figure}
    
    For reference, we also explicitly give formulas for $R^{(n)}(p)$ for small $n$. We also give them in terms of $q=1-p$ because they sometimes look nicer that way.
    \begin{align*}
    	R^{(3)}(p) &= \frac{1-(1-p)^3}{3(1-p)^3}
        			= \frac{1-q^3}{3q^3}\\
    	R^{(4)}(p) &= \frac{p(6-12p+10p^2-3p^3)}{6(1-p)^4}
                    = \frac{(1-q)(1+q+q^2+3q^3)}{6q^4}\\
        R^{(5)}(p) &= \frac{p(90-300p+435p^2-325p^3+136p^4-36p^5+6p^6)}{15(1-p)^5(6-2p+p^2)}\\
                   &= \frac{(1-q)(6+5q+6q^2+21q^3+46q^4+6q^6)}{15q^5(5+q^2)}
    \end{align*}
    For $n=3$ the system becomes very simple because regardless of the current state, the probability of going to $111$ is always equal to $(1-p)^3$. Therefore the expected number of resamplings is simply the expectation of a geometric distribution. This gives the formula for $R^{(3)}(p)$ as shown above. Note that the $k$-th coefficient of the powerseries of a function $f(p)$ is given by $\frac{1}{k!}\left.\frac{d^k f}{dp^k}\right|_{p=0}$, i.e. the $k$-th derivative to $p$ evaluated at $0$ divided by $k!$. For the function $R^{(3)}(p) =\frac{(1-p)^{-3} - 1}{3} $ this yields $a^{(3)}_k = (k+2)(k+1)/6$ for $k\geq 1$ and $a^{(3)}_0=0$.

    We can do the same for $n=4,5$, which gives, for $k\geq 1$ (with Mathematica):
    \begin{align*}
        a^{(3)}_k &= \frac{(k+2)(k+1)}{6}\\
        a^{(4)}_k &= \frac{1}{6}\left(2+\frac{(k+3)(k+2)(k+1)}{6}\right)\\
        a^{(5)}_k &= \frac{1}{15}\left(\frac{(k+4)(k+3)(k+2)(k+1)}{20} - \frac{(k+3)(k+2)(k+1)}{30} - \frac{(k+2)(k+1)}{50} + \frac{76(k+1)}{25}\right.\\
                  &  \qquad\quad \left. + \frac{626}{125} - \frac{4}{250}
                  \left( \left(\frac{1+i\sqrt{5}}{6}\right)^k(94-25\sqrt{5}i)+\left(\frac{1-i\sqrt{5}}{6}\right)^k(94+25\sqrt{5}i) \right)
                  \right)
    \end{align*}
    and from $n=6$ and onwards, the expression becomes complicated and Mathematica can only give expressions including roots of polynomials.

    ~

	If statements \ref{it:pos}-\ref{it:lim} are true, then we can define the function 
	$$R^{(\infty)}(p):=\sum_{k=0}^{\infty}a^{(k+1)}_k p^k,$$
	which would then have radius of convergence $p_c$, also it would satisfy for all $p\in[0,p_c)$ that $R^{(n)}(p)\leq R^{(\infty)}(p)$ and $\lim\limits_{n\rightarrow\infty}R^{(n)}(p)=R^{(\infty)}(p)$.
	It would also imply, that for all $p\in(p_c,1]$ we get $R^{(n)}(p)=\Omega\left(\left(\frac{p}{p_c}\right)^{n/2}\right)$.
	This would then imply a very strong critical behaviour. It would mean that for all $p\in[0,p_c)$ the expected number of resamplings is bounded by a constant $R^{(\infty)}(p)$ times $n$, whereas for all $p\in(p_c,1]$ the expected number of resamplings is exponentially growing in $n$.
	
	Now we turn to the possible proof techniques for justifying the conjectures \ref{it:pos}-\ref{it:lim}.
	First note that $\forall n\geq 3$ we have $a^{(n)}_0=0$, since for $p=0$ the expected number of resamplings is $0$.
	Also note that the expected number of initial $0$s is $p\cdot n$. If $p\ll1/n$, then with high probability there is a single $0$ initially and the first resampling will fix it, so the linear term in the expected number of resamplings is $np$, therefore $\forall n\geq 3$, $a^{(n)}_1=1$. 
	
	For the second order coefficients it is a bit harder to argue, but one can use the structure of $M_{(n)}$ to come up with a combinatorial proof. To see this, first assume we have a vector $e_b$ having a single non-zero, unit element indexed with bitstring $b$.
	Observe that $e_bM_{(n)}$ is a vector containing polynomial entries, such that the only indices $b'$ which have a non-zero constant term must have $|b'|\geq|b|+1$, since if a resampling produces a $0$ entry it also introduces a $p$ factor. Using this observation one can see that the second order term can be red off from $\rho M_{(n)}\mathbbm{1}+\rho M_{(n)}^2\mathbbm{1}$,
	which happens to be $2n$. (Note that it is already a bit surprising, form the steps of the combinatorial proof one would expect $n^2$ terms appearing, but they just happen to cancel each other.) Using similar logic one should be able to prove the claim for $k=3$, but for larger $k$s it seems to quickly get more involved.
	
	The question is how could we prove the statements \ref{it:pos}-\ref{it:lim} for a general $k$?
	
    \appendix
    
    \section{Lower bound on $R^{(n)}(p)$}
    Proof that \ref{it:pos} and \ref{it:lim} imply that for any fixed $p>p_c$ we have $R^{(n)}(p)\in\Omega\left(\left(\frac{p}{p_c}\right)^{n/2}\right)$. 
    
    By definition of $p_c = \lim_{k\to\infty} 1\left/ \sqrt[k]{a_k^{(k+1)}} \right.$ we know that for any $\epsilon$ there exists a $k_\epsilon$ such that for all $k\geq k_\epsilon$ we have $a_k^{(k+1)}\geq (p_c + \epsilon)^{-k}$. Now note that $R^{(n)}(p) \geq a_{n-1}^{(n)}p^{n-1}$ since all terms of the power series are positive, so for $n\geq k_\epsilon$ we have $R^{(n)}(p)\geq (p_c +\epsilon)^{-(n-1)}p^{n-1}$. Note that
    \begin{align*}
    	R^{(n)}(p)\geq(p_c+\epsilon)^{-(n-1)}p^{n-1}=\left(\frac{p}{p_c+\epsilon}\right)^{n-1} \geq \left(\frac{p}{p_c}\right)^{\frac{n-1}{2}},
    \end{align*}
    where the last inequality holds for $\epsilon\leq\sqrt{p_c}(\sqrt{p}-\sqrt{p_c})$.
    
    \section{Calculating the coefficients $a_k^{(n)}$}
    Let $\rho'\in\mathbb{R}[p]^{2^n}$ be a vector of polynomials, and let $\text{rank}(\rho')$ be defined in the following way: 
    $$\text{rank}(\rho'):=\min_{b\in\{0,1\}^n}\left( |b|+ \text{maximal } k\in\mathbb{N} \text{ such that } p^k \text{ divides } \rho'_b\right).$$
	Clearly for any $\rho'$ we have that $\text{rank}(\rho' M_{(n)})\geq \text{rank}(\rho') + 1$. Another observation is, that all elements of $\rho'$ are divisible by $p^{\text{rank}(\rho')-n}$.
    We observe that for the initial $\rho$ we have that $\text{rank}(\rho)=n$, therefore $\text{rank}(\rho*(M_{(n)}^k))\geq n+k$, and so $\rho*(M_{(n)}^k)*\mathbbm{1}$ is obviously divisible by $p^{k}$. This implies that $a_k^{(n)}$ can be calculated by only looking at $\rho*(M_{(n)}^1)*\mathbbm{1}, \ldots, \rho*(M_{(n)}^k)*\mathbbm{1}$.
    
\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)$.
   
Some terminology: for any configuration we call a $0$ a \emph{particle} (probability $p$) and a $1'$ an \emph{antiparticle} (probability $-p$). We use the word \emph{slot} for a position that is occupied by either a paritcle or antiparticle ($0$ or $1'$). In the initial state, the probability of a configuration is given by $\pm p^{\mathrm{\#slots}}$ where the $\pm$ sign depends on the parity of the number of antiparticles.
    
We can further rewrite the sum over $b\in\{0,1,1'\}^n$ as a sum over all slot configurations $C\subseteq[n]$ and over all possible fillings of these slots.
\begin{align*}
	R^{(n)}(p) &= \frac{1}{n} \sum_{C\subseteq[n]} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,
\end{align*}
where $C(f)\in\{0,1,1'\}^n$ denotes a configuration with slots on the sites $C$ filled with (anti)particles described by $f$. The non-slot positions are filled with $1$s.

\begin{definition}[Diameter and gaps] \label{def:diameter} \label{def:gaps}
    For a subset $C\subseteq[n]$, we define the \emph{diameter} $\diam{C}$ to be the minimum size of an integer interval $I$ containing $C$. Here we consider both $C$ and the interval modulo $n$. In other words $\diam{C} = \min\{ j \vert \exists i : C\subseteq [i,i+j-1] \}$. We define the \emph{gaps} of $C$, as $I\setminus C$ and denote this by $\gaps{C}$. Note that $\diam{C} = |C| + |\gaps{C}|$.  Define $\maxgap{C}$ as the size of the largest connected component of $\gaps{C}$. Figure \ref{fig:diametergap} illustrates these concepts with a picture. 
\end{definition}
\begin{figure}
	\begin{center}
    	\includegraphics{diagram_gap.pdf}
    \end{center}
    \caption{\label{fig:diametergap} Illustration of Definition \ref{def:diameter}. A set $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 positions is shown by the red dots. The smallest interval containing $C$ is $[1,9]$, so the diameter is $\diam{C}=9$. The blue squares denote the set $\gaps{C} = \{3,5,6,8\}$. The dotted line at the top depicts the rest of the cycle which may be much larger. The largest gap of $C$ is $\maxgap{C}=2$ which is the largest connected component of $\gaps{C}$.}
\end{figure}

\begin{claim}[Strong cancellation claim] \label{claim:strongcancel}
	The lowest order term in
    \begin{align*}
        \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,
    \end{align*}
	is $p^{\diam{C}}$ when $n$ is large enough. All lower order terms cancel out.
\end{claim}

Example: for $C_0=\{1,2,4,7,9\}$ (the configuration shown in Figure \ref{fig:diametergap}) we computed the quantity up to order $p^{20}$ in an infinite system:
\begin{align*}
	\sum_{f\in\{0,1'\}^{|C_0|}} \rho_{C_0(f)} R_{C_0(f)} &= 0.0240278 p^{9} + 0.235129 p^{10} + 1.24067 p^{11} + 4.71825 p^{12} \\
    &\quad + 14.5555 p^{13} + 38.8307 p^{14} + 93.2179 p^{15} + 206.837 p^{16}\\
    &\quad + 432.302 p^{17} + 862.926 p^{18} + 1662.05 p^{19} + 3112.9 p^{20} + \mathcal{O}(p^{21})
\end{align*}
and indeed the lowest order is $\diam{C}=9$.

~

A weaker version of the claim is that if $C$ contains a gap of size $k$, then the sum is zero up to and including order $p^{|C|+k-1}$.
\begin{claim}[Weak cancellation claim] \label{claim:weakcancel}
	For $C\subseteq[n]$ a configuration of slot positions, the lowest order term in
    \begin{align*}
        \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,
    \end{align*}
    is at least $p^{|C|+\maxgap{C}}$ when $n$ is large enough. All lower order terms cancel out.
\end{claim}
This weaker version would imply \ref{it:const} but for $\mathcal{O}(k^2)$ as opposed to $k+1$.

\newpage
The reason that claim \ref{claim:strongcancel} would prove \ref{it:const} is the following: to know the value of $a_k^{(n)}$, for any $n\geq k+1$ it is enough to look at configurations $C$ with diameter at most $k$, since larger configurations do not contribute to $a_k^{(n)}$.
For a starting state $b\in\{0,1\}^n$ that \emph{does} give a nonzero contribution, you can take that same starting configuration and translate it to get $n$ other configurations that give the same contribution. (An exception is a starting state like $1010101010...$ which you can only translate twice, but we only have to consider configurations with small diameter, in which case you can make exactly $n$ translations.)
Therefore the coefficient in the expected number of resamplings is a multiple of $n$ which Andr\'as already divided out in the definition of $R^{(n)}(p)$. To show \ref{it:const} we argue that this is the \emph{only} dependency on $n$. This is because there are only finitely many (depending on $k$ but not on $n$) configurations where the $k$ slots are nearby regardless of the value of $n$. So there are only finitely many nonzero contributions after translation symmetry was taken out. For example, when considering all starting configurations with 5 slots one might think there are $\binom{n}{5}$ configurations to consider which would be a dependency on $n$ (more than only the translation symmetry). But since most of these configurations have a diameter larger than $k$, they do not contribute to $a_k$. Only finitely many do and that does not depend on $n$.

~

Section \ref{sec:computerb} shows how to compute $R_b$ (this is not relevant for showing the claim) and the section after that shows how to prove the weaker claim.

\newpage
\subsection{Computation of $R_b$} \label{sec:computerb}

By $R_{101}$ we denote $R_b(p)$ for a $b$ that consists of only $1$s except for a single zero. We compute $R_{101}$ up to second order in $p$. This requires the following transitions.
\begin{align*}
    \framebox{$1 0 1$} &\to \framebox{$1 1 1$} & (1-p)^3 = 1-3p+3p^2-p^3\\
    \hline
    \framebox{$1 0 1$} &\to
        \begin{cases}
            \framebox{$0 1 1$}\\
            \framebox{$1 0 1$}\\
            \framebox{$1 1 0$}
        \end{cases}
        & 3p(1-p)^2 = 3p-6p^2+3p^3\\
    \hline
    \framebox{$1 0 1$} &\to \framebox{$0 1 0$} & p^2(1-p) = p^2-p^3\\
    \framebox{$1 0 1$} &\to
        \begin{cases}
            \framebox{$1 0 0$}\\
            \framebox{$0 0 1$}
        \end{cases}
        & 2p^2(1-p) = 2p^2 - 2p^3\\
    \hline
    \framebox{$1 0 1$} &\to \framebox{$0 0 0$} & p^3
\end{align*}
With this we can write a recursive formula for the expected number of resamples from $101$:
\begin{align*}
    R_{101} &= (1-3p+3p^2 - p^3)(1) + (3p -6p^2 +3p^3) (1+R_{101}) \\
            &\quad + (p^2 - p^3) (1+R_{10101}) + (2p^2-2p^3) (1+R_{1001}) + p^3(1+R_{10001}) \\
			&= 1 + 3 p + 7 p^2 + 14.6667 p^3 + 29 p^4 + 55.2222 p^5 + 102.444 p^6 + 186.36 p^7 \\
            &\quad + 333.906 p^8 + 590.997 p^9 + 1035.58 p^{10} + 1799.39 p^{11} + 3104.2 p^{12} \\
            &\quad+ 5322.18 p^{13} + 9075.83 p^{14} + 15403.6 p^{15} + 26033.4 p^{16} + 43833.5 p^{17} \\
            &\quad+ 73555.2 p^{18} + 123053 p^{19} + 205290 p^{20} + 341620 p^{21} + 567161 p^{22} \\
            &\quad+ 939693 p^{23} + 1.5537\cdot10^{6} p^{24} + 2.56158\cdot10^{6} p^{25} + \mathcal{O}(p^{26})
\end{align*}
where the recursion steps were done with a computer for an infinite line (or a cirlce where $n$ is assumed to be much larger than the largest power of $p$ considered).

Note: in the first line at the second term it uses that with probability $(3p-6p^2 + 3p^3)$ the state goes to $\framebox{$101$}$ and then the expected number of resamplings is $1+R_{101}$. Note that the actual term in the recursive formula should be
$$(3p-6p^2+3p^3)\cdot\left( \sum_{\xi\in\paths{101}} \mathbb{P}[\xi] \cdot \left( 1 + |\xi|\right) \right) = (3p-6p^2+3p^3)\left( p_\mathrm{tot} + R_{101} \right)$$
where $p_\mathrm{tot} := \sum_{\xi\in\paths{b}} \mathbb{P}[\xi]$. However, since the state space is finite (for finite $n$) and there is always a non-vanishing probability to go to $\mathbf{1}$, we know that $p_\mathrm{tot}=1$, i.e. the process terminates almost surely.

\newpage
\subsection{Weak cancellation proof}

Here we prove claim \ref{claim:weakcancel}, the weaker version of the claim. We require the following definition
\begin{definition}[Path independence] \label{def:independence}
	We say two paths $\xi_i\in\paths{b_i}$ ($i=1,2$) of the Markov Chain are \emph{independent} if $\xi_1$ never resamples a site that was ever zero in $\xi_2$ and the other way around. It is allowed that $\xi_1$ resamples a $1$ to a $1$ that was also resampled from $1$ to $1$ by $\xi_2$ and vice versa. If the paths are not independent then we call the paths \emph{dependent}.
\end{definition}
\begin{definition}[Path independence - alternative] \label{def:independence2}
    Equivalently, on the infinite line $\xi_1$ and $\xi_2$ are independent if there is a site `inbetween' them that was never zero in $\xi_1$ and never zero in $\xi_2$. On the cycle $\xi_1$ and $\xi_2$ are independent if there are \emph{two} sites inbetween them that are never zero.
\end{definition}
\begin{claim}[Sum of expectation values] \label{claim:expectationsum}
When $b=b_1\land b_2\in\{0,1\}^n$ is a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes with $k$ $1$s inbetween the groups, then we have $R_b(p) = R_{b_1}(p) + R_{b_2}(p) + \bigO{p^{k}}$ where $b_1$ and $b_2$ are the configurations where only one of the groups is present and the other group has been replaced by $1$s. To be precise, the sums agree up to and including order $p^{k-1}$.
\end{claim}
\textbf{Example}: For $b_1 = 0111111$ and $b_2 = 1111010$ we have $b=0111010$ and $k=3$. The claim says that the expected time to reach $\mathbf{1}$ from $b$ is the time to make the first group $1$ plus the time to make the second group $1$, as if they are independent. Simulation shows that
\begin{align*}
    R_{b_1} &= 1 + 3p + 7p^2 + 14.67p^3 + 29p^4 + \mathcal{O}(p^5)\\
    R_{b_2} &= 2 + 5p + 10.67p^2 + 21.11p^3+40.26p^4 + \mathcal{O}(p^5)\\
    R_{b} &= 3 + 8p + 17.67p^2 + 34.78p^3+65.27p^4 + \mathcal{O}(p^5)\\
    R_{b_1} + R_{b_2} &= 3 + 8p + 17.67p^2+35.78p^3 + 69.26p^4 +\mathcal{O}(p^5)
\end{align*}
and indeed the sums agree up to order $p^{k-1}=p^2$. When going up to order $p^{k}$ or higher, there will be terms where the groups interfere so they are no longer independent.

~

\begin{proof}
    Consider a path $\xi_1\in\paths{b_1}$ and a path $\xi_2\in\paths{b_2}$ such that $\xi_1$ and $\xi_2$ are independent (Definition \ref{def:independence} or \ref{def:independence2}). The paths $\xi_1,\xi_2$ induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ different paths of total length $|\xi_1|+|\xi_2|$ in $\paths{b_1\land b_2}$. In the sums $R_{b_1}$ and $R_{b_2}$, the contribution of these paths are $\mathbb{P}[\xi_1]\cdot |\xi_1|$ and $\mathbb{P}[\xi_2]\cdot |\xi_2|$. The next diagram shows how these $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths contribute to $R_{b_1\land b_2}$. Point $(i,j)$ in the grid indicates that $i$ steps of $\xi_1$ have been done and $j$ steps of $\xi_2$ have been done. At every point (except the top and right edges of the grid) one has to choose between doing a step of $\xi_1$ or a step of $\xi_2$. The number of zeroes in the current state determine the probabilities with which this happens (beside the probabilities associated to the two original paths already). The grid below shows that at a certain point one can choose to do a step of $\xi_1$ with probability $p_i$ or a step of $\xi_2$ with probability $1-p_i$. These $p_i$ could in principle be different at every point in this grid. The weight of such a new path $\xi\in\paths{b_1\land b_2}$ is $p_\mathrm{grid}\cdot\mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]$ where $p_\mathrm{grid}$ is the weight of the path in the diagram. By induction one can show that the sum over the $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ different terms $p_\mathrm{grid}$ is $1$.
\begin{center}
\includegraphics{diagram_paths.pdf}
\end{center}
 Hence the contribution of all $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths together to $R_{b_1\land b_2}$ is given by
\[
\mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]\cdot(|\xi_1|+|\xi_2|) = \mathbb{P}[\xi_2]\cdot\mathbb{P}[\xi_1]\cdot|\xi_1| \;\; + \;\; \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]\cdot|\xi_2|.
\]
Ideally we would now like to sum this expression over all possible paths $\xi_1,\xi_2$ and use $p_\mathrm{tot}:=\sum_{\xi\in\paths{b_i}} \mathbb{P}[\xi] = 1$ (which also holds up to arbitrary order in $p$). The above expression would then become $R_{b_1} + R_{b_2}$. However, not all paths in the sum would satisfy the independence condition so it seems we can't do this. We now argue that it works up to order $p^{k-1}$.
For all $\xi\in\paths{b_1\land b_2}$ we have that \emph{either} $\xi$ splits into two independent paths $\xi_1,\xi_2$ as above, \emph{or} it does not. In the latter case, when $\xi$ can not be split like that, we know $\mathbb{P}[\xi]$ contains a power $p^k$ or higher because there is a gap of size $k$  and the paths must have moved at least $k$ times `towards each other' (for example one path moves $m$ times to the right and the other path moves $k-m$ times to the left). So the total weight of such a combined path is at least order $p^k$. Therefore we have
\[
	R_{b_1\land b_2} = \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1| + \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_1]\mathbb{P}[\xi_2]|\xi_2| + \sum_{\mathclap{\xi\;\mathrm{dependent}}} \mathbb{P}[\xi]|\xi|.
\]
where last sum only contains only terms of order $p^{k}$ or higher. Now for the first sum, note that
\[
	\sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|
    = \sum_{\xi_1\in\paths{b_1}} \sum_{\substack{\xi_2\in\paths{b_2}\\ \text{independent of }\xi_1}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|
\]
where the sum over independent paths could be empty for certain $\xi_1$. Now we replace this last sum by a sum over \emph{all} paths $\xi_2\in\paths{b_2}$. This will change the sum but only for terms where $\xi_1,\xi_2$ are dependent. For those terms we already know that $\mathbb{P}[\xi_1]\mathbb{P}[\xi_2]$ contains a factor $p^k$ and hence we have 
\begin{align*}
    \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|
    &= \sum_{\xi_1\in\paths{b_1}} \sum_{\xi_2\in\paths{b_2}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\
    &= \sum_{\xi_1\in\paths{b_1}} \mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\
    &= R_{b_1} + \mathcal{O}(p^k)
\end{align*}
we can do the same with the second term and this proves the claim.
\end{proof}

~\\
\textbf{Proof of claim \ref{claim:weakcancel}}: We can assume $C$ consists of a group on the left with $l$ slots and a group on the right with $r$ slots (so $r+l=|C|$), with a gap of size $k=\mathrm{gap}(C)$ between these groups. Then on the left we have strings in $\{0,1'\}^l$ as possibilities and on the right we have strings in $\{0,1'\}^r$. The combined configuration can be described by strings $f=(a,b)\in\{0,1'\}^{l+r}$. The initial probability of such a state $C(a,b)$ is $\rho_{C(a,b)} = (-1)^{|a|+|b|} p^{r+l}$ and by claim \ref{claim:expectationsum} we know $R_{C(a,b)} = R_{C(a)} + R_{C(b)} + \mathcal{O}(p^k)$ where $C(a)$ indicates that only the left slots have been filled by $a$ and the other slots are filled with $1$s. The total contribution of these configurations is therefore
\begin{align*}
    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}
    &= \sum_{a\in\{0,1'\}^l} \sum_{b\in\{0,1'\}^r} (-1)^{|a|+|b|}p^{r+l} \left( R_{C(a)} + R_{C(b)} + \mathcal{O}(p^k) \right) \\
    &=\;\;\; p^{r+l}\sum_{a\in\{0,1'\}^l} (-1)^{|a|} R_{C(a)} \sum_{b\in\{0,1'\}^r} (-1)^{|b|} \\
    &\quad + p^{r+l}\sum_{b\in\{0,1'\}^r} (-1)^{|b|} R_{C(b)} \sum_{a\in\{0,1'\}^l} (-1)^{|a|}
        + \mathcal{O}(p^{r+l+k})\\
    &= 0 + \mathcal{O}(p^{|C|+k})
\end{align*}
where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$.

\newpage
\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 $\start{b}$ as the event that the starting state of the chain is the state $b$. For any event $A$, define
    \begin{align*}
        \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) %\\
        %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \start{b})
    \end{align*}
    Furthermore, for $v\in[n]$ we define
    \begin{align*}
        \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1),
    \end{align*}
    and we define similarly $\P^{[n]}_{b_v=b_w=1}(A)$ for $v,w\in[n]$.
\end{definition}
%Note that we have $\P^{(n)}(\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}^{(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 $v,w$.}
%\end{figure}
\begin{wrapfigure}{r}{0.25\textwidth}
    \centering
    \includegraphics{diagram_groups.pdf}
    \caption{\label{fig:separatedgroups} Lemma \ref{lemma:eventindependence}.}
\end{wrapfigure}
The following lemma considers two vertices $v,w$ that are never ``crossed'' so that two halves of the cycle become independent.\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 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*}
        \P^{(n)}_b(\mathrm{NZ}^{(v,w)}, A_1, A_2)
        &=
        \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)}, A_1)
        \; \cdot \;
        \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)}, A_2) \\
        \P^{(n)}_b(A_1, A_2 \mid \mathrm{NZ}^{(v,w)})
        &=
        \P^{(n)}_{b_1}(A_1 \mid \mathrm{NZ}^{(v,w)})
        \; \cdot \;
        \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$.
\end{lemma}

\begin{proof}
    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^{(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 $\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.
    %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{definition}[Starting state dependent probability distribution.]
	Let $I\subset\mathbb{Z}$ be a finite set of vertices.
    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}

\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^{[v,w]}_{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}

    Some notation: let $P$ be an interval $[a,b]$. We say $P$ is a \emph{patch} when the $\Z{i}$ event holds for all $i \in [a,b]$ and $\NZ{a-1}$ and $\NZ{b+1}$ holds. We denote this event by $P\in\mathcal{P}$, so
	\begin{align*}
	P\in\mathcal{P} \equiv \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*}
	Note that we have the following partition of the event $\Z{v}$ for any vertex $v\in[n]$:
	\begin{align*}
	\Z{v} = \dot\bigcup_{P : 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 are 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)}-R^{(m)}=\bigO{p^{\min(n,m)}}$.
	\end{theorem}
	\begin{proof}
		Let $N\geq \max(2n,2m)$, then
		\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^{[-N,-v]}(\NZ{-v})\P^{[w,N]}(\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^{[-N,-v]}(\NZ{-v})\P^{[w,N]}(\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^{[-N,N]}(\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^{[-N,N]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\[-1mm]
			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:0\in P}\P^{[-N,N]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\
			&= \E^{[-N,N]}(\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}			

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})+\bigO{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})+\bigO{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}}\\
		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)
		\left(\sum_{S'\subseteq [-d]}\sum_{f'\in\{0,1'\}^{|S'|}}\rho_{S'(f')} \P^\infty_{S'(f')}(\NZ{k})\right)
		+\mathcal{O}(p^{d})\\
		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!2}
		+\mathcal{O}(p^{d})\tag{by symmetry}\\		
		&=\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}).\tag{Corollary \ref{cor:probIndep}}
		\end{align*}
	\end{proof}
	
	\begin{remark}\label{rem:cycleContained}
		For all $n\geq k$ and $I\subseteq [k]$ we have that 
		$$\P^n_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1}\cap \NZ{k}).$$
	\end{remark}
	
	
	\begin{theorem}
		Suppose $n,m\geq 2k$, then $R^{(n)}-R^{(m)}=\bigO{p^{k}}$.
	\end{theorem}
	\begin{proof}
		\begin{align*}
		R^{(n)} &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}\\
		&= \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_{v\in[n]}\sum_{t=1}^{\infty}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step})\\
		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step and }P\text{ is a patch})\\
		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}
		\rho_{S(f)} \sum_{P\text{ patch}} R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\  
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}
		\rho_{S(f)}  R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) + \bigO{p^{k}} \tag{by translation symmetry}\\   
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq [n]}\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}}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \bigO{p^{k}}  \tag{by Lemma~\ref{claim:eventindependence}}\\   	
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq P}\sum_{f\in\{0,1'\}^{|S|}}
		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})
		\sum_{S'\subseteq \overline{P}}\sum_{f'\in\{0,1'\}^{|S'|}}\P_{S'(f')}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \bigO{p^{k}} \\  
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq P}\sum_{f\in\{0,1'\}^{|S|}}
		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})\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}
		+\bigO{p^{k}}.\tag{By Corollary \ref{cor:independenetSides} with $k=|\overline{P}|$ observing			$p^{k}=\mathcal{O}(p^{|P|+\lfloor\frac{|\overline{P}|}{2}\rfloor})$.}	
		\end{align*}
		Since the above expression is independent of $n$ the statement follows.
	\end{proof}
	
	
	%Final observation: Suppose $S={a,b}$ 
	%    \begin{align*}
	%    &\sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)}\cap \NZ{(P_{\max}+1)})  \\
	%    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)}) \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\
	%    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}}  \rho_{a_f}\mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)})  \rho_{b_f}\mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\
	%    \end{align*}
	
	~
	
	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.

Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the infinite chain.
\begin{lemma}[Startingstate dependence] \label{lemma:probIndepCycle}
    Let $d(a,b)$ be the distance between $a,b\in[n]$ on the cycle, so $d(a,b)=\min(|a-b| , n-|a-b|)$. Let $\dist{s}(a,b)$ be the distance between $a,b$ when taking the path that does \emph{not} cross $s$. Let $I\subseteq [n]$ be a non-empty set of vertices. Let $i_* \in I$ and define $I' = I \setminus \{i_*\}$. Let $j,s\notin I$, with $j\neq s$ be any vertices not in $I$.
    Then
    \begin{align*}
        \P_{I}(\Z{j})        &= \P_{I'}(\Z{j})        + \mathcal{O}(p^{d(i_*,j) + 1 - |I|}) \\
        \P_{I}(\Z{j},\NZ{s}) &= \P_{I'}(\Z{j},\NZ{s}) + \mathcal{O}(p^{\min\left( \dist{s}(i_*,j), \dist{j}(i_*,s) \right) + 1 - |I|}) .
    \end{align*}
\end{lemma}
\begin{proof}
    Without loss of generality, we can assume that $j=0$ and  $0 < i_* < s < n$ (because we can shift $j$ to $0$ and switch the direction to get the correct ordering). Therefore, we have to prove:
    \begin{align*}
        \P_{I}(\Z{0})        &= \P_{I'}(\Z{0})        + \mathcal{O}(p^{d(i_*,0) + 1 - |I|}) \\
        \P_{I}(\Z{0},\NZ{s}) &= \P_{I'}(\Z{0},\NZ{s}) + \mathcal{O}(p^{\min\left( i_*, s-i_* \right) + 1 - |I|}) .
    \end{align*}
    We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{0})=0$ and
    \begin{align*}
        \P_{I}(\Z{0})        &= \mathcal{O}(p^{d(i_*,0)}) \\
        \P_{I}(\Z{0},\NZ{s}) &= \mathcal{O}(p^{i_*}) = \mathcal{O}(p^{\min\left( i_*, s-i_* \right)})
    \end{align*}
    simply because a chain of zeroes has to be formed between $i_*$ and $0$, and in the second case this chain can not go through $s$ so the shortest path has length $i_*$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.

    When we refer to an interval $[a,b]$ on the cycle we could be referring to two possible intervals because of the periodicity of the cycle. Define $[a,b]_j$ as the interval with vertex $j$ on the \emph{inside}. Furthermore by $-a$ we mean the vertex $n-a$, as one would expect modulo $n$.

 We will now consider intervals around vertex 0.
    For $l,r\geq 1$ and $l+r\leq n$, define the event ``zeroes patch'' $\mathrm{ZP}^{[-l,r]_0}$ as the event of getting zeroes inside the interval $[-l,r]_0$ but not on the boundary, i.e.
    $$\mathrm{ZP}^{[-l,r]_0} = \NZ{-l} \cap \Z{-l+1} \cap \cdots \cap \Z{0} \cap \cdots \cap \Z{r-1} \cap \NZ{r}$$
    Note that there are $r+l-1$ `zeroes' in this event, so $\P_{J}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{r+l-1-|J|})$ for $J\subseteq[-l,r]_0$ is a lower bound on the order of $p$.\\
    Claim:
    \begin{align*}
        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
        + \mathcal{O}(p^{d(i_*,0)+1-|I|})
    \end{align*}
    If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ and also $\P_{I'}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ so then the claim holds.
    If $-l\in I$ or $r\in I$ (and $-l,r$ are both not $i_*$ because of the previous point) then the probability of $\mathrm{ZP}^{[-l,r]_0}$ is zero for both $I$ and $I'$ so the claim holds.
    If $[-l,r]_0$ has no overlap with $I$ then both sides are also zero so it also holds. We are left with the case where: $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.
    The following diagram illustrates the situation
    \begin{center}
        \includegraphics{diagram_circle_lemma.pdf}
    \end{center}
    Note that by Claim~\ref{claim:eventindependence} we have
    \begin{align*}
        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I\setminus [-l,r]_0}(\NZ{-l},\NZ{r})
    \end{align*}
    We have $i_*\in I \setminus[-l,r]_0$, and $I\cap[-l,r]_0 = I' \cap [-l,r]_0$. Define $J=I\setminus[-l,r]_0$ and $J'=I'\setminus[-l,r]_0$. We have $|J|<|I|$ so we can apply the induction hypothesis to $J$:
    \begin{align*}
        \P_{J}(\NZ{-l},\NZ{r})
        &=
        1
        - \P_{J}(\Z{-l},\NZ{r})
        - \P_{J}(\Z{r})
        \tag{partition of all events} \\
        &=
        1
        - \P_{J'}(\Z{-l},\NZ{r})
        - \P_{J'}(\Z{r}) \\
        &\quad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l), \dist{-l}(i_*,r) \right) +1-|J|})
        + \mathcal{O}(p^{d(i_*,r)+1-|J|}) \\
        &=
        \P_{J'}(\NZ{-l},\NZ{b})
        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|})
    \end{align*}
    Note that the event $\mathrm{ZP}^{[-l,r]_0}$ contains $l+r-1$ zeroes, so $\P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{l+r-1-|I\cap[-l,r]_0|})$. This means
    \begin{align*}
        \P_{I}(\mathrm{ZP}^{[-l,r]_0})
        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0})
        \left( \P_{I' \setminus [-l,r]_0}(\NZ{a},\NZ{b}) + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|}) \right) \\
        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I'\setminus [-l,r]_0}(\NZ{a},\NZ{b}) \\
        &\qquad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J| + l+r-1-|I\cap[-l,r]_0|}) \\
        &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})
    \end{align*}
    Where we used Claim~\ref{claim:eventindependence} again.
    Case separation shows that
    $$\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) + l +r \geq d(i_*,0) + 1$$
    for $l,r\geq 1$ which proves the claim.

    The first equality that we have to prove now follows from the fact that the ``zeroes patch'' events are a partition of $\Z{0}$:
    \begin{align*}
        \P_{I}(\Z{0})
        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
        \P_I(\mathrm{ZP}^{[-l,r]_0})
        \tag{the events are a partition of $\Z{0}$}\\
        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
        \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
        + \mathcal{O}(p^{d(i_*,0)+1-|I|})
        \tag{by claim} \\
        &= \P_{I'}(\Z{0}) + \mathcal{O}(p^{d(i_*,0)+1-|I|})
    \end{align*}
    Similarly, we have
    \begin{align*}
        \P_{I}(\Z{0} , \NZ{s})
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
        \tag{partition of $\Z{0}$}\\
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
        +\mathcal{O}(p^{i_*+1-|I|}) \\
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
        \P_{I\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})
        +\mathcal{O}(p^{i_*+1-|I|})
        \tag{Claim~\ref{claim:eventindependence}}\\
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})
        +\mathcal{O}(p^{i_*+1-|I|})
        \tag{$i_*\in I \setminus[s,r]_0$}\\
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\
        &\qquad +\mathcal{O}(p^{\min\left( \dist{r}(i_*,s) , d(i_*,r)\right)+l+r-|I|})
        +\mathcal{O}(p^{i_*+1-|I|})
        \tag{same argument as before}\\
        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}
        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot
        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\
        &\qquad
        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})
        \tag{case separation}\\
        &= \P_{I'}(\Z{0} , \NZ{s})
        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})
    \end{align*}
    This finishes the proof.
\end{proof}

    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.
    
\begin{comment}
    \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}}
    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.
    %\begin{definition}[Resample sequences]
    %	A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.
    %\end{definition}
    %\begin{definition}[Constrained resample sequence]\label{def:constrainedRes}
    %	Let $C\subseteq[n]$ denote a slot configuration, and let $a\in\{\text{res},\neg\text{res}\}^{n-|C|}$, where the elements correspond to labels ``resampled" vs. ``not resampled" respectively. 
    %	For $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.
    %	We define the set $A^{(C,a)}\subseteq RS$ as the set of resample sequences $(r_\ell)$ such that for all $j$ which has $a_j=\text{res}$ we have that $i_j$ appears in $(r_\ell)$ but for $j'$-s which have $a_{j'}=\neg\text{res}$ we have that $i_{j'}$ never appears in $(r_\ell)$. 
    %\end{definition}    
    \begin{definition}[Conditional expected number of resamples]
    	For a slot configuration $C\subseteq[n]$ and $a\in\{\!\text{ever},\text{ never}\}^{n-|C|}$ we define the event $A^{(C,a)}:=\bigwedge_{j\in[n-|C|]}\{i_j\text{ has }a_j\text{ become }0\text{ before reaching }\mathbf{1}\}$,
    	where $i_j$ is the $j$-th vertex of $[n]\setminus C$.
    	Then we also define
    	$$R^{(C,a)}_b:=\mathbb{E}[\#\{\text{resamplings when started from inital state }b\}|A^{(C,a)}].$$
    \end{definition}     
    
    As in Mario's proof I use the observation that 
    \begin{align*}
    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}}\sum_{a\in\{\!\text{ever},\text{ never}\}^{n-|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)P_{C(f)}(A^{(C,a)})\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\!\text{ever},\text{ never}\}^{n-|C|}} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)P_{C(f)}(A^{(C,a)}), 
    \end{align*}
    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$, while all other location in $[n]\setminus C$ are set to $1$. 
    When we write $R_{C(f)}$ we mean $R_{C(\bar{f})}$, i.e., replace $1'$-s with $1$-s. Since the notation is already heavy we dropped the bar from $f$, as it is clear from the context. Finally by $P_{C(f)}(A^{(C,a)})$ we denote the probability that the event $A^{(C,a)}$ holds.
    
    As in Definition for $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.
    Suppose that $a$ is such that there are two indices $j_1\neq j_2$ such that 
    $a_{j_1}=\text{never}=a_{j_2}$, moreover the sets $\{i_{j_1}+1,\ldots, i_{j_2}-1\}$ and $\{i_{j_2}+1,\ldots, i_{j_1}-1\}$ partition $C$ non-trivially, and we denote by $C_l$,$C_r$ the corresponding partitions. 
    I wanted to prove that
    \begin{equation}\label{eq:conditionalCancellation}
		\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)=0,
    \end{equation}    
    based on the observation that for all $f\in\{0,1'\}^{|C|}$ we have 
    that 
    \begin{equation}\label{eq:keyIndependce}
    R^{{(C,a)}}_{C(f)}(p)=R^{{(C_l,a_l)}}_{C_l(f_l)}(p)+R^{{(C_r,a_r)}}_{C_r(f_r)}(p),
    \end{equation}
    where $f_l\in\{0,1'\}^{|C_l|}$ is defined as taking only the indices (and values) of $f$ corresponding to vertices of $C_l$, also $a_l\in[n-|C_l|]$ is defined such that $a$ and $a_l$ agree on vertices where $a$ is defined, and on the vertices where $a$ is not defined, i.e., the vertices of $C_r$ we define $a_l$ to contain ``never". We define things analogously for $f_r$ and $a_r$. 
    
    The reason why \eqref{eq:keyIndependce} holds is that as before the two halves of the cycle are conditionally independent because neither $i_{j_1}$ nor $i_{j_2}$ can become $0$. To be more precise each resample sequence $\left(C(f)\rightarrow \mathbf{1} \right)\in A^{(C,a)}$ can be uniquely decomposed to resample sequences $\left(C_l(f_l)\rightarrow \mathbf{1}\right)\in A^{(C_l,a_l)}$ and $\left(C_r(f_r)\rightarrow \mathbf{1}\right)\in A^{(C_r,a_r)}$. The sum of probabilities of the set of resample sequences $\{r\}$ which have decomposition $(r_l,r_r)$ have probability which is the product of the probabilities of $r_l$ and $r_r$ as shown in the proof of Claim~\ref{claim:expectationsum}. This proves that the set of all resample sequences $\left(C(f)\rightarrow \mathbf{1}\right)\in A^{(C,a)}$ for our purposes can be viewed as a product set with product probability distribution. Therefore the halves can be treated independently and so the expectation values just add up. 
    
    From here I wanted to mimic Mario's proof:
    \begin{align*}
    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)&=
    \sum_{f_l\in\{0,1'\}^{|C_l|}} \sum_{f_r\in\{0,1'\}^{|C_r|}}  (-1)^{|f_l|+|f_r|}p^{|C_l|+|C_r|} \left( R^{{(C_l,a_l)}}_{C_l(f_l)}(p) + R^{{(C_r,a_r)}}_{C_r(f_l)}(p) \right)\\
    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} R^{{(C_l,a_l)}}_{C_l(f_l)}(p) \sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} \\
    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} R^{{(C_r,a_r)}}_{C_r(f_r)}(p) \sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} \\
    &= 0.
    \end{align*}
    The nasty issue which I did not realise that the missing term $P_{C(f)}(A^{(C,a)})$ is non-constant: even though the event $A^{(C,a)}$ is independent of $f$ the probability $P_{C(f)}(A^{(C,a)})=P_{C(f_l)}(A^{(C_l,a_l)})\cdot P_{C(f_r)}(A^{(C_r,a_r)})$ is not and so the above breaks down.
    
    Observe that if \eqref{eq:conditionalCancellation} would hold for configurations that cut the slot configuration to two halves it would imply that the only non-zero contribution comes from pairs $(C,a)$ such that $C\cup\{i_j:a_j=\text{ever}\}$ is connected. This is because if this set is not connected, then either we can cut $C$ to two halves non-trivially along ``never" vertices, or there is an island of $\text{ever}$ vertices separated from any slots, and therefore from any $0$-s. This latter case has zero contribution since we cannot set these indices to $0$, without reaching them by some resamplings, and thereby building a path of $0$-s leading there.
    
    If $|C\cup\{i_j:a_j=\text{ever}\}|\geq k+1$ then all contribution has a power at least $k+1$ in $p$ since $(C,a)$ requires the prior appearance of at least $k+1$ particles. If $n\geq k+1$ than all $(C,a)$ such that $|C\cup\{i_j:a_j=\text{ever}\}|\leq k$ appears exactly $n$ times, since $(C,a)$ cannot be translationally invariant. Moreover the quantity $R^{{(C,a)}}_{C(f)}(p)$ is independent of $n$ due to the conditioning that every resampling happens on a connected component of length at most $k<n$. This would prove that $a_k^{(n)}$ is constant for $n\geq k+1$. The same arguments would directly translate to the torus and other translationally invariant objects, so we could go higher dimensional as Mario suggested.
    
    Questions:
    \begin{itemize}
    	\item Is it possible to somehow fix this proof?
    	\item In view of this (false) 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}?
    	\item Can we prove the conjectured formula for $a_k^{(3)}$?		
    \end{itemize} 

\begin{comment}
    \subsection{Sketch of the proof of the linear bound \ref{it:const}}
    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.
    \begin{definition}[Resample sequences]
		A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.
    \end{definition}
    \begin{definition}[Constrained resample sequence]\label{def:constrainedRes}
    	Let $C\subseteq[n]$ denote a slot configuration, and let $a\in\{\text{res},\neg\text{res}\}^{n-|C|}$, where the elements correspond to labels ``resampled" vs. ``not resampled" respectively. 
    	For $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.
		We define the set $A^{(C,a)}\subseteq RS$ as the set of resample sequences $(r_\ell)$ such that for all $j$ which has $a_j=\text{res}$ we have that $i_j$ appears in $(r_\ell)$ but for $j'$-s which have $a_{j'}=\neg\text{res}$ we have that $i_{j'}$ never appears in $(r_\ell)$. 
    \end{definition}    
    \begin{definition}[Expected number of resamples]
		For $b\in\{0,1\}^n$ we define 
		$$R_b=\mathbb{E}[\#\{\text{resamplings when started from inital state }b\}],$$
		and for $(C,a)$ as in the previous definition we also define
		$$R^{(C,a)}_b=\mathbb{E}[\#\{\text{resamplings }\in A^{(C,a)} \text{ when started from inital state }b\}].$$
		Here we mean by the latter that after each resampling we check whether the sequence of resamplings so far is in $A^{(C,a)}$, if yes we count it, otherwise we do not count.
    \end{definition}     
    
    As in Mario's proof I use the observation that 
    \begin{align*}
    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}}\sum_{a\in\{\text{res},\neg\text{res}\}^{n-|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\text{res},\neg\text{res}\}^{n-|C|}} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p), 
    \end{align*}
    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$, while all other location in $[n]\setminus C$ are set to $1$. 
	When we write $R_{C(f)}$ we mean $R_{C(\bar{f})}$, i.e., replace $1'$-s with $1$-s. Since the notation is already heavy we dropped the bar from $f$, as it is clear from the context.
    
    As in Definition~\ref{def:constrainedRes} for $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.
    Suppose that $a$ is such that there are two indices $j_1\neq j_2$ such that 
    $a_{j_1}=\neg\text{res}=a_{j_2}$, moreover the sets $\{i_{j_1}+1,\ldots, i_{j_2}-1\}$ and $\{i_{j_2}+1,\ldots, i_{j_1}-1\}$ partition $C$ non-trivially, and we denote by $C_l$,$C_r$ the corresponding partitions. 
    We claim that 
    $$\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)=0.$$
    
	This is based on the observation that that for all $f\in\{0,1'\}^{|C|}$ we have 
    that 
    \begin{equation}\label{eq:keyIndependceWrong}
    R^{{(C,a)}}_{C(f)}(p)=R^{{(C_l,a_l)}}_{C_l(f_l)}(p)+R^{{(C_r,a_r)}}_{C_r(f_r)}(p),
    \end{equation}
    where $f_l\in\{0,1'\}^{|C_l|}$ is defined as taking only the indices (and values) of $f$ corresponding to vertices of $C_l$, also $a_l\in[n-|C_l|]$ is defined such that $a$ and $a_l$ agree on vertices where $a$ is defined, and on the vertices where $a$ is not defined, i.e., the vertices of $C_r$ we define $a_l$ to contain $\neg\text{res}$. We define things analogously for $f_r$ and $a_r$.
    
    The reason why \eqref{eq:keyIndependceWrong} holds is as before that the two halves of the cycle are conditionally independent because neither $i_{j_1}$ nor $i_{j_2}$ are resampled. One could probably also argue similarly as Tom's grid figure shows. 
    From here the proof goes just as in Mario's proof:
    \begin{align*}
    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)&=
    \sum_{f_l\in\{0,1'\}^{|C_l|}} \sum_{f_r\in\{0,1'\}^{|C_r|}}  (-1)^{|f_l|+|f_r|}p^{|C_l|+|C_r|} \left( R^{{(C_l,a_l)}}_{C_l(f_l)}(p) + R^{{(C_r,a_r)}}_{C_r(f_l)}(p) \right)\\
    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} R^{{(C_l,a_l)}}_{C_l(f_l)}(p) \sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} \\
    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} R^{{(C_r,a_r)}}_{C_r(f_r)}(p) \sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} \\
    &= 0.
    \end{align*}
    
    Observe that it implies that the only non-zero contribution comes from pairs $(C,a)$ such that $C\cup\{i_j:a_j=\text{res}\}$ is connected. This is because if this set is not connected, then either we can cut $C$ to two halves non-trivially along $\neg\text{res}$ vertices, or there is an island of $\text{res}$ vertices separated from any slots, and therefore from any $0$-s. This latter case has zero contribution since we cannot resample these indices without first setting them to $0$, but under the conditions they can be never reached by any resampling, therefore they remain $1$ always.
    
    If $|C\cup\{i_j:a_j=\text{res}\}|\geq k+1$ then all contribution has a power at least $k+1$ in $p$ since $(C,a)$ requires the prior appearance of at least $k+1$ particles. If $n\geq k+1$ than all $(C,a)$ such that $|C\cup\{i_j:a_j=\text{res}\}|\leq k$ appears exactly $n$ times, since $(C,a)$ cannot be translationally invariant. Moreover the quantity $R^{{(C,a)}}_{C(f)}(p)$ is independent of $n$ due to the conditioning that every resampling happens on a connected component of length at most $k<n$. This proves that $a_k^{(n)}$ is constant for $n\geq k+1$.
    
    Note that the heart of the proof is \eqref{eq:keyIndependceWrong}, so this is what we should double check.    

	The same arguments directly translate to the torus and other translationally invariant objects, so we can go higher dimensional :-) as Mario suggested.
	
	Questions:
	\begin{itemize}
		\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}?
		\item Can we prove the conjectured formula for $a_k^{(3)}$?		
	\end{itemize} 
\end{comment}
        
\begin{comment}    
    \begin{definition}[Neighborhood]
	   	For the length-$n$ cycle we identify sites with $[n]$. 
	   	For a subset $S\subseteq [n]$ we define the $k$ neighborhood of $S$ as
	   	$N_k(S):=\cup_{s\in S} \{s-k,s-k+1,\ldots,s+k\}$ where numbers are interpreted mod $n$ and we represent the $\equiv 0$ class by $n$).
	\end{definition}
	\begin{definition}[Blocks and Gaps]
	   	For a configuration $C\subseteq [n]$ we call the connected components of $[n]\setminus N_1(C)$ the gaps. We denote by $m_C$ the number of gaps.
	   	We call a non-empty subset $B\subset C$ a block if $N_3(B)\cap C=B$ and $B$ is minimal, i.e., there is no proper subset $\emptyset\neq B'\subsetneq B$ satisfying $N_3(B')\cap C=B'$. 
	   	Observe that whenever $m_C\geq 2$ the number of blocks is the same as the number of gaps.  
    \end{definition}
    \begin{definition}[Crossings]
    	We say that a run (path) of the resampling procedure crosses $i\in[n]$ if there is ever a $0$ in $N_1({i})$ during the run.
    \end{definition}
    \begin{definition}[Enumerating gaps and mid points]
		Let $G_1,G_2,\ldots, G_{m_C}$ be an enumeration of the gaps respecting the cyclic ordering, and let $g_i$ be the middle element of $G_i$, if there are two middle elements we choose the smaller according to the cyclic ordering. (If $m_C=1$ and $G_1=[n]$ let $g_1=1$.)
		If $m_C\geq 2$ then for all $i\in[m_C]$ let $B_i$ be the block between $G_i$ and $G_{i+1}$.
    \end{definition}
    
    As in Mario's proof I use the observation that 
    \begin{align*}
    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_b(p)\\
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p),
    \end{align*}
    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$. 
    For $a\in\{\text{crossed},\text{not crossed}\}^m$ we also introduce the notation $R^a_{C(f)}(p):=\mathbb{E}(\#\{\text{resamples before reaching }\mathbbm{1} \text{ from } C(f)\}|\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)\cdot\mathbb{P}(\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)$, which we define as $0$ if the conditioning event has $0$ probability. 
    Since $$R_{C(f)}(p)=\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}R^a_{C(f)}(p),$$ we can further rewrite the expectation as
    \begin{align*}
	    R^{(n)}(p) &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p).
    \end{align*}
    Suppose that $a$ contains at least two ``not crossed'', the we claim that $\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)=0$. Let $j_1\neq j_2$ be two distinct indexes such that $a_{j_1}$ and $a_{j_2}$ are both saying ``not crossed''. Let $B_l:=B_{j_1}\cup B_{j_1+1}\cup\cdots\cup B_{j_2-1}$ and $B_r:=B_{j_2}\cup B_{j_2+1}\cup\cdots\cup B_{j_1-1}$ (again we interpret indexes mod $m_C$).
    Then we claim that for all $f\in\{0,1'\}^{|C|}$ we have 
    that 
    \begin{equation}\label{eq:keyIndependceOld}
		R^a_{C(f)}(p)=R^a_{B_l(f)}(p)+R^a_{B_r(f)}(p).
    \end{equation} 
    The reason is as before that the halves are independent because neither $g_{j_1}$ nor $g_{j_2}$ is crossed. One could probably similarly prove it as the grid figure shows. 
    From here the proof goes just as in Mario's proof:
    \begin{align*}
    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)&=
    \sum_{f_l\in\{0,1'\}^{|B_l|}} \sum_{f_r\in\{0,1'\}^{|B_r|}}  (-1)^{|f_l|+|f_r|}p^{|B_l|+|B_r|} \left( R^a_{B_l(f)} + R^a_{B_r(f)} \right)\\
    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} R^a_{B_l(f)} \sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} \\
    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} R^a_{B_r(f)} \sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} \\
    &= 0 
    \end{align*}
    From this it follows that the only contribution comes from paths that cross all but one (or all) of the mid gaps. This then implies that it is enough to consider $\mathcal{O}(k)$ length configurations. (We define the length of a configuration $C$ as $n-\max_{j\in[m_C]}|G_j|$.)
    
    Note that the heart of the proof is \eqref{eq:keyIndependceOld}, so this is what we should double check.
    
    In fact I think the independence that we use in \eqref{eq:keyIndependceOld} can be also proven when we define a crossing as crossing the actual point, and not its $1$-neighborhood. It then would make it possible to define blocks as consecutive slacks. Also then we could actually use all points of the gaps not only the mid points. The requirement for the cancellation would be that there are ``not crossed'' labels from at least two distinct gaps. This would probably lead to the optimal $k+1$ bound giving the actual statement \ref{it:const}. 
    
    Speculation: The $n=k$ case would then probably not work because the all $0$ starting configuration is invariant under rotations.
    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}

	\bibliographystyle{alpha}
	\bibliography{Resample.bib}
	
\end{document}