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

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

\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

\[

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

        &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        - \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{Z}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &= R_{b_1}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &\overset{???}{=} R_{b_1} + R_{b_2} + \mathcal{O}(p^k)

\end{align*}

\end{comment}

Consider the chain (instead of the cycle) for simplicity with vertices identified by $\mathbb{Z}$.

\begin{definition}[Starting state dependent probability distribution.]

	Let $I\subset\mathbb{Z}$ be a finite set of vertices.

    Let $b_I$ be the initial state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $P_I(A)=P_{b_I}(A)$ where the latter is defined in Definition \ref{def:conditionedevents}, i.e. the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$. 

\end{definition}

New:

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

	\begin{align*}

	\end{align*}

	up to any order in $p$.

\end{lemma}

The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.

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

\end{lemma}

\begin{proof}

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

	\begin{align*}

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

	\end{align*}

\end{proof}

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

\end{corollary}

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

 	\end{lemma}   

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

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

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

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

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

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

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

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

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

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

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

 		\end{align*}

 	\end{proof}

	\begin{theorem}

	\end{theorem}

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

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

		\begin{align*}

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

	\end{proof} 	

Old:

The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.

\begin{lemma}\label{lemma:probIndep}

	Suppose we have a finite set $I\subset\mathbb{N}_+$ of vertices.

    Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$. These definitions are illustraded in Figure \ref{fig:lemmaillustration}.

	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{I'}(\Z{0}) = O(p^{I_{\max}-|I'|})$.

\end{lemma}

\begin{proof}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_proborders.pdf}

    \end{center}

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

\end{figure}

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

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

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

	\begin{align*}

		\P^\infty_{I}(\Z{(0)})

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

		\end{align}

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

		\begin{align*}

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

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

		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}

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

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