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

\section{Quasiprobability method}

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

\end{align*}

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

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

    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.

~\\

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

\begin{align*}

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

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

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

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

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

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

\end{align*}

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

\newpage

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