\documentclass{standalone}

\usepackage[T1]{fontenc}

\usepackage{amsmath}

\usepackage{amsfonts}

\usepackage{parskip}

\usepackage{marvosym} %Lightning symbol

\usepackage[usenames,dvipsnames]{color}

\usepackage[hidelinks]{hyperref}

\renewcommand*{\familydefault}{\sfdefault}

\usepackage{bbm} %For \mathbbm{1}

%\usepackage{bbold}

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}

    \draw[gray] (0,0) -- (10,0);

    \draw[gray,dotted] (0,2) -- (10,2);

    \draw[gray] (0,2) arc (90:270:1);

    \draw[gray] (10,0) arc (-90:90:1);

    \foreach \x in {0,...,10} {

        \draw[fill] (\x,0) circle (0.04);

    }

    \draw[fill] (11,1) circle (0.04);

    \draw[fill] (-1,1) circle (0.04);

    \foreach \x in {1,2,4,7,9} {

        \draw[fill,red] (\x,0) circle (0.08);

    }

    \draw[<->] (1,-0.5) -- (9,-0.5);

    \draw (5,-0.9) node {$\mathcal{D}(C)$};

    \draw[<->] (4.9,0.3) -- (6.1,0.3);

    \draw (5.5,0.7) node {$\mathrm{gap}(C)$};

    \draw[fill,red] (1,-2) circle (0.08);

    \draw (2,-2) node {slots $C$};

\end{tikzpicture}

\end{document}

		\item $\forall k\in\mathbb{N}, \forall n>m\geq 3 : a^{(n)}_k\geq a^{(m)}_k$ \label{it:geq}		

		\item $\forall k\in\mathbb{N}, \forall n,m\geq \max(k,3) : a^{(n)}_k=a^{(m)}_k$ \label{it:const}		

  		\item $\exists p_c=\lim\limits_{k\rightarrow\infty}1\left/\sqrt[k]{a_{k}^{(k+1)}}\right.$ \label{it:lim}			

	\end{enumerate}

	We also conjecture that $p_c\approx0.61$, see Figure~\ref{fig:coeffs_conv_radius}.

	\begin{figure}[!htb]\centering

	\includegraphics[width=0.5\textwidth]{coeffs_conv_radius.pdf}

	%\includegraphics[width=0.5\textwidth]{log_coeffs.pdf}	

	\caption{$1\left/\sqrt[k]{a_{k}^{(k+1)}}\right.$} %$\frac{1}{\sqrt[k]{a_k^{(k+1)}}}$

	\label{fig:coeffs_conv_radius}

	\end{figure}

    For reference, we also explicitly give formulas for $R^{(n)}(p)$ for small $n$. We also give them in terms of $q=1-p$ because they sometimes look nicer that way.

    \begin{align*}

    	R^{(3)}(p) &= \frac{1-(1-p)^3}{3(1-p)^3}

        			= \frac{1-q^3}{3q^3}\\

    	R^{(4)}(p) &= \frac{p(6-12p+10p^2-3p^3)}{6(1-p)^4}

                    = \frac{(1-q)(1+q+q^2+3q^3)}{6q^4}\\

        R^{(5)}(p) &= \frac{p(90-300p+435p^2-325p^3+136p^4-36p^5+6p^6)}{15(1-p)^5(6-2p+p^2)}\\

                   &= \frac{(1-q)(6+5q+6q^2+21q^3+46q^4+6q^6)}{15q^5(5+q^2)}

    \end{align*}

	If statements \ref{it:pos}-\ref{it:lim} are true, then we can define the function 

	$$R^{(\infty)}(p):=\sum_{k=0}^{\infty}a^{(k+1)}_k p^k,$$

	which would then have radius of convergence $p_c$, also it would satisfy for all $p\in[0,p_c)$ that $R^{(n)}(p)\leq R^{(\infty)}(p)$ and $\lim\limits_{n\rightarrow\infty}R^{(n)}(p)=R^{(\infty)}(p)$.

	It would also imply, that for all $p\in(p_c,1]$ we get $R^{(n)}(p)=\Omega\left(\left(\frac{p}{p_c}\right)^{n/2}\right)$.

	This would then imply a very strong critical behaviour. It would mean that for all $p\in[0,p_c)$ the expected number of resamplings is bounded by a constant $R^{(\infty)}(p)$ times $n$, whereas for all $p\in(p_c,1]$ the expected number of resamplings is exponentially growing in $n$.

	Now we turn to the possible proof techniques for justifying the conjectures \ref{it:pos}-\ref{it:lim}.

	First note that $\forall n\geq 3$ we have $a^{(n)}_0=0$, since for $p=0$ the expected number of resamplings is $0$.

	Also note that the expected number of initial $0$s is $p\cdot n$. If $p\ll1/n$, then with high probability there is a single $0$ initially and the first resampling will fix it, so the linear term in the expected number of resamplings is $np$, therefore $\forall n\geq 3$, $a^{(n)}_1=1$. 

	For the second order coefficients it is a bit harder to argue, but one can use the structure of $M_{(n)}$ to come up with a combinatorial proof. To see this, first assume we have a vector $e_b$ having a single non-zero, unit element indexed with bitstring $b$.

	Observe that $e_bM_{(n)}$ is a vector containing polynomial entries, such that the only indices $b'$ which have a non-zero constant term must have $|b'|\geq|b|+1$, since if a resampling produces a $0$ entry it also introduces a $p$ factor. Using this observation one can see that the second order term can be red off from $\rho M_{(n)}\mathbbm{1}+\rho M_{(n)}^2\mathbbm{1}$,

	which happens to be $2n$. (Note that it is already a bit surprising, form the steps of the combinatorial proof one would expect $n^2$ terms appearing, but they just happen to cancel each other.) Using similar logic one should be able to prove the claim for $k=3$, but for larger $k$s it seems to quickly get more involved.

	The question is how could we prove the statements \ref{it:pos}-\ref{it:lim} for a general $k$?

    \appendix

    \section{Lower bound on $R^{(n)}(p)$}

    Proof that \ref{it:pos} and \ref{it:lim} imply that for any fixed $p>p_c$ we have $R^{(n)}(p)\in\Omega\left(\left(\frac{p}{p_c}\right)^{n/2}\right)$. 

    By definition of $p_c = \lim_{k\to\infty} 1\left/ \sqrt[k]{a_k^{(k+1)}} \right.$ we know that for any $\epsilon$ there exists a $k_\epsilon$ such that for all $k\geq k_\epsilon$ we have $a_k^{(k+1)}\geq (p_c + \epsilon)^{-k}$. Now note that $R^{(n)}(p) \geq a_{n-1}^{(n)}p^{n-1}$ since all terms of the power series are positive, so for $n\geq k_\epsilon$ we have $R^{(n)}(p)\geq (p_c +\epsilon)^{-(n-1)}p^{n-1}$. Note that

    \begin{align*}

    	R^{(n)}(p)\geq(p_c+\epsilon)^{-(n-1)}p^{n-1}=\left(\frac{p}{p_c+\epsilon}\right)^{n-1} \geq \left(\frac{p}{p_c}\right)^{\frac{n-1}{2}},

    \end{align*}

    where the last inequality holds for $\epsilon\leq\sqrt{p_c}(\sqrt{p}-\sqrt{p_c})$.

    \section{Calculating the coefficients $a_k^{(n)}$}

    Let $\rho'\in\mathbb{R}[p]^{2^n}$ be a vector of polynomials, and let $\text{rank}(\rho')$ be defined in the following way: 

    $$\text{rank}(\rho'):=\min_{b\in\{0,1\}^n}\left( |b|+ \text{maximal } k\in\mathbb{N} \text{ such that } p^k \text{ divides } \rho'_b\right).$$

	Clearly for any $\rho'$ we have that $\text{rank}(\rho' M_{(n)})\geq \text{rank}(\rho') + 1$. Another observation is, that all elements of $\rho'$ are divisible by $p^{\text{rank}(\rho')-n}$.

    We observe that for the initial $\rho$ we have that $\text{rank}(\rho)=n$, therefore $\text{rank}(\rho*(M_{(n)}^k))\geq n+k$, and so $\rho*(M_{(n)}^k)*\mathbbm{1}$ is obviously divisible by $p^{k}$. This implies that $a_k^{(n)}$ can be calculated by only looking at $\rho*(M_{(n)}^1)*\mathbbm{1}, \ldots, \rho*(M_{(n)}^k)*\mathbbm{1}$.

\newpage

\section{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 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}$.

\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$. Note that if a path samples a $0$ then $\mathbb{P}[\xi]$ gains a factor $p$.\\

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

	For a slot configuration $C\subseteq[n]$, we define the diameter $\diam{C}$ to be the minimum size of an interval containing $C$ where the interval is also considered modulo $n$. In other words $\diam{C} = n - \max\{ j \vert \exists i : [i,i+j-1]\cap C = \emptyset \}$. Figure \ref{fig:diametergap} shows the diameter in a picture.

\end{definition}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_gap.pdf}

    \end{center}

\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|+\mathrm{gap}(C)}$ when $n$ is large enough. Here $\mathrm{gap}(C)$ is defined as in Figure \ref{fig:diametergap}, its the size of the largest gap of $C$ within the diameter of $C$. 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:

For a starting configuration 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. 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}) \\

			&= 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. This assumes $n$ 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)$ the state goes to $\framebox{$101$}$ and then the expected number of resamplings is $1+R_{101}$. I (Tom) believe this requires the assumption $p_\mathrm{tot} := \sum_{\xi\in\paths{b}} \mathbb{P}[\xi] = 1$. To see why this is required, note that the actual term in the recursive formula should be $$(3p-6p^2)\cdot\left( \sum_{\xi\in\paths{101}} \mathbb{P}[\xi] \cdot \left( 1 + |\xi|\right) \right) = (3p-6p^2)\left( p_\mathrm{tot} + R_{101} \right)$$

When there would be a non-zero probability of never stopping the resample process then $p_\mathrm{tot}$ (the probability of ever reaching $\mathbf{1}$) could be less than one. Therefore I assume that $R^{(n)}(p)$ is finite which implies that the probability of ever reaching $\mathbf{1}$ is 1.

\newpage

\subsection{Cancellation of gapped configurations}

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 circle $\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) + \mathcal{O}(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)\\

        = \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi]

        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}}

          \sum_{\substack{\xi_2\in\paths{b_1}\\\xi_2 \in \mathrm{NZ}_j}}

        \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\

        &=

        \mathbb{P}_{b_1}(\mathrm{NZ}_j)

        \; \cdot \;

        \mathbb{P}_{b_2}(\mathrm{NZ}_j).

    \end{align*}

    For the second equality, note that again by the same reasoning as in the proof of claim \ref{claim:expectationsum} we have

    \begin{align*}

        \mathbb{P}_b(\mathrm{NZ}_j) R_{b,\mathrm{NZ}_j}

        := \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi] |\xi| 

        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}}

          \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}_j}}

        \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\

        &=

        \mathbb{P}_{b_2}(\mathrm{NZ}_j) \mathbb{P}_{b_1}(\mathrm{NZ}_j) R_{b_1,\mathrm{NZ}_j}

        \; + \;

        \mathbb{P}_{b_1}(\mathrm{NZ}_j) \mathbb{P}_{b_2}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} .

    \end{align*}

    Dividing by $\mathbb{P}_b(\mathrm{NZ}_j)$ and using the first equality gives the desired result.

\end{proof}

~

TEST: Although a proof of claim \ref{claim:expectationsum} was already given, I'm trying to prove it in an alternate way using claim \ref{claim:eventindependence}.

~

Assume that $b_1$ ranges up to site $0$, the gap ranges from sites $1,...,k$ and $b_2$ ranges from site $k+1$ and onwards. For $j=1,...,k$ define the ``partial-zeros'' event $\mathrm{PZ}_j = \mathrm{Z}_1 \cap \mathrm{Z}_2 \cap ... \cap \mathrm{Z}_{j-1} \cap \mathrm{NZ}_j$ i.e. the first $j-1$ sites of the gap become zero and site $j$ does not become zero. Also define the ``all-zeros'' event $\mathrm{AZ} = \mathrm{Z}_1 \cap ... \cap \mathrm{Z}_k$, where all sites of the gap become zero. Note that these events partition the space, so we have for all $b$ that $\sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) = 1 - \mathbb{P}_b(\mathrm{AZ}) = 1 - \mathcal{O}(p^k)$.

~

Furthermore, if site $j$ becomes zero when starting from $b_1$ it means all sites to the left of $j$ become zero as well. Similarly, from $b_2$ it implies all the sites to the right of $j$ become zero.

Because of that, we have

\begin{align*}

    \mathbb{P}_{b_1}(\mathrm{PZ}_j) &= \mathbb{P}_{b_1}(\mathrm{Z}_{j-1} \cap \mathrm{NZ}_j) = \mathcal{O}(p^{j-1}) \\

    \mathbb{P}_{b_2}(\mathrm{NZ}_j) &= 1 - \mathbb{P}_{b_2}(\mathrm{Z}_j) = 1 - \mathcal{O}(p^{k-j+1})

\end{align*}

Following the proof of claim \ref{claim:eventindependence} we also have

\begin{align*}

    \mathbb{P}_b(\mathrm{PZ}_{j})

    &=

    \mathbb{P}_{b_1}(\mathrm{PZ}_{j})

    \; \cdot \;

    \mathbb{P}_{b_2}(\mathrm{NZ}_{j}) \\

    R_{b,\mathrm{PZ}_{j}}

    &=

    R_{b_1,\mathrm{PZ}_{j}}

    \; + \;

    R_{b_2,\mathrm{NZ}_{j}}

\end{align*}

Now observe that

\begin{align*}

    R_b &= \sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) R_{b,\mathrm{PZ}_j} + \mathbb{P}_b(\mathrm{AZ}) R_{b,\mathrm{AZ}} \\

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

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

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

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

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

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

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

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

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

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

        &= R_{b_1}

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

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

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

\end{align*}

\newpage

    \subsection{Attempt to prove the linear bound \ref{it:const}}

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

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

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

	Let $b_I$ be the initial state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. For an event $A$ representing a subset of all possible resample sequences let $P_I(A)$ denote the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$. 

\end{definition}

\begin{definition}[Vertex visiting resamplings]\label{def:visitingResamplings}

	Let $V^{(i)}$ be the event corresponding to ``Vertex $i$ gets resampled to $0$ before termination''.

\end{definition}

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

	Then $P_{I}(V^{(0)})=P_{I'}(V^{(0)}) + O(p^{I_{\max}+1-|I|})$.

\end{lemma}

\begin{proof}

	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples the $0$ vertex must produce at least $I_{\max}$ number of $0$-s during the resamplings.

	Induction step: For an event $A$ and $k>0$ let us denote by $A_k=A\cap$``Each vertex in $0,1,2,\ldots, k-1$ gets $0$ before termination (either by resampling or initialisation), but not $k$''. Observe that $V^{(0)}=\dot{\bigcup}_{k=1}^{\infty}V^{(0)}_k$.

	\begin{align*}

		P_{I}(V^{(0)})

		&=\sum_{k=1}^{\infty}P(V^{(0)}_k)

		=\sum_{k\in \mathbb{N}\setminus I}P(V^{(0)}_k)\\

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

		&=\sum_{k\in I_{><}}P_{I_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}+1-|I|})

		\tag{$k<I_{\min}\Rightarrow P_{I_{<k}}(V^{(0)}_k)=0$}\\

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

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

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

		\left(P_{I'_{>k}}(\overline{V^{(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_{I'_{<k}}(V^{(0)}_k)\cdot

		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})	

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

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

		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\

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

		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow P_{I'_{<k}}(V^{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\

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

	\end{align*}

\end{proof}

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

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

\end{definition} 

Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is \emph{exactly} $\mathcal{P}$ whereas $A^{(P)}$ is the event that one of the patches is equal to $P$ but there can be other patches as well.

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

	Then we define

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

	For a patch set $\mathcal{P}$ and some $P\in\mathcal{P}$ we define

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

	and 

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

	finally

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

\end{definition} 

    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{V^{(P_{\min}-1)}}\cap\overline{V^{(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{V^{(P_{\min}-1)}}\cap\overline{V^{(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_{><}|}) \\             

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

    \end{align*}

   	The penultimate inequality can be seen by case separation.

   	If $S_{><}\subseteq P$ then already $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$.

   	Otherwise if all elements of $S_{><}\setminus P$ are larger than $P_{\max}$ then we view the last summation as $\sum_{f'_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}\setminus\{S_{\max}\}|}}\sum_{f''_{\overline{P}}\in\{0,1'\}^{1}}$ and use Lemma~\ref{lemma:probIndep} to conclude the cancellations pairwise regarding the filling of $S_{\max}$, i.e., the value of $f''_{\overline{P}}$. We proceed similarly when 

   	all elements of $S_{><}\setminus P$ are smaller than $P_{\min}$. In the last case we again proceed similarly, but now the cancellations will come from the interplay of $4$ fillings, corresponding to the possible filling of $S_{\min}$ and $S_{\max}$ simultaneously.

	I think the same arguments would directly translate to the torus and other translationally invariant objects, so we could go higher dimensional as Mario suggested. Then 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.

    Questions:

    \begin{itemize}

    	\item Is this proof finally flawless?

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

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