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

    \begin{align*}

    \end{align*}

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

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