AENC/resampling_chain Changeset - 15d6625cf194 · Centrum Wiskunde & Informatica (CWI)

@@ -191,30 +191,6 @@

	\label{fig:coeffs_conv_radius}

	\end{figure}

    \newpage

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

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

@@ -274,142 +250,155 @@

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

\section{General graphs proof}

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 consider the following generalization of the Markov Chain.

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

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.

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

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

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

%\begin{figure}

%	\begin{center}

%    	\includegraphics{diagram_groups.pdf}

%    \end{center}

%    \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependence}. Here $b_1,b_2\in\{0,1\}^n$ are bitstrings such that all zeroes of $b_1$ and all zeroes of $b_2$ are separated by two indices $v,w$.}

%\end{figure}

\begin{wrapfigure}[7]{r}{0.25\textwidth} % The first [] argument is number of lines that are narrowed

    \centering

    \includegraphics{diagram_groups.pdf}

    \caption{\label{fig:separatedgroups} Lemma \ref{lemma:eventindependence}.}

\end{wrapfigure}

The following lemma considers two vertices $v,w$ that are never ``crossed'' so that two halves of the cycle become independent.\begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}

    Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two separated groups of zeroes 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

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^{(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^{G}_S(\NZ{S} \cap A^X \cap A^Y)

&=

        \P^{(n)}_{b_1}(A_1 \mid \mathrm{NZ}^{(v,w)})

        \P^{G\setminus Y}_S(\NZ{S} \cap A^X)

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

        \P^{G\setminus X}_S(\NZ{S} \cap A^Y)

    \end{align*}

    %up to any order in $p$.

\end{lemma}

%\newcommand{\initone}[1]{\textsc{InitOne}_#1}

\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

    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^{(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|}) .

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

    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:

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

        \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_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$:

    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_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)

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

    The probability of $\xi_1$, started from $b_1$, is given by

    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^{(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|}) .

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

    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_paths2.pdf}

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

    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^{(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')

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

        \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^{(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]

        \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^{(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).

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

    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.

\end{proof}

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

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

@@ -435,7 +424,7 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t

        \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

    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)

&=

@@ -473,12 +462,15 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t

\end{proof}

	\begin{definition}[Connected patches]

		Let $P$ be an interval $[a,b]$. 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 $P\in \mathcal{P}$ denote the event that one of the patches is equal to $P$.

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

		P\in\mathcal{P} := \NZ{a-1} \cap \Z{a} \cap \Z{a+1} \cap \cdots \cap \Z{b-1} \cap \Z{b} \cap \NZ{b+1} .

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

		(In the extreme case when $P$ covers the whole cycle $[n]$, then instead $P\in\mathcal{P}:= \bigcap_{v\in[n]}\Z{v}$.)

	\end{definition}

	We are often going to use the observation that we can partition the event $\Z{v}$ using patches:

@@ -487,7 +479,7 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t

	\end{align*}

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

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

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

@@ -498,21 +490,21 @@ The intuition of the following lemma is that the far right can only affect the z

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

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

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

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

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

@@ -535,7 +527,7 @@ The intuition of the following lemma is that the far right can only affect the z

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

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

@@ -547,11 +539,11 @@ The intuition of the following lemma is that the far right can only affect the z

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

 		+\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:eventindependenceNew}}\\

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

@@ -573,11 +565,11 @@ The intuition of the following lemma is that the far right can only affect the z

			&= \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^{[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:eventindependenceNew}}\\[-1mm]

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

@@ -592,14 +584,14 @@ The intuition of the following lemma is that the far right can only affect the z

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

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

@@ -608,269 +600,37 @@ The intuition of the following lemma is that the far right can only affect the z

Questions:

\begin{itemize}

	\item Can we generalise the proof to other translationally invariant spaces, like the torus?

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

	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

\end{itemize}

	%I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.

\newpage

\section{General graphs proof}

We consider the following generalization of the Markov Chain.

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

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.

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.

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

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

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

%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^{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)

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

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

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

@@ -893,7 +653,7 @@ The intuition of the following lemma is that the far right can only affect the z

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

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

@@ -905,11 +665,11 @@ The intuition of the following lemma is that the far right can only affect the z

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

 		+\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:eventindependenceNewGen}}\\

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

@@ -931,11 +691,11 @@ The intuition of the following lemma is that the far right can only affect the z

			&= \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^{[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:eventindependenceNewGen}}\\[-1mm]

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

@@ -950,26 +710,20 @@ The intuition of the following lemma is that the far right can only affect the z

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

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

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{Characterisation of $p_c$}

\textbf{Conjecture} for a fixed $p\in [0,1]$ the following are equivalent:

@@ -990,766 +744,34 @@ Questions:

		\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]}(\Z{\{-n\}}_{\overline{\{0\}}}\cup\Z{\{n\}})>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}

\newpage

\section{Quasiprobability method}

Let us first introduce notation for paths of the Markov Chain

\begin{definition}[Paths]

	We define a \emph{path} of the Markov Chain as a sequence of states and resampling choices $\xi=((b_0,r_0),(b_1,r_1),...,(b_k,r_k)) \in (\{0,1\}^n\times[n])^k$ indicating that at time $t$ Markov Chain was in state $b_t\in\{0,1\}^n$ and then resampled site $r_t$. We denote by $|\xi|$ the length $k$ of such a path, i.e. the number of resamples that happened, and by $\mathbb{P}[\xi]$ the probability associated to this path.

	We denote by $\paths{b}$ the set of all valid paths $\xi$ that start in state $b$ and end in state $\mathbf{1} := 1^n$.

\end{definition}

We can write the expected number of resamplings per site $R^{(n)}(p)$ as

\begin{align}

R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1\}^{n}} \rho_b \; R_b(p) \label{eq:originalsum} ,

\end{align}

where $R_b(p)$ is the expected number of resamplings when starting from configuration $b$

\begin{align*}

R_b(p) &= \sum_{\xi \in \paths{b}} \mathbb{P}[\xi] \cdot |\xi| .

\end{align*}

We consider $R^{(n)}(p)$ as a power series in $p$ and show that many terms in (\ref{eq:originalsum}) cancel out if we only consider the series up to some finite order $p^k$. The main idea is that if a path samples a $0$ then $\mathbb{P}[\xi]$ gains a factor $p$ so paths that contribute to $p^k$ can't be arbitrarily long.\\

To see this, we split the sum in (\ref{eq:originalsum}) into parts that will later cancel out. The initial probabilities $\rho_b$ contain a factor $p$ for every $0$ and a factor $(1-p)$ for every $1$. When expanding this product of $p$s and $(1-p)$s, we see that the $1$s contribute a factor $1$ and a factor $(-p)$ and the $0$s only give a factor $p$. We want to expand this product explicitly and therefore we no longer consider bitstrings $b\in\{0,1\}^n$ but bitstrings $b\in\{0,1,1'\}^n$. We view this as follows: every site can have one of $\{0,1,1'\}$ with `probabilities' $p$, $1$ and $-p$ respectively. A configuration $b=101'1'101'$ now has probability $\rho_{b} = 1\cdot p\cdot(-p)\cdot(-p)\cdot 1\cdot p\cdot(-p) = -p^5$ in the starting state $\rho$. It should not be hard to see that we have

\begin{align*}

R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_{b} \; R_{\bar{b}}(p) ,

\end{align*}

where $\bar{b}$ is the bitstring obtained by changing every $1'$ in it back to a $1$. It is simply the same sum as (\ref{eq:originalsum}) but now every factor $(1-p)$ is explicitly split into $1$ and $(-p)$.

Some terminology: for any configuration we call a $0$ a \emph{particle} (probability $p$) and a $1'$ an \emph{antiparticle} (probability $-p$). We use the word \emph{slot} for a position that is occupied by either a paritcle or antiparticle ($0$ or $1'$). In the initial state, the probability of a configuration is given by $\pm p^{\mathrm{\#slots}}$ where the $\pm$ sign depends on the parity of the number of antiparticles.

We can further rewrite the sum over $b\in\{0,1,1'\}^n$ as a sum over all slot configurations $C\subseteq[n]$ and over all possible fillings of these slots.

\begin{align*}

R^{(n)}(p) &= \frac{1}{n} \sum_{C\subseteq[n]} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,

\end{align*}

where $C(f)\in\{0,1,1'\}^n$ denotes a configuration with slots on the sites $C$ filled with (anti)particles described by $f$. The non-slot positions are filled with $1$s.

\begin{definition}[Diameter and gaps] \label{def:diameter} \label{def:gaps}

	For a subset $C\subseteq[n]$, we define the \emph{diameter} $\diam{C}$ to be the minimum size of an integer interval $I$ containing $C$. Here we consider both $C$ and the interval modulo $n$. In other words $\diam{C} = \min\{ j \vert \exists i : C\subseteq [i,i+j-1] \}$. We define the \emph{gaps} of $C$, as $I\setminus C$ and denote this by $\gaps{C}$. Note that $\diam{C} = |C| + |\gaps{C}|$.  Define $\maxgap{C}$ as the size of the largest connected component of $\gaps{C}$. Figure \ref{fig:diametergap} illustrates these concepts with a picture.

\end{definition}

\begin{figure}

	\begin{center}

		\includegraphics{diagram_gap.pdf}

	\end{center}

	\caption{\label{fig:diametergap} Illustration of Definition \ref{def:diameter}. A set $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 positions is shown by the red dots. The smallest interval containing $C$ is $[1,9]$, so the diameter is $\diam{C}=9$. The blue squares denote the set $\gaps{C} = \{3,5,6,8\}$. The dotted line at the top depicts the rest of the cycle which may be much larger. The largest gap of $C$ is $\maxgap{C}=2$ which is the largest connected component of $\gaps{C}$.}

\end{figure}

\begin{claim}[Strong cancellation claim] \label{claim:strongcancel}

	The lowest order term in

	\begin{align*}

	\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,

	\end{align*}

	is $p^{\diam{C}}$ when $n$ is large enough. All lower order terms cancel out.

\end{claim}

Example: for $C_0=\{1,2,4,7,9\}$ (the configuration shown in Figure \ref{fig:diametergap}) we computed the quantity up to order $p^{20}$ in an infinite system:

\begin{align*}

\sum_{f\in\{0,1'\}^{|C_0|}} \rho_{C_0(f)} R_{C_0(f)} &= 0.0240278 p^{9} + 0.235129 p^{10} + 1.24067 p^{11} + 4.71825 p^{12} \\

&\quad + 14.5555 p^{13} + 38.8307 p^{14} + 93.2179 p^{15} + 206.837 p^{16}\\

&\quad + 432.302 p^{17} + 862.926 p^{18} + 1662.05 p^{19} + 3112.9 p^{20} + \mathcal{O}(p^{21})

\end{align*}

and indeed the lowest order is $\diam{C}=9$.

A weaker version of the claim is that if $C$ contains a gap of size $k$, then the sum is zero up to and including order $p^{|C|+k-1}$.

\begin{claim}[Weak cancellation claim] \label{claim:weakcancel}

	For $C\subseteq[n]$ a configuration of slot positions, the lowest order term in

	\begin{align*}

	\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,

	\end{align*}

	is at least $p^{|C|+\maxgap{C}}$ when $n$ is large enough. All lower order terms cancel out.

\end{claim}

This weaker version would imply \ref{it:const} but for $\mathcal{O}(k^2)$ as opposed to $k+1$.

\newpage

The reason that claim \ref{claim:strongcancel} would prove \ref{it:const} is the following: to know the value of $a_k^{(n)}$, for any $n\geq k+1$ it is enough to look at configurations $C$ with diameter at most $k$, since larger configurations do not contribute to $a_k^{(n)}$.

For a starting state $b\in\{0,1\}^n$ that \emph{does} give a nonzero contribution, you can take that same starting configuration and translate it to get $n$ other configurations that give the same contribution. (An exception is a starting state like $1010101010...$ which you can only translate twice, but we only have to consider configurations with small diameter, in which case you can make exactly $n$ translations.)

Therefore the coefficient in the expected number of resamplings is a multiple of $n$ which Andr\'as already divided out in the definition of $R^{(n)}(p)$. To show \ref{it:const} we argue that this is the \emph{only} dependency on $n$. This is because there are only finitely many (depending on $k$ but not on $n$) configurations where the $k$ slots are nearby regardless of the value of $n$. So there are only finitely many nonzero contributions after translation symmetry was taken out. For example, when considering all starting configurations with 5 slots one might think there are $\binom{n}{5}$ configurations to consider which would be a dependency on $n$ (more than only the translation symmetry). But since most of these configurations have a diameter larger than $k$, they do not contribute to $a_k$. Only finitely many do and that does not depend on $n$.

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

\newpage

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

By $R_{101}$ we denote $R_b(p)$ for a $b$ that consists of only $1$s except for a single zero. We compute $R_{101}$ up to second order in $p$. This requires the following transitions.

\begin{align*}

\framebox{$1 0 1$} &\to \framebox{$1 1 1$} & (1-p)^3 = 1-3p+3p^2-p^3\\

\hline

\framebox{$1 0 1$} &\to

\begin{cases}

\framebox{$0 1 1$}\\

\framebox{$1 0 1$}\\

\framebox{$1 1 0$}

\end{cases}

& 3p(1-p)^2 = 3p-6p^2+3p^3\\

\hline

\framebox{$1 0 1$} &\to \framebox{$0 1 0$} & p^2(1-p) = p^2-p^3\\

\framebox{$1 0 1$} &\to

\begin{cases}

\framebox{$1 0 0$}\\

\framebox{$0 0 1$}

\end{cases}

& 2p^2(1-p) = 2p^2 - 2p^3\\

\hline

\framebox{$1 0 1$} &\to \framebox{$0 0 0$} & p^3

\end{align*}

With this we can write a recursive formula for the expected number of resamples from $101$:

\begin{align*}

R_{101} &= (1-3p+3p^2 - p^3)(1) + (3p -6p^2 +3p^3) (1+R_{101}) \\

&\quad + (p^2 - p^3) (1+R_{10101}) + (2p^2-2p^3) (1+R_{1001}) + p^3(1+R_{10001}) \\

&= 1 + 3 p + 7 p^2 + 14.6667 p^3 + 29 p^4 + 55.2222 p^5 + 102.444 p^6 + 186.36 p^7 \\

&\quad + 333.906 p^8 + 590.997 p^9 + 1035.58 p^{10} + 1799.39 p^{11} + 3104.2 p^{12} \\

&\quad+ 5322.18 p^{13} + 9075.83 p^{14} + 15403.6 p^{15} + 26033.4 p^{16} + 43833.5 p^{17} \\

&\quad+ 73555.2 p^{18} + 123053 p^{19} + 205290 p^{20} + 341620 p^{21} + 567161 p^{22} \\

&\quad+ 939693 p^{23} + 1.5537\cdot10^{6} p^{24} + 2.56158\cdot10^{6} p^{25} + \mathcal{O}(p^{26})

\end{align*}

where the recursion steps were done with a computer for an infinite line (or a cirlce where $n$ is assumed to be much larger than the largest power of $p$ considered).

Note: in the first line at the second term it uses that with probability $(3p-6p^2 + 3p^3)$ the state goes to $\framebox{$101$}$ and then the expected number of resamplings is $1+R_{101}$. Note that the actual term in the recursive formula should be

$$(3p-6p^2+3p^3)\cdot\left( \sum_{\xi\in\paths{101}} \mathbb{P}[\xi] \cdot \left( 1 + |\xi|\right) \right) = (3p-6p^2+3p^3)\left( p_\mathrm{tot} + R_{101} \right)$$

where $p_\mathrm{tot} := \sum_{\xi\in\paths{b}} \mathbb{P}[\xi]$. However, since the state space is finite (for finite $n$) and there is always a non-vanishing probability to go to $\mathbf{1}$, we know that $p_\mathrm{tot}=1$, i.e. the process terminates almost surely.

\newpage

\subsection{Weak cancellation proof}

Here we prove claim \ref{claim:weakcancel}, the weaker version of the claim. We require the following definition

\begin{definition}[Path independence] \label{def:independence}

	We say two paths $\xi_i\in\paths{b_i}$ ($i=1,2$) of the Markov Chain are \emph{independent} if $\xi_1$ never resamples a site that was ever zero in $\xi_2$ and the other way around. It is allowed that $\xi_1$ resamples a $1$ to a $1$ that was also resampled from $1$ to $1$ by $\xi_2$ and vice versa. If the paths are not independent then we call the paths \emph{dependent}.

\end{definition}

\begin{definition}[Path independence - alternative] \label{def:independence2}

	Equivalently, on the infinite line $\xi_1$ and $\xi_2$ are independent if there is a site `inbetween' them that was never zero in $\xi_1$ and never zero in $\xi_2$. On the cycle $\xi_1$ and $\xi_2$ are independent if there are \emph{two} sites inbetween them that are never zero.

\end{definition}

\begin{claim}[Sum of expectation values] \label{claim:expectationsum}

	When $b=b_1\land b_2\in\{0,1\}^n$ is a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes with $k$ $1$s inbetween the groups, then we have $R_b(p) = R_{b_1}(p) + R_{b_2}(p) + \bigO{p^{k}}$ where $b_1$ and $b_2$ are the configurations where only one of the groups is present and the other group has been replaced by $1$s. To be precise, the sums agree up to and including order $p^{k-1}$.

\end{claim}

\textbf{Example}: For $b_1 = 0111111$ and $b_2 = 1111010$ we have $b=0111010$ and $k=3$. The claim says that the expected time to reach $\mathbf{1}$ from $b$ is the time to make the first group $1$ plus the time to make the second group $1$, as if they are independent. Simulation shows that

\begin{align*}

R_{b_1} &= 1 + 3p + 7p^2 + 14.67p^3 + 29p^4 + \mathcal{O}(p^5)\\

R_{b_2} &= 2 + 5p + 10.67p^2 + 21.11p^3+40.26p^4 + \mathcal{O}(p^5)\\

R_{b} &= 3 + 8p + 17.67p^2 + 34.78p^3+65.27p^4 + \mathcal{O}(p^5)\\

R_{b_1} + R_{b_2} &= 3 + 8p + 17.67p^2+35.78p^3 + 69.26p^4 +\mathcal{O}(p^5)

\end{align*}

and indeed the sums agree up to order $p^{k-1}=p^2$. When going up to order $p^{k}$ or higher, there will be terms where the groups interfere so they are no longer independent.

\begin{proof}

	Consider a path $\xi_1\in\paths{b_1}$ and a path $\xi_2\in\paths{b_2}$ such that $\xi_1$ and $\xi_2$ are independent (Definition \ref{def:independence} or \ref{def:independence2}). The paths $\xi_1,\xi_2$ induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ different paths of total length $|\xi_1|+|\xi_2|$ in $\paths{b_1\land b_2}$. In the sums $R_{b_1}$ and $R_{b_2}$, the contribution of these paths are $\mathbb{P}[\xi_1]\cdot |\xi_1|$ and $\mathbb{P}[\xi_2]\cdot |\xi_2|$. The next diagram shows how these $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths contribute to $R_{b_1\land b_2}$. Point $(i,j)$ in the grid indicates that $i$ steps of $\xi_1$ have been done and $j$ steps of $\xi_2$ have been done. At every point (except the top and right edges of the grid) one has to choose between doing a step of $\xi_1$ or a step of $\xi_2$. The number of zeroes in the current state determine the probabilities with which this happens (beside the probabilities associated to the two original paths already). The grid below shows that at a certain point one can choose to do a step of $\xi_1$ with probability $p_i$ or a step of $\xi_2$ with probability $1-p_i$. These $p_i$ could in principle be different at every point in this grid. The weight of such a new path $\xi\in\paths{b_1\land b_2}$ is $p_\mathrm{grid}\cdot\mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]$ where $p_\mathrm{grid}$ is the weight of the path in the diagram. By induction one can show that the sum over the $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ different terms $p_\mathrm{grid}$ is $1$.

	\begin{center}

		\includegraphics{diagram_paths.pdf}

	\end{center}

	Hence the contribution of all $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths together to $R_{b_1\land b_2}$ is given by

\[

	\mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]\cdot(|\xi_1|+|\xi_2|) = \mathbb{P}[\xi_2]\cdot\mathbb{P}[\xi_1]\cdot|\xi_1| \;\; + \;\; \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2]\cdot|\xi_2|.

\]

	Ideally we would now like to sum this expression over all possible paths $\xi_1,\xi_2$ and use $p_\mathrm{tot}:=\sum_{\xi\in\paths{b_i}} \mathbb{P}[\xi] = 1$ (which also holds up to arbitrary order in $p$). The above expression would then become $R_{b_1} + R_{b_2}$. However, not all paths in the sum would satisfy the independence condition so it seems we can't do this. We now argue that it works up to order $p^{k-1}$.

	For all $\xi\in\paths{b_1\land b_2}$ we have that \emph{either} $\xi$ splits into two independent paths $\xi_1,\xi_2$ as above, \emph{or} it does not. In the latter case, when $\xi$ can not be split like that, we know $\mathbb{P}[\xi]$ contains a power $p^k$ or higher because there is a gap of size $k$  and the paths must have moved at least $k$ times `towards each other' (for example one path moves $m$ times to the right and the other path moves $k-m$ times to the left). So the total weight of such a combined path is at least order $p^k$. Therefore we have

\[

	R_{b_1\land b_2} = \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1| + \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_1]\mathbb{P}[\xi_2]|\xi_2| + \sum_{\mathclap{\xi\;\mathrm{dependent}}} \mathbb{P}[\xi]|\xi|.

\]

	where last sum only contains only terms of order $p^{k}$ or higher. Now for the first sum, note that

\[

	\sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|

	= \sum_{\xi_1\in\paths{b_1}} \sum_{\substack{\xi_2\in\paths{b_2}\\ \text{independent of }\xi_1}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|

\]

	where the sum over independent paths could be empty for certain $\xi_1$. Now we replace this last sum by a sum over \emph{all} paths $\xi_2\in\paths{b_2}$. This will change the sum but only for terms where $\xi_1,\xi_2$ are dependent. For those terms we already know that $\mathbb{P}[\xi_1]\mathbb{P}[\xi_2]$ contains a factor $p^k$ and hence we have

	\begin{align*}

	\sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|

	&= \sum_{\xi_1\in\paths{b_1}} \sum_{\xi_2\in\paths{b_2}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\

	&= \sum_{\xi_1\in\paths{b_1}} \mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\

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

	\end{align*}

	we can do the same with the second term and this proves the claim.

\end{proof}

~\\

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

\begin{align*}

\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}

&= \sum_{a\in\{0,1'\}^l} \sum_{b\in\{0,1'\}^r} (-1)^{|a|+|b|}p^{r+l} \left( R_{C(a)} + R_{C(b)} + \mathcal{O}(p^k) \right) \\

&=\;\;\; p^{r+l}\sum_{a\in\{0,1'\}^l} (-1)^{|a|} R_{C(a)} \sum_{b\in\{0,1'\}^r} (-1)^{|b|} \\

&\quad + p^{r+l}\sum_{b\in\{0,1'\}^r} (-1)^{|b|} R_{C(b)} \sum_{a\in\{0,1'\}^l} (-1)^{|a|}

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

&= 0 + \mathcal{O}(p^{|C|+k})

\end{align*}

where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$.

\begin{comment}

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

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

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

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

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

\end{lemma}

\begin{proof}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_proborders.pdf}

    \end{center}

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

\end{figure}

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

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

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

	\begin{align*}

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

		&=\sum_{k=1}^{\infty}\P^\infty(\Z{(0)}_k) \tag{the events are a partition}\\

        &=\sum_{k\in \mathbb{N}\setminus I}\P^\infty(\Z{(0)}_k) \tag{$\mathbb{\P^\infty}(A_k)=0$ for $k\in I$}\\

        &=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\

        &=\sum_{k\in I_{><}}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})

		\tag{$k<I_{\min}\Rightarrow \P^\infty_{I_{<k}}(\Z{(0)}_k)=0$}\\

        &=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})

		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\

		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \left(\P^\infty_{I'_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}-k+1-|I_{>k}|})\right) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{by induction, since for $k>I_{\min}$ we have $|I_{<k}|<|I|$}\\

		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})

		\tag{as $\P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{k-|I'_{<k}|})$}\\

		&=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\

		&=\sum_{k\in\mathbb{N}\setminus I'}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\

		&=\P^\infty_{I'}(\Z{(0)}) +\mathcal{O}(p^{I_{\max}-|I'|})	\tag{analogously to the beginning}

	\end{align*}

\end{proof}

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

	Suppose $I,J\subset\mathbb{N}_+$ are finite sets of vertices, and let $m=\min(\Delta(I,J))$.

	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{J}(\Z{0}) = O(p^{|[m]\cap I\cap J|})$.

\end{corollary}

	%The main insight that Lemma~\ref{lemma:probIndep} gives is that if we separate the slots to two halves, in order to see the cancellation of the contribution of the expected resamples on the right, we can simply pair up the left configurations by the particle filling the leftmost slot. And similarly for cancelling the left expectations we pair up right configurations based on the rightmost filling.

	%Also this claim finally ``sees'' how many empty places are between slots. These properties make it possible to use this lemma to prove the sought linear bound. We show it for the infinite chain, but with a little care it should also translate to the cycle.

\begin{definition}[Connected patches]

	Let $\mathcal{P}\subset 2^{\mathbb{Z}}$ be a finite system of finite subsets of $\mathbb{Z}$. We say that the patch set of a resample sequence is $\mathcal{P}$,

	if the connected components of the vertices that have ever become $0$ are exactly the elements of $\mathcal{P}$. We denote by $A^{(\mathcal{P})}$ the event that the set of patches is $\mathcal{P}$. For a patch $P$ let $A^{(P)}=\bigcup_{\mathcal{P}:P\in \mathcal{P}}A^{(\mathcal{P})}$ denote the event that one of the patches is equal to $P$ but there can be other patches as well.

	As a shorthand we are going to use the notation $P\in \mathcal{P}$ for the event $A^{(P)}$.

\end{definition}

\begin{definition}[Conditional expectations]

	Let $S\subset\mathbb{Z}$ be a finite slot configuration, and for $f\in\{0,1'\}^{|S|}$ let $I:=S(f)$ be the set of vertices filled with a particle (i.e. $1'$).

	Then we define

	$$R_I:=\mathbb{E}[\#\{\text{resamplings when started from inital state }I\}],$$

	and similarly for a patch $P$ we define

	$$R^{(P)}_I:=\mathbb{E}[\#\{\text{resamplings inside }P\text{ when started from inital state }I\}|A^{(P)}].$$

\end{definition}

 	\begin{lemma}Suppose $I\subseteq [k]$, then on the infinite chain

		$$\P^\infty_I(\Z{1}\cap \Z{k})=\P^\infty_I(\Z{1})\P^\infty_I(\Z{k})+\mathcal{O}(p^{k-|I|}).$$

	\end{lemma}

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

	$$\P^\infty_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1})\P^\infty_I(\NZ{k})+\mathcal{O}(p^{k-|I|}).$$

	\begin{proof}

		We proceed by induction on $|I|$. For $|I|=0$ the statement is trivial.

		Now observe that:

		$$\P^\infty_I(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^\infty_I(P\in\mathcal{P})$$

		$$\P^\infty_I(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^\infty_I(P\in\mathcal{P})$$

		Suppose we proved the statement for all $\ell< |I|$, then we proceed using induction similarly to the above (let us use the notation $>I<:=I\cap \overline{P_l}\cap \overline{P_r}$ for simplicity)

		\begin{align*}

		&\P^\infty_I(\Z{1}\cap \Z{k})=\\

		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_I(P_l,P_r\in\mathcal{P})

		+\sum_{P\text{ patch}\,:\,1,k\in P}\P^\infty_I(P\in\mathcal{P})\\

		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_I(P_l,P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{>I<}(\NZ{P_l^{\max}+1}\cap \NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{\text{induction}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{> I <}(\NZ{P_l^{\max}+1})\P^\infty_{> I <}(\NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Corrolary~\ref{cor:probIndep}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

		\P^\infty_{I\setminus P_l}(\NZ{P_l^{\max}+1})\P^\infty_{I\setminus P_r}(\NZ{P_r^{\min}-1})

		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

		\P^\infty_{I}(P_l\in\mathcal{P})

		\P^\infty_{I}(P_r\in\mathcal{P})

		+\mathcal{O}(p^{k-|I|})\\

		&=\left(\sum_{P_l\text{ patch}\,:\,1\in P_l}\P^\infty_{I}(P_l\in\mathcal{P})\right)

		\left(\sum_{P_r\text{ patch}\,:\,k\in P_r}\P^\infty_{I}(P_r\in\mathcal{P})\right)

		+\mathcal{O}(p^{k-|I|})\\

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

		+\mathcal{O}(p^{k-|I|}).

		\end{align*}

	\end{proof}

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

		Let $k>0$ and $d:=\lfloor\frac{k}{2}\rfloor$, then

		\begin{align*}

		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

		=\left(\sum_{\underset{|S|<\infty}{S\subseteq \mathbb{N}_+}}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!\!2}

		+\mathcal{O}(p^{d}).

		\end{align*}

	\end{corollary}

	(Question: is the above is true with $d=k$?)

	\begin{proof}

		Let $[-d]:=\{k-d+1,\ldots, k\}$ and $[\pm d]:=[d]\cup [-d]$. By the above statement we know that

		\begin{align}\label{eq:intervalIndep}

		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

		=\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\bigO{p^{k}}.

		\end{align}

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

		\begin{align*}

		&\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\bigO{p^{k}}\\

		&=\sum_{f_{\overline{s}}\in\{0,1'\}^{|S|-1}}\rho_{S\setminus\{s\}(f_{\overline{s}})} \left(p\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{k})-p\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{k})\right)\\

		&=\mathcal{O}(p^{d}). \tag{by Corollary~\ref{cor:probIndep}}

		\end{align*}

		Therefore we can see that

		\begin{align*}

		\eqref{eq:intervalIndep}&=\sum_{S\subseteq [\pm d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{d})\\

		&=\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\sum_{S'\subseteq [d]}\sum_{f'\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\rho_{S'(f')}\P^\infty_{S'(f')}(\NZ{k})+\mathcal{O}(p^{d}) \tag{Corollary \ref{cor:probIndep}}\\

		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)

		\left(\sum_{S'\subseteq [-d]}\sum_{f'\in\{0,1'\}^{|S'|}}\rho_{S'(f')} \P^\infty_{S'(f')}(\NZ{k})\right)

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

		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!2}

		+\mathcal{O}(p^{d})\tag{by symmetry}\\

		&=\left(\sum_{\underset{|S|<\infty}{S\subseteq \mathbb{N}_+}}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!2}

		+\mathcal{O}(p^{d}).\tag{Corollary \ref{cor:probIndep}}

		\end{align*}

	\end{proof}

	\begin{remark}\label{rem:cycleContained}

		For all $n\geq k$ and $I\subseteq [k]$ we have that

		$$\P^n_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1}\cap \NZ{k}).$$

	\end{remark}

	\begin{theorem}

		Suppose $n,m\geq 2k$, then $R^{(n)}-R^{(m)}=\bigO{p^{k}}$.

	\end{theorem}

	\begin{proof}

		\begin{align*}

		R^{(n)} &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}\\

		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} R_{S(f)}\\

		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \sum_{v\in[n]}\sum_{t=1}^{\infty}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step})\\

		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step and }P\text{ is a patch})\\

		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}

		\rho_{S(f)} \sum_{P\text{ patch}} R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\

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

		\rho_{S(f)}  R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) + \bigO{p^{k}} \tag{by translation symmetry}\\

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

		\rho_{S(f)}  R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \bigO{p^{k}}  \tag{by Lemma~\ref{claim:eventindependence}}\\

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

		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})

		\sum_{S'\subseteq \overline{P}}\sum_{f'\in\{0,1'\}^{|S'|}}\P_{S'(f')}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \bigO{p^{k}} \\

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

		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})\left(\sum_{\underset{|S'|<\infty}{S'\subseteq \mathbb{N}_+}}\sum_{f'\in\{0,1'\}^{|S'|}}\rho_{S'(f')} \P^\infty_{S'(f')}(\NZ{1})\right)^{\!\!2}

		+\bigO{p^{k}}.\tag{By Corollary \ref{cor:independenetSides} with $k=|\overline{P}|$ observing			$p^{k}=\mathcal{O}(p^{|P|+\lfloor\frac{|\overline{P}|}{2}\rfloor})$.}

		\end{align*}

		Since the above expression is independent of $n$ the statement follows.

	\end{proof}

Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the infinite chain.

\begin{lemma}[Startingstate dependence] \label{lemma:probIndepCycle}

    Let $d(a,b)$ be the distance between $a,b\in[n]$ on the cycle, so $d(a,b)=\min(|a-b| , n-|a-b|)$. Let $\dist{s}(a,b)$ be the distance between $a,b$ when taking the path that does \emph{not} cross $s$. Let $I\subseteq [n]$ be a non-empty set of vertices. Let $i_* \in I$ and define $I' = I \setminus \{i_*\}$. Let $j,s\notin I$, with $j\neq s$ be any vertices not in $I$.

    Then

    \begin{align*}

        \P_{I}(\Z{j})        &= \P_{I'}(\Z{j})        + \mathcal{O}(p^{d(i_*,j) + 1 - |I|}) \\

        \P_{I}(\Z{j},\NZ{s}) &= \P_{I'}(\Z{j},\NZ{s}) + \mathcal{O}(p^{\min\left( \dist{s}(i_*,j), \dist{j}(i_*,s) \right) + 1 - |I|}) .

    \end{align*}

\end{lemma}

\begin{proof}

    Without loss of generality, we can assume that $j=0$ and  $0 < i_* < s < n$ (because we can shift $j$ to $0$ and switch the direction to get the correct ordering). Therefore, we have to prove:

    \begin{align*}

        \P_{I}(\Z{0})        &= \P_{I'}(\Z{0})        + \mathcal{O}(p^{d(i_*,0) + 1 - |I|}) \\

        \P_{I}(\Z{0},\NZ{s}) &= \P_{I'}(\Z{0},\NZ{s}) + \mathcal{O}(p^{\min\left( i_*, s-i_* \right) + 1 - |I|}) .

    \end{align*}

    We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{0})=0$ and

    \begin{align*}

        \P_{I}(\Z{0})        &= \mathcal{O}(p^{d(i_*,0)}) \\

        \P_{I}(\Z{0},\NZ{s}) &= \mathcal{O}(p^{i_*}) = \mathcal{O}(p^{\min\left( i_*, s-i_* \right)})

    \end{align*}

    simply because a chain of zeroes has to be formed between $i_*$ and $0$, and in the second case this chain can not go through $s$ so the shortest path has length $i_*$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.

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

 We will now consider intervals around vertex 0.

    For $l,r\geq 1$ and $l+r\leq n$, define the event ``zeroes patch'' $\mathrm{ZP}^{[-l,r]_0}$ as the event of getting zeroes inside the interval $[-l,r]_0$ but not on the boundary, i.e.

    $$\mathrm{ZP}^{[-l,r]_0} = \NZ{-l} \cap \Z{-l+1} \cap \cdots \cap \Z{0} \cap \cdots \cap \Z{r-1} \cap \NZ{r}$$

    Note that there are $r+l-1$ `zeroes' in this event, so $\P_{J}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{r+l-1-|J|})$ for $J\subseteq[-l,r]_0$ is a lower bound on the order of $p$.\\

    Claim:

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{d(i_*,0)+1-|I|})

    \end{align*}

    If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ and also $\P_{I'}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ so then the claim holds.

    If $-l\in I$ or $r\in I$ (and $-l,r$ are both not $i_*$ because of the previous point) then the probability of $\mathrm{ZP}^{[-l,r]_0}$ is zero for both $I$ and $I'$ so the claim holds.

    If $[-l,r]_0$ has no overlap with $I$ then both sides are also zero so it also holds. We are left with the case where: $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.

    The following diagram illustrates the situation

    \begin{center}

        \includegraphics{diagram_circle_lemma.pdf}

    \end{center}

    Note that by Claim~\ref{claim:eventindependence} we have

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I\setminus [-l,r]_0}(\NZ{-l},\NZ{r})

    \end{align*}

    We have $i_*\in I \setminus[-l,r]_0$, and $I\cap[-l,r]_0 = I' \cap [-l,r]_0$. Define $J=I\setminus[-l,r]_0$ and $J'=I'\setminus[-l,r]_0$. We have $|J|<|I|$ so we can apply the induction hypothesis to $J$:

    \begin{align*}

        \P_{J}(\NZ{-l},\NZ{r})

&=

        - \P_{J}(\Z{-l},\NZ{r})

        - \P_{J}(\Z{r})

        \tag{partition of all events} \\

&=

        - \P_{J'}(\Z{-l},\NZ{r})

        - \P_{J'}(\Z{r}) \\

        &\quad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l), \dist{-l}(i_*,r) \right) +1-|J|})

        + \mathcal{O}(p^{d(i_*,r)+1-|J|}) \\

&=

        \P_{J'}(\NZ{-l},\NZ{b})

        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|})

    \end{align*}

    Note that the event $\mathrm{ZP}^{[-l,r]_0}$ contains $l+r-1$ zeroes, so $\P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{l+r-1-|I\cap[-l,r]_0|})$. This means

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0})

        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0})

        \left( \P_{I' \setminus [-l,r]_0}(\NZ{a},\NZ{b}) + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|}) \right) \\

        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I'\setminus [-l,r]_0}(\NZ{a},\NZ{b}) \\

        &\qquad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J| + l+r-1-|I\cap[-l,r]_0|}) \\

        &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})

    \end{align*}

    Where we used Claim~\ref{claim:eventindependence} again.

    Case separation shows that

    $$\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) + l +r \geq d(i_*,0) + 1$$

    for $l,r\geq 1$ which proves the claim.

    The first equality that we have to prove now follows from the fact that the ``zeroes patch'' events are a partition of $\Z{0}$:

    \begin{align*}

        \P_{I}(\Z{0})

        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}

        \P_I(\mathrm{ZP}^{[-l,r]_0})

        \tag{the events are a partition of $\Z{0}$}\\

        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}

        \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{d(i_*,0)+1-|I|})

        \tag{by claim} \\

        &= \P_{I'}(\Z{0}) + \mathcal{O}(p^{d(i_*,0)+1-|I|})

    \end{align*}

    Similarly, we have

    \begin{align*}

        \P_{I}(\Z{0} , \NZ{s})

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})

        \tag{partition of $\Z{0}$}\\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})

        +\mathcal{O}(p^{i_*+1-|I|}) \\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})

        +\mathcal{O}(p^{i_*+1-|I|})

        \tag{Claim~\ref{claim:eventindependence}}\\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})

        +\mathcal{O}(p^{i_*+1-|I|})

        \tag{$i_*\in I \setminus[s,r]_0$}\\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\

        &\qquad +\mathcal{O}(p^{\min\left( \dist{r}(i_*,s) , d(i_*,r)\right)+l+r-|I|})

        +\mathcal{O}(p^{i_*+1-|I|})

        \tag{same argument as before}\\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\

        &\qquad

        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})

        \tag{case separation}\\

        &= \P_{I'}(\Z{0} , \NZ{s})

        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})

    \end{align*}

    This finishes the proof.

\end{proof}

    Similarly to Mario's proof I use the observation that

    \begin{align*}

    R^{(n)} &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} R_{S(f)}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{(\mathcal{P})}) R^{(\mathcal{P})}_{S(f)} \\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{\mathcal{P}}) \sum_{P\in\mathcal{P}} R^{(P,\mathcal{P})}_{S(f)}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{\mathcal{P}}) \sum_{P\in\mathcal{P}} R^{(P)}_{S(f)\cap P}\tag{by Claim~\ref{claim:eventindependence}}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)}

    \sum_{P\text{ patch}} R^{(P)}_{S(f)\cap P}\sum_{\mathcal{P}:P\in\mathcal{P}}\mathbb{P}_{S(f)}(A^{\mathcal{P}})\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

     \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

    \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}}) \tag{remember Definition~\ref{def:visitingResamplings} and use Claim~\ref{claim:eventindependence}}\\

    &= \frac{1}{n}\sum_{S\subseteq [n]} \sum_{P\text{ patch}} \sum_{f_P\in\{0,1'\}^{|S\cap P|}}

    \rho_{S(f_P)} R^{(P)}_{S(f_P)} \mathbb{P}_{S(f_P)}(A^{(P)})

    \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}}) \\

	&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f_P\in\{0,1'\}^{|S\cap P|}}

	\rho_{S(f_P)}

        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathcal{O}(p^{|S_{><}|}) \tag{see below} \\

	&= \frac{1}{n}\sum_{S\subseteq [n]}\mathcal{O}(p^{|S|+|S_{><}|}).

    \end{align*}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_patches.pdf}

    \end{center}

    \caption{\label{fig:patches} Illustration of last steps of the proof.}

\end{figure}

    The penultimate inequality can be seen by case separation as follows: If $S\subseteq P$ then there is no splitting into $S\cap P$ and $S\setminus P$, and we already have $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$ simply because the patch $P$ must be filled with zeroes that were not yet in $S$, so this is at least $|S_{><}|$ resampled zeroes. For the more general case, assume that $S$ is larger than $P$ on both sides of $P$. This is illustrated in Figure \ref{fig:patches}. We will focus on the following sum that was in the above equations:

    \begin{align*}

        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S \cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}})

    \end{align*}

    By Lemma \ref{lemma:eventindependence} we can split this sum into two parts: the part to the left of $P$ and the part to the right of $P$. Define $S_\mathrm{left}=S\cap[S_\mathrm{min},P_{\mathrm{min}}-1]$ and $S_\mathrm{right}=S\cap[P_{\mathrm{max}}+1,S_\mathrm{max}]$, so that $S\cap\overline{P} = S_\mathrm{left} \cup S_\mathrm{right}$. These are also illustrated in Figure \ref{fig:patches}. Then we have

    \begin{align*}

        \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}})

        &= \mathbb{P}_{S(f_{\mathrm{left}})}(\overline{\Z{(P_{\min}-1)}}) \;\cdot\; \mathbb{P}_{S(f_{\mathrm{right}})}(\overline{\Z{(P_{\max}+1)}})

    \end{align*}

    and hence we can split the sum. Without loss of generality we now only consider the `right' part of the sum:

    \begin{align*}

        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}} \rho_{S_\mathrm{right}(f)} \mathbb{P}_{S_\mathrm{right}(f)}(\overline{\Z{(P_{\max}+1)}})

    \end{align*}

    Now further split this sum over the value of $f$ at position $S_\mathrm{max}$:

    \begin{align*}

        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}} \sum_{f'\in\{0,1'\}}

        \rho_{S_\mathrm{right}(f\,f')} \mathbb{P}_{S_\mathrm{right}(f\,f')}(\overline{\Z{(P_{\max}+1)}})

    \end{align*}

    and we use the definition of $\rho$ for the sum over $f'$:

    \begin{align*}

         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

        \rho_{S_\mathrm{right}(f)} \left(p \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{\Z{(P_{\max}+1)}}) + (-p) \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) \right)

    \end{align*}

    Now we recognize the setup of Lemma~\ref{lemma:probIndep} with $I=S_\mathrm{right}(f\,0)$ and $I'=S_\mathrm{right}(f\,1)$. The lemma yields

    \begin{align*}

        \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{\Z{(P_{\max}+1)}}) &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-(P_{\mathrm{max}}+1)+1-|S_\mathrm{right}|}) \\

        &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) .

    \end{align*}

    Entering this back into the sum gives

    \begin{align*}

         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

        \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|+1})

         = \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}}

        \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|})

    \end{align*}

    One can do the same for the `left' part, which gives a term $\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|})$. The part of $S$ that was within $P$ gives $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|})$. Combining these three factors yields

    \begin{align*}

        (\textrm{left part})(P\textrm{ part})(\textrm{right part}) &=

\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|}) \cdot \mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|}) \cdot \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) \\

        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S_\mathrm{left}\cup S_\mathrm{right}\cup (S\cap P)|})\\

        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S|})

        = \mathcal{O}(p^{|S_{><}|})

    \end{align*}

    as required. This finishes the proof.

\end{comment}

\begin{comment}

    \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}}

    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.

    %\begin{definition}[Resample sequences]

    %	A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.

    %\end{definition}

    %\begin{definition}[Constrained resample sequence]\label{def:constrainedRes}

    %	Let $C\subseteq[n]$ denote a slot configuration, and let $a\in\{\text{res},\neg\text{res}\}^{n-|C|}$, where the elements correspond to labels ``resampled" vs. ``not resampled" respectively.

    %	For $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.

    %	We define the set $A^{(C,a)}\subseteq RS$ as the set of resample sequences $(r_\ell)$ such that for all $j$ which has $a_j=\text{res}$ we have that $i_j$ appears in $(r_\ell)$ but for $j'$-s which have $a_{j'}=\neg\text{res}$ we have that $i_{j'}$ never appears in $(r_\ell)$.

    %\end{definition}

    \begin{definition}[Conditional expected number of resamples]

    	For a slot configuration $C\subseteq[n]$ and $a\in\{\!\text{ever},\text{ never}\}^{n-|C|}$ we define the event $A^{(C,a)}:=\bigwedge_{j\in[n-|C|]}\{i_j\text{ has }a_j\text{ become }0\text{ before reaching }\mathbf{1}\}$,

    	where $i_j$ is the $j$-th vertex of $[n]\setminus C$.

    	Then we also define

    	$$R^{(C,a)}_b:=\mathbb{E}[\#\{\text{resamplings when started from inital state }b\}|A^{(C,a)}].$$

    \end{definition}

    As in Mario's proof I use the observation that

    \begin{align*}

    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}}\sum_{a\in\{\!\text{ever},\text{ never}\}^{n-|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)P_{C(f)}(A^{(C,a)})\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\!\text{ever},\text{ never}\}^{n-|C|}} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)P_{C(f)}(A^{(C,a)}),

    \end{align*}

    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$, while all other location in $[n]\setminus C$ are set to $1$.

    When we write $R_{C(f)}$ we mean $R_{C(\bar{f})}$, i.e., replace $1'$-s with $1$-s. Since the notation is already heavy we dropped the bar from $f$, as it is clear from the context. Finally by $P_{C(f)}(A^{(C,a)})$ we denote the probability that the event $A^{(C,a)}$ holds.

    As in Definition for $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.

    Suppose that $a$ is such that there are two indices $j_1\neq j_2$ such that

    $a_{j_1}=\text{never}=a_{j_2}$, moreover the sets $\{i_{j_1}+1,\ldots, i_{j_2}-1\}$ and $\{i_{j_2}+1,\ldots, i_{j_1}-1\}$ partition $C$ non-trivially, and we denote by $C_l$,$C_r$ the corresponding partitions.

    I wanted to prove that

    \begin{equation}\label{eq:conditionalCancellation}

		\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)=0,

    \end{equation}

    based on the observation that for all $f\in\{0,1'\}^{|C|}$ we have

    that

    \begin{equation}\label{eq:keyIndependce}

    R^{{(C,a)}}_{C(f)}(p)=R^{{(C_l,a_l)}}_{C_l(f_l)}(p)+R^{{(C_r,a_r)}}_{C_r(f_r)}(p),

    \end{equation}

    where $f_l\in\{0,1'\}^{|C_l|}$ is defined as taking only the indices (and values) of $f$ corresponding to vertices of $C_l$, also $a_l\in[n-|C_l|]$ is defined such that $a$ and $a_l$ agree on vertices where $a$ is defined, and on the vertices where $a$ is not defined, i.e., the vertices of $C_r$ we define $a_l$ to contain ``never". We define things analogously for $f_r$ and $a_r$.

    The reason why \eqref{eq:keyIndependce} holds is that as before the two halves of the cycle are conditionally independent because neither $i_{j_1}$ nor $i_{j_2}$ can become $0$. To be more precise each resample sequence $\left(C(f)\rightarrow \mathbf{1} \right)\in A^{(C,a)}$ can be uniquely decomposed to resample sequences $\left(C_l(f_l)\rightarrow \mathbf{1}\right)\in A^{(C_l,a_l)}$ and $\left(C_r(f_r)\rightarrow \mathbf{1}\right)\in A^{(C_r,a_r)}$. The sum of probabilities of the set of resample sequences $\{r\}$ which have decomposition $(r_l,r_r)$ have probability which is the product of the probabilities of $r_l$ and $r_r$ as shown in the proof of Claim~\ref{claim:expectationsum}. This proves that the set of all resample sequences $\left(C(f)\rightarrow \mathbf{1}\right)\in A^{(C,a)}$ for our purposes can be viewed as a product set with product probability distribution. Therefore the halves can be treated independently and so the expectation values just add up.

    From here I wanted to mimic Mario's proof:

    \begin{align*}

    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)&=

    \sum_{f_l\in\{0,1'\}^{|C_l|}} \sum_{f_r\in\{0,1'\}^{|C_r|}}  (-1)^{|f_l|+|f_r|}p^{|C_l|+|C_r|} \left( R^{{(C_l,a_l)}}_{C_l(f_l)}(p) + R^{{(C_r,a_r)}}_{C_r(f_l)}(p) \right)\\

    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} R^{{(C_l,a_l)}}_{C_l(f_l)}(p) \sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} \\

    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} R^{{(C_r,a_r)}}_{C_r(f_r)}(p) \sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} \\

    &= 0.

    \end{align*}

    The nasty issue which I did not realise that the missing term $P_{C(f)}(A^{(C,a)})$ is non-constant: even though the event $A^{(C,a)}$ is independent of $f$ the probability $P_{C(f)}(A^{(C,a)})=P_{C(f_l)}(A^{(C_l,a_l)})\cdot P_{C(f_r)}(A^{(C_r,a_r)})$ is not and so the above breaks down.

    Observe that if \eqref{eq:conditionalCancellation} would hold for configurations that cut the slot configuration to two halves it would imply that the only non-zero contribution comes from pairs $(C,a)$ such that $C\cup\{i_j:a_j=\text{ever}\}$ is connected. This is because if this set is not connected, then either we can cut $C$ to two halves non-trivially along ``never" vertices, or there is an island of $\text{ever}$ vertices separated from any slots, and therefore from any $0$-s. This latter case has zero contribution since we cannot set these indices to $0$, without reaching them by some resamplings, and thereby building a path of $0$-s leading there.

    If $|C\cup\{i_j:a_j=\text{ever}\}|\geq k+1$ then all contribution has a power at least $k+1$ in $p$ since $(C,a)$ requires the prior appearance of at least $k+1$ particles. If $n\geq k+1$ than all $(C,a)$ such that $|C\cup\{i_j:a_j=\text{ever}\}|\leq k$ appears exactly $n$ times, since $(C,a)$ cannot be translationally invariant. Moreover the quantity $R^{{(C,a)}}_{C(f)}(p)$ is independent of $n$ due to the conditioning that every resampling happens on a connected component of length at most $k<n$. This would prove that $a_k^{(n)}$ is constant for $n\geq k+1$. The same arguments would directly translate to the torus and other translationally invariant objects, so we could go higher dimensional as Mario suggested.

    Questions:

    \begin{itemize}

    	\item Is it possible to somehow fix this proof?

    	\item In view of this (false) proof, can we better characterise $a_k^{(k+1)}$?

    	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

    	\item Can we prove the conjectured formula for $a_k^{(3)}$?

    \end{itemize}

\begin{comment}

    \subsection{Sketch of the proof of the linear bound \ref{it:const}}

    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.

    \begin{definition}[Resample sequences]

		A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.

    \end{definition}

    \begin{definition}[Constrained resample sequence]\label{def:constrainedRes}

    	Let $C\subseteq[n]$ denote a slot configuration, and let $a\in\{\text{res},\neg\text{res}\}^{n-|C|}$, where the elements correspond to labels ``resampled" vs. ``not resampled" respectively.

    	For $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.

		We define the set $A^{(C,a)}\subseteq RS$ as the set of resample sequences $(r_\ell)$ such that for all $j$ which has $a_j=\text{res}$ we have that $i_j$ appears in $(r_\ell)$ but for $j'$-s which have $a_{j'}=\neg\text{res}$ we have that $i_{j'}$ never appears in $(r_\ell)$.

    \end{definition}

    \begin{definition}[Expected number of resamples]

		For $b\in\{0,1\}^n$ we define

		$$R_b=\mathbb{E}[\#\{\text{resamplings when started from inital state }b\}],$$

		and for $(C,a)$ as in the previous definition we also define

		$$R^{(C,a)}_b=\mathbb{E}[\#\{\text{resamplings }\in A^{(C,a)} \text{ when started from inital state }b\}].$$

		Here we mean by the latter that after each resampling we check whether the sequence of resamplings so far is in $A^{(C,a)}$, if yes we count it, otherwise we do not count.

    \end{definition}

    As in Mario's proof I use the observation that

    \begin{align*}

    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}}\sum_{a\in\{\text{res},\neg\text{res}\}^{n-|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\text{res},\neg\text{res}\}^{n-|C|}} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p),

    \end{align*}

    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$, while all other location in $[n]\setminus C$ are set to $1$.

	When we write $R_{C(f)}$ we mean $R_{C(\bar{f})}$, i.e., replace $1'$-s with $1$-s. Since the notation is already heavy we dropped the bar from $f$, as it is clear from the context.

    As in Definition~\ref{def:constrainedRes} for $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.

    Suppose that $a$ is such that there are two indices $j_1\neq j_2$ such that

    $a_{j_1}=\neg\text{res}=a_{j_2}$, moreover the sets $\{i_{j_1}+1,\ldots, i_{j_2}-1\}$ and $\{i_{j_2}+1,\ldots, i_{j_1}-1\}$ partition $C$ non-trivially, and we denote by $C_l$,$C_r$ the corresponding partitions.

    We claim that

    $$\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)=0.$$

	This is based on the observation that that for all $f\in\{0,1'\}^{|C|}$ we have

    that

    \begin{equation}\label{eq:keyIndependceWrong}

    R^{{(C,a)}}_{C(f)}(p)=R^{{(C_l,a_l)}}_{C_l(f_l)}(p)+R^{{(C_r,a_r)}}_{C_r(f_r)}(p),

    \end{equation}

    where $f_l\in\{0,1'\}^{|C_l|}$ is defined as taking only the indices (and values) of $f$ corresponding to vertices of $C_l$, also $a_l\in[n-|C_l|]$ is defined such that $a$ and $a_l$ agree on vertices where $a$ is defined, and on the vertices where $a$ is not defined, i.e., the vertices of $C_r$ we define $a_l$ to contain $\neg\text{res}$. We define things analogously for $f_r$ and $a_r$.

    The reason why \eqref{eq:keyIndependceWrong} holds is as before that the two halves of the cycle are conditionally independent because neither $i_{j_1}$ nor $i_{j_2}$ are resampled. One could probably also argue similarly as Tom's grid figure shows.

    From here the proof goes just as in Mario's proof:

    \begin{align*}

    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)&=

    \sum_{f_l\in\{0,1'\}^{|C_l|}} \sum_{f_r\in\{0,1'\}^{|C_r|}}  (-1)^{|f_l|+|f_r|}p^{|C_l|+|C_r|} \left( R^{{(C_l,a_l)}}_{C_l(f_l)}(p) + R^{{(C_r,a_r)}}_{C_r(f_l)}(p) \right)\\

    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} R^{{(C_l,a_l)}}_{C_l(f_l)}(p) \sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} \\

    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|C_r|}} (-1)^{|f_r|} R^{{(C_r,a_r)}}_{C_r(f_r)}(p) \sum_{f_l\in\{0,1'\}^{|C_l|}} (-1)^{|f_l|} \\

    &= 0.

    \end{align*}

    Observe that it implies that the only non-zero contribution comes from pairs $(C,a)$ such that $C\cup\{i_j:a_j=\text{res}\}$ is connected. This is because if this set is not connected, then either we can cut $C$ to two halves non-trivially along $\neg\text{res}$ vertices, or there is an island of $\text{res}$ vertices separated from any slots, and therefore from any $0$-s. This latter case has zero contribution since we cannot resample these indices without first setting them to $0$, but under the conditions they can be never reached by any resampling, therefore they remain $1$ always.

    If $|C\cup\{i_j:a_j=\text{res}\}|\geq k+1$ then all contribution has a power at least $k+1$ in $p$ since $(C,a)$ requires the prior appearance of at least $k+1$ particles. If $n\geq k+1$ than all $(C,a)$ such that $|C\cup\{i_j:a_j=\text{res}\}|\leq k$ appears exactly $n$ times, since $(C,a)$ cannot be translationally invariant. Moreover the quantity $R^{{(C,a)}}_{C(f)}(p)$ is independent of $n$ due to the conditioning that every resampling happens on a connected component of length at most $k<n$. This proves that $a_k^{(n)}$ is constant for $n\geq k+1$.

    Note that the heart of the proof is \eqref{eq:keyIndependceWrong}, so this is what we should double check.

	The same arguments directly translate to the torus and other translationally invariant objects, so we can go higher dimensional :-) as Mario suggested.

	Questions:

	\begin{itemize}

		\item In view of this proof, can we better characterise $a_k^{(k+1)}$?

		\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

		\item Can we prove the conjectured formula for $a_k^{(3)}$?

	\end{itemize}

\end{comment}

\begin{comment}

    \begin{definition}[Neighborhood]

	   	For the length-$n$ cycle we identify sites with $[n]$.

	   	For a subset $S\subseteq [n]$ we define the $k$ neighborhood of $S$ as

	   	$N_k(S):=\cup_{s\in S} \{s-k,s-k+1,\ldots,s+k\}$ where numbers are interpreted mod $n$ and we represent the $\equiv 0$ class by $n$).

	\end{definition}

	\begin{definition}[Blocks and Gaps]

	   	For a configuration $C\subseteq [n]$ we call the connected components of $[n]\setminus N_1(C)$ the gaps. We denote by $m_C$ the number of gaps.

	   	We call a non-empty subset $B\subset C$ a block if $N_3(B)\cap C=B$ and $B$ is minimal, i.e., there is no proper subset $\emptyset\neq B'\subsetneq B$ satisfying $N_3(B')\cap C=B'$.

	   	Observe that whenever $m_C\geq 2$ the number of blocks is the same as the number of gaps.

    \end{definition}

    \begin{definition}[Crossings]

    	We say that a run (path) of the resampling procedure crosses $i\in[n]$ if there is ever a $0$ in $N_1({i})$ during the run.

    \end{definition}

    \begin{definition}[Enumerating gaps and mid points]

		Let $G_1,G_2,\ldots, G_{m_C}$ be an enumeration of the gaps respecting the cyclic ordering, and let $g_i$ be the middle element of $G_i$, if there are two middle elements we choose the smaller according to the cyclic ordering. (If $m_C=1$ and $G_1=[n]$ let $g_1=1$.)

		If $m_C\geq 2$ then for all $i\in[m_C]$ let $B_i$ be the block between $G_i$ and $G_{i+1}$.

    \end{definition}

    As in Mario's proof I use the observation that

    \begin{align*}

    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_b(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p),

    \end{align*}

    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$.

    For $a\in\{\text{crossed},\text{not crossed}\}^m$ we also introduce the notation $R^a_{C(f)}(p):=\mathbb{E}(\#\{\text{resamples before reaching }\mathbbm{1} \text{ from } C(f)\}|\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)\cdot\mathbb{P}(\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)$, which we define as $0$ if the conditioning event has $0$ probability.

    Since $$R_{C(f)}(p)=\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}R^a_{C(f)}(p),$$ we can further rewrite the expectation as

    \begin{align*}

	    R^{(n)}(p) &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p).

    \end{align*}

    Suppose that $a$ contains at least two ``not crossed'', the we claim that $\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)=0$. Let $j_1\neq j_2$ be two distinct indexes such that $a_{j_1}$ and $a_{j_2}$ are both saying ``not crossed''. Let $B_l:=B_{j_1}\cup B_{j_1+1}\cup\cdots\cup B_{j_2-1}$ and $B_r:=B_{j_2}\cup B_{j_2+1}\cup\cdots\cup B_{j_1-1}$ (again we interpret indexes mod $m_C$).

    Then we claim that for all $f\in\{0,1'\}^{|C|}$ we have

    that

    \begin{equation}\label{eq:keyIndependceOld}

		R^a_{C(f)}(p)=R^a_{B_l(f)}(p)+R^a_{B_r(f)}(p).

    \end{equation}

    The reason is as before that the halves are independent because neither $g_{j_1}$ nor $g_{j_2}$ is crossed. One could probably similarly prove it as the grid figure shows.

    From here the proof goes just as in Mario's proof:

    \begin{align*}

    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)&=

    \sum_{f_l\in\{0,1'\}^{|B_l|}} \sum_{f_r\in\{0,1'\}^{|B_r|}}  (-1)^{|f_l|+|f_r|}p^{|B_l|+|B_r|} \left( R^a_{B_l(f)} + R^a_{B_r(f)} \right)\\

    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} R^a_{B_l(f)} \sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} \\

    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} R^a_{B_r(f)} \sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} \\

    &= 0

    \end{align*}

    From this it follows that the only contribution comes from paths that cross all but one (or all) of the mid gaps. This then implies that it is enough to consider $\mathcal{O}(k)$ length configurations. (We define the length of a configuration $C$ as $n-\max_{j\in[m_C]}|G_j|$.)

    Note that the heart of the proof is \eqref{eq:keyIndependceOld}, so this is what we should double check.

    In fact I think the independence that we use in \eqref{eq:keyIndependceOld} can be also proven when we define a crossing as crossing the actual point, and not its $1$-neighborhood. It then would make it possible to define blocks as consecutive slacks. Also then we could actually use all points of the gaps not only the mid points. The requirement for the cancellation would be that there are ``not crossed'' labels from at least two distinct gaps. This would probably lead to the optimal $k+1$ bound giving the actual statement \ref{it:const}.

    Speculation: The $n=k$ case would then probably not work because the all $0$ starting configuration is invariant under rotations.

    To actually go below $2k$ one needs to be careful, because there are periodic configurations that are invariant under some rotations causing double counting issues. This can be probably resolved by showing that when a pattern becomes periodic for some $n$ it actually produces periodicity times more expectation due to symmetry. But this is all just speculation.

\end{comment}

	\bibliographystyle{alpha}

	\bibliography{Resample.bib}