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

\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 the Markov Chain on the finite chain, define

    \begin{align*}

        \P^{[n]}_{\partial=1}(A) &= \P^{[n]}(A \;|\; \text{boundary is initialized to }1)

    \end{align*}

    where the boundary of $[n]$ is site $1$ and site $n$, and the boundary of $[a,b]$ are $a$ and $b$.

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

    \includegraphics{diagram_groups.pdf}

    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

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

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.