\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{\patch}[1]{\textsc{Patch}\left(#1\right)}
\newcommand{\patches}[1]{\textsc{Patches}\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 \\
            16& 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 & 1009.38 & \cellcolor{blue!25}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 > \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}
	\colorbox{red}{\ref{it:pos}-\ref{it:geq} is false since $a_{1114}^{(10)}<0$ -- needs to be double checked!}
	I figured this out by observing that $R^{(10)}(p)$ has a pole inside the disk of radius $0.96$. This also means that $R^{(10)}(p)=\sum_{k=0}^{\infty}a_k^{(10)}p^k$ is only true in an analytic sense, since for $p>0.96$ the right hand side does not converge.

	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}
    
    \newpage
    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{General graphs proof}

We consider the following generalization of the Markov Chain.

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain and $\E^G$ to denote expectation values.

\begin{definition}[Events and notation] \label{def:events}
    Let $G=(V,E)$ be a graph. Let $S\subseteq V$ be any subset of vertices.
    \begin{itemize}
        \item Define $\Z{S}$ as the event that \emph{all} vertices in $S$ become zero at any point in time before the Markov Chain terminates.
        \item Define $\NZ{S}$ as the event that \emph{none} of the vertices in $S$ become zero at any point in time before the Markov Chain terminates.
        \item Define for any event $A$:
            \begin{align*}
                \P^{G}_S(A) &= \P^{G}(A \mid \text{All vertices in $S$ get initialized to }1)
            \end{align*}
            The condition does not apply to subsequent resamplings of vertices in $S$, it only specifies the initial assignment.
        \item Define $G\setminus S$ as the graph obtained by removing from $G$ all vertices in $S$ and edges adjacent to $S$.
        \item Define the $d$-neighbourhood $B^G(S;d)$ of $S$ as the set of vertices reachable from $S$ within $d$ steps.
        \item Define the boundary $\overline{\partial} S$ of $S$ as the set of vertices adjacent to $S$, excluding $S$ itself. In other words $\overline{\partial} S = B(S;1) \setminus S$.
    \end{itemize}
\end{definition}

The following Lemma says that if a set $S$ splits the graph in two, then those two parts become independent if the vertices in $S$ never become zero.
\begin{center}
    \includegraphics[scale=0.8]{diagram_splittinglemma.pdf}
\end{center}
\begin{lemma}[Splitting lemma] \label{lemma:splitting}
    Let $G=(V,E)$ be a graph. Let $S,X,Y\subseteq V$ be a partition of the vertices, such that $X$ and $Y$ are disconnected in the graph $G\setminus S$. Furthermore, let $A^X$ and $A^Y$ be any events that depends only on the sites in $X$ and $Y$ respectively. Then we have
    \begin{align*}
        \P^{G}_S(\NZ{S} \cap A^X \cap A^Y)
        &=
        \P^{G\setminus Y}_S(\NZ{S} \cap A^X)
        \; \cdot \;
        \P^{G\setminus X}_S(\NZ{S} \cap A^Y)
    \end{align*}
\end{lemma}

%\newcommand{\initone}[1]{\textsc{InitOne}_#1}
\begin{proof}
    We are considering three different Markov Chains, and the events $\NZ{S}$ in the different parts of the equation are events on different probability spaces. We will keep using the same notation for these events because it should be clear from the context which Markov Chain is being considered. We will consider paths (i.e. resampling sequences) and we will use a superscript to denote to which Markov Chain a path belongs. Let $\xi^G \in \NZ{S}$ be a path of the Markov Chain associated to the resample process on the graph $G$, that satisfies the event $\NZ{S}$. 
    From $\xi^G$ we will now construct paths $\xi^{G\setminus Y} \in \NZ{S}$ and $\xi^{G \setminus X} \in \NZ{S}$ of the other Markov Chains satisfying the corresponding events on those Markov Chains.
    Let us write the path $\xi^G$ as an initialization and a sequence of resamplings:
    \begin{align*}
        \xi^G=\left( (\text{initialize to }b), (z_1, v_1, r_1), (z_2, v_2, r_2), ..., (z_{|\xi^G|}, v_{|\xi^G|}, r_{|\xi^G|}) \right)
    \end{align*}
    where $b\in\{0,1\}^V$ is the initial state, $1 \leq z_i \leq |V|$ denotes the number of zeroes in the state before the $i$th step, $v_i\in V$ denotes the site that was resampled and $r_i\in \{0,1\}^{d(v_i)+1}$ is the result of the resampled bits. Here $d(v_i)$ is the degree of vertex $v_i$. By definition of the resample process, we have
    \begin{align*}
        \P^{G}_S(\xi^G) &=
        \P(\text{initialize }b \mid \text{initialize $S$ to }1)
        \P(\text{pick }v_1 \mid z_1) \P(r_1)
        \P(\text{pick }v_2 \mid z_2) \P(r_2) \cdots \\ 
        &= \frac{(1-p)^{|b|} p^{|V|-|b|}}{(1-p)^{|S|}} \cdot
        \frac{1}{z_1} \P(r_1) \cdot
        \frac{1}{z_2} \P(r_2) \cdots
        \frac{1}{z_{|\xi^G|}} \P(r_{|\xi^G|}) .
    \end{align*}
    Let $b|_{G\setminus X}$ be the restriction of $b$ to $G\setminus X$ and similar for $b|_{G\setminus Y}$.
    To construct $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$, start with $\xi^{G\setminus Y} = \left( (\text{initialize }b|_{G\setminus Y}) \right)$ and $\xi^{G\setminus X} = \left( (\text{initialize }b|_{G\setminus X}) \right)$. For each step $(z_i,v_i,r_i)$ in $\xi^G$ do the following: if $v_i \in X$ then append $(z^{X}_i,v_i,r_i)$ to $\xi^{G\setminus Y}$ and if $v_i \in Y$ then append $(z^{Y}_i,v_i,r_i)$ to $\xi^{G\setminus X}$.
    Here $z^{X}_i$ is the number of zeroes that were in $X$ and $z^{Y}_i$ is the number of zeroes in $Y$. We have $z_i = z^{X}_i + z^{Y}_i$ because $\xi^G\in\NZ{S}$ so there can not be any zero in $S$; they all have to be in $X$ or $Y$. Furthermore, this also makes sure that we always have either $v_i\in X$ or $v_i\in Y$ since only vertices that are zero can be chosen to resample.

    Now $\xi^{G\setminus Y}$ is a valid path of the Markov Chain associated to the graph $G\setminus Y$ (i.e. with vertices $X\cup S$), because in the original path $\xi^G$, all zeroes in $X$ have been resampled by resamplings in $X$. There can not be a vertex $v\in Y$ such that the resampling of $v$ changed a vertex in $X$, since $X$ and $Y$ are only connected through $S$ and we know $\xi^G\in\NZ{S}$.

    Vice versa, any two paths $\xi^{G\setminus Y}\in\NZ{S}$ and $\xi^{G\setminus X}\in\NZ{S}$ also induce a path $\xi^G\in\NZ{S}$ by simply interleaving the resampling positions. Note that $\xi^{G\setminus Y},\xi^{G\setminus X}$ actually induce $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ paths $\xi^G$ because of the possible orderings of interleaving the resamplings in $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$.
    For a fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ we will now show the following:
    \begin{align*}
        \sum_{\substack{\xi^G\in\NZ{S} \text{ s.t.}\\ \xi^G \text{ decomposes into } \xi^{G\setminus Y},\xi^{G\setminus X} }} \P^{G}_S(\xi^G) &=
        \sum_{\text{interleavings of }\xi^{G\setminus Y},\xi^{G\setminus X}} \P(\text{interleaving}) \cdot \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) \\
        &= \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) 
    \end{align*}
    where both sums are over $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ terms.
    This is best explained by an example. Lets consider the following fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ and an example interleaving where we choose vertices from $Y,X,X,Y,\cdots$:
    \begin{align*}
        \xi^{G\setminus Y} &= \left( (\text{initialize to }b^X\;1^S),
        (z^X_1, v^X_1, r^X_1),
        (z^X_2, v^X_2, r^X_2),
        (z^X_3, v^X_3, r^X_3),
        (z^X_4, v^X_4, r^X_4),
        \cdots  \right) \\
        \xi^{G\setminus X} &= \left( (\text{initialize to }1^S\;b^Y),
        (z^Y_1, v^Y_1, r^Y_1),
        (z^Y_2, v^Y_2, r^Y_2),
        (z^Y_3, v^Y_3, r^Y_3),
        (z^Y_4, v^Y_4, r^Y_4),
        \cdots  \right) \\
        \xi^G             &= \big( (\text{initialize to }b^X \; 1^S \; b^Y),
        (z^X_1+z^Y_1, v^Y_1, r^Y_1),
        (z^X_1+z^Y_2, v^X_1, r^X_1), \\
        &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
        (z^X_2+z^Y_2, v^X_2, r^X_2),
        (z^X_3+z^Y_2, v^Y_2, r^Y_2),
        \cdots \big)
    \end{align*}
    Here $b^X\in \{0,1\}^{X}$ and $b^Y\in\{0,1\}^Y$. Since we condition on the event that $S$ is initialized to ones, we know the initial state is of the form $b^X\;1^S$ in $\xi^{G\setminus Y}$. Similarly, since these paths satisfy the $\NZ{S}$ event, we know all the vertices $v_i$ resampled in $\xi^{G\setminus Y}$ are vertices in $X$, and the resampled bits $r_i$ are bits corresponding to vertices in $X$.
    In the newly constructed path $\xi^G$ the number of zeroes is the number of zeroes in $X$ and $Y$ together, so this starts as $z^X_1 + z^Y_1$. Then in this example, after the first step the number of zeroes is $z^X_1+z^Y_2$ since a step of $\xi^{G\setminus X}$ was done (so a vertex in $Y$ was resampled).
    The probability of $\xi^{G\setminus Y}$ is given by
    \begin{align*}
        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) &=
        \P(\text{initialize }b^X\;1^S \mid \text{initialize $S$ to }1)
        \P(\text{pick }v^X_1 \mid z^X_1) \P(r^X_1)
        \P(\text{pick }v^X_2 \mid z^X_2) \P(r^X_2) \cdots \\ 
        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot
        \frac{1}{z^X_1} \P(r^X_1) \cdot
        \frac{1}{z^X_2} \P(r^X_2) \cdots
        \frac{1}{z^X_{|\xi^{G\setminus Y}|}} \P(r^X_{|\xi^{G\setminus Y}|}) .
    \end{align*}
    and similar for $\xi^{G\setminus X}$.
    Instead of choosing a step in $Y,X,X,Y,\cdots$ we could have chosen other orderings. The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $Y,X,X,Y$ in the example above.
    \begin{center}
        \includegraphics{diagram_paths3.pdf}
    \end{center}
    For the labels shown within the grid, define $p_{ij} = \frac{z^X_i}{z^X_i + z^Y_j}$.
    The probability of this particular interleaving $\xi^G$ is given by
    \begin{align*}
        \P^{G}_S(\xi^{G})
        &= (1-p)^{|b^X\; b^Y|} p^{|X\cup Y|-|b^X\;b^Y|} \quad
        \frac{1}{z^X_1+z^Y_1} \P(r^Y_1) \cdot
        \frac{1}{z^X_1+z^Y_2} \P(r^X_1) \cdots \\
        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot (1-p)^{|b^Y|} p^{|Y|-|b^Y|} \\
        &\qquad \cdot
        \frac{z^Y_1}{z^X_1+z^Y_1} \frac{1}{z^Y_1} \P(r^Y_1) \;
        \frac{z^X_1}{z^X_1+z^Y_2} \frac{1}{z^X_1} \P(r^X_1) \;
        \frac{z^X_2}{z^X_2+z^Y_2} \frac{1}{z^X_2} \P(r^X_2)
        \cdots \tag{rewrite fractions}\\
        &=
        \frac{z^Y_1}{z^X_1+z^Y_1} 
        \frac{z^X_1}{z^X_1+z^Y_2} 
        \frac{z^X_2}{z^X_2+z^Y_2} 
        \cdots
        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})
        \tag{definition} \\
        &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \cdots \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})
        \tag{definition of $p_{i,j}$} \\
        &= \P(\text{path in grid}) \; \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})
    \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^{G}_S(\NZ{S} \cap A^X \cap A^Y)
        &= \sum_{\xi^G \in \NZ{S}\cap A^X \cap A^Y} \P^{G}_S(\xi^G) \\
        &= \sum_{\xi^{G\setminus Y} \in \NZ{S}\cap A^X}
           \sum_{\xi^{G\setminus X} \in \NZ{S}\cap A^Y}
            \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot
            \P^{G\setminus X}_S(\xi^{G\setminus X}) \\
        &= \P^{G\setminus Y}_S(\NZ{S} \cap A^X) \; \cdot \; \P^{G\setminus X}_S(\NZ{S} \cap A^Y)
    \end{align*}
\end{proof}

\todo{rewrite from here}
\begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNewGen}
	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:splitting}, 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^{[w,v]}_{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}

	\begin{definition}[Connected patches]
		Let $P\subseteq V$ be a connected component of $G$. We say that $P$ is a patch of a particular run of the process if $P$ is a maximal connected component of the vertices that have ever become $0$ before termination. We denote the set of patches of a run by $\mathcal{P}$. For a patch $P$ let $\patch{P}$ denote the event that one of the patches is equal to $P$. 
		In other words
		\begin{align*}
		\patch{P} := \NZ{\overline{\partial}P} \cap \Z{P}.
		\end{align*}
		For a set of patches $\mathcal{P}$ 	
		\begin{align*}
			\mathcal{P}'\in \mathcal{P} := \bigcup_{P\in \mathcal{P}'}\NZ{\overline{\partial}P} \cap \Z{P}.
		\end{align*}
	\end{definition} 

	We are often going to use the observation that we can partition the event $\Z{v}$ using patches:
	\begin{align*}
	\Z{v} = \dot\bigcup_{P\text{ patch } : 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:probIndepNewGen}
	$\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 form 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:eventindependenceNewGen}}\\
	&=\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:eventindependenceNewGen}}\\
	&=\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:probIndepNewGen}
	$\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:independenetSidesNewGen}	
 		$$\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:eventindependenceNewGen}}\\
 		&=\!\!\!\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:probIndepNewGen}}\\
 		&=\!\!\!\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:eventindependenceNewGen}}\\
 		&=\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)}=\E^{[-m,m]}(\Res{0})+\bigO{p^{n}}$ for all $m\geq n \geq 3$, thus
		$R^{(n)}-R^{(m)}=\bigO{p^{n}}$.
	\end{theorem}
	\begin{proof} In the proof we identify the sites of the $n$-cycle with the$\mod n$ remainder classes.
		\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:eventindependenceNewGen}}\\
			&= \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:independenetSidesNewGen}}\\
			&= \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^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\NZ{w})\!+\!\bigO{p^{n-v-w+1}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNewGen}}\\	
			&= \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^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\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^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P_{v,w}\!\in\!\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNewGen}}\\[-1mm]
			&= \sum_{k=1}^{\infty}\sum_{\underset{|P|<n}{P\text{ patch}:0\in P}}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\[-1mm]
			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:0\in P}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\
			&= \E^{[-m,m]}(\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:eventindependenceNewGen}}\\				
		&= \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:eventindependenceNewGen}}\\
		&= \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:independenetSidesNewGen}}\\
		&= \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:probIndepNewGen}}\\
		&= \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:eventindependenceNewGen}}\\
		&= \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:eventindependenceNewGen}}\\
		&= \E^{[-N,N]}(\Res{1})+\bigO{p^{n}}.
		\end{align*}	
\end{comment}			

~

Questions:
\begin{itemize}
	\item Can we prove some upper bound of the coefficients in the difference, other than they are zero for small powers?
	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?
\end{itemize} 

\newpage
\section{Proving that $a_k^{(k+1)}=a_k^{(n)}$ for all $n>k$}
We consider $R^{(n)}(p)$ as a power series in $p$ and our main aim in this section is to show that $R^{(n)}(p)$ and $R^{(n+k)}(p)$ are the same up to order $n-1$.

The proof will consider variations of the Markov Chain:
\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 only resample itself and its single neighbour so it draws only two new bits. 

We use the notation $\E^{(n)}$,$\E^{[a,b]}$ and $\E^{[n]}$ similarly for denoting expectations.

%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$ and any $v\in[n]$, define
    \begin{align*}
        \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) \\
        \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1) \\
        \P^{[n]}_{b_v=b_w=1}(A) &= \P^{[n]}(A \;|\; v\text{ and }w\text{ are initialized to }1) ,
    \end{align*}
    The last two probabilities are not conditioned on any other bits of the starting state.
\end{definition}
%Note that we have $\P^{(n)}(\start{b}) = (1-p)^{|b|}p^{n-|b|}$ by definition of our Markov Chain.
	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)}=\E^{[-m,m]}(\Res{0})+\bigO{p^{n}}$ for all $m\geq n \geq 3$, thus
		$R^{(n)}-R^{(m)}=\bigO{p^{n}}$.
	\end{theorem}
	\begin{proof} In the proof we identify the sites of the $n$-cycle with the$\mod n$ remainder classes.
		\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^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\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^{[-m,-v]}(\NZ{-v})\P^{[w,m]}(\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^{[-m,m]}(\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^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\[-1mm]
			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:0\in P}\P^{[-m,m]}(\Res{0}\!\geq\! k\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \\
			&= \E^{[-m,m]}(\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}			

~

\newpage
\section{Characterisation of $p_c$}
\textbf{Conjecture} for a fixed $p\in [0,1]$ the following are equivalent:
\begin{enumerate}
	\item $\lim_{n\to\infty}\P^{[-n,n]}_{\overline{\{0\}}}(\Z{\{n\}})>0$
	\item $\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Not reaching the all 1 state})>0$
	\item $\P^{[-\infty,\infty]}(\NZ{\{0\}})>0$
	\item $\P^{[0,\infty]}(\NZ{\{0\}})>0$
	\item $\lim_{n\to\infty}\P^{[0,n]}(\NZ{\{0\}})>0$		
	\item $\exists c,\lambda>0:\P^{[-\infty,\infty]}(\Z{[k]})<ce^{-\lambda k}$
	\item $\exists c,\lambda>0:\mathrm{Cov}^{[-\infty,\infty]}(A,B)<ce^{-\lambda d(A,B)}$
	\item $\exists c,\lambda>0\,\forall n\in\mathbb{N}:\mathrm{Cov}^{[n]}(A,B)<ce^{-\lambda d(A,B)}$	
	\item $R^{(\infty)}<\infty$
\end{enumerate}
\begin{proof}
	$1\Leftrightarrow 2:$
	\begin{align*}
		\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Not reaching the all 1 state})>0
		&=\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\text{Resampling arbitrary far away})>0\\
		&=\P^{[-\infty,\infty]}_{\overline{\{0\}}}\left(\bigcap_{n=1}^{\infty}\Z{\{-n\}}\cup\Z{\{n\}}\right)>0\\
		&=\lim_{n\to\infty}\P^{[-\infty,\infty]}_{\overline{\{0\}}}(\Z{\{-n\}}\cup\Z{\{n\}})>0\\
		&=\lim_{n\to\infty}\P^{[-n,n]}_{\overline{\{0\}}}(\Z{\{-n\}}\cup\Z{\{n\}})>0
	\end{align*}
\end{proof}

    \textbf{New conjecture(s)}: The following statements are equivalent
    \begin{enumerate}
        \item $p<p_c$
        \item (requires continuous time) $\P^{[0,\infty]}(\NZ{0}) > 0$
        \item (requires continuous time) $\P^{[-\infty,\infty]}(\NZ{0}) > 0$
        \item (requires continuous time) $\exists c,\lambda$ such that $\P^{[-\infty,\infty]}(\Z{[0,k]}) \leq c \; e^{-\lambda \; k}$
        \item (requires continuous time) $\exists c,\lambda$ such that $\mathrm{COV}^{[-\infty,\infty]}(A,B) \leq c \; e^{-\lambda \; d(A,B)}$
        \item (requires continuous time) $\E^{(\infty)}(\text{\# resamples of }0) < \infty$
        \item (first lines requires continuous time)
            \begin{align*}
                \P^{[-\infty,\infty]}(\textsc{NonStop})
                &= \P^{[-\infty,\infty]}(\textsc{NonStop} \text{ and unbounded}) \\
                &= \P^{[-\infty,\infty]}(\bigcap_{n=1}^{\infty} \Z{[-n,n]}) \\
                &= \lim_{n\to\infty} \P^{[-\infty,\infty]}(\Z{[-n,n]}) \\
                &\overset{?}{=} \lim_{n\to\infty} \P^{[-n,n]}(\Z{[-n,n]})
            \end{align*}
        \item (does \emph{not} requires continuous time) $\P^{[-\infty,\infty]}(\textsc{NonStop} \mid \text{start with single 0 at 0})$
        \item $\lim_{n\to\infty} \P^{[0,n]}(\Z{n} \mid \text{start with single 0 at 0}) = 0$
        \item $\lim_{n\to\infty} \P^{[0,n]}(\NZ{0}) > 0$ (note: symbolically computable for small n)
        \item $\lim_{n\to\infty} \P^{[0,n]}(\Z{0}) < 1$ (note: symbolically computable for small n)
        \item For the non-terminating process (resample a random 1 in case there are only 1s available), the number of zeroes in the stationary distribution is $o(n)$.
    \end{enumerate}


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