\label{tab:coeffs}

	\resizebox{\columnwidth}{!}{%

		\begin{tabular}{c|ccccccccccccccccccccc}

			\backslashbox[10mm]{$n$}{$k$} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\		\hline

			3 &	0 & 1 & \cellcolor{blue!25}2 & 3+1/3 & 5.00 & 7.00 & 9.33 & 12.00 & 15.00 & 18.33 & 22.00 & 26.00 & 30.33 & 35.00 & 40.00 & 45.333 & 51.000 & 57.000 & 63.333 & 70.000 & 77.000 \\

			4 &	0 & 1 & 2 & \cellcolor{blue!25}3+2/3 & 6.16 & 9.66 & 14.3 & 20.33 & 27.83 & 37.00 & 48.00 & 61.00 & 76.16 & 93.66 & 113.6 & 136.33 & 161.83 & 190.33 & 222.00 & 257.00 & 295.50 \\

			5 &	0 & 1 & 2 & 3+2/3 & \cellcolor{blue!25}6.44 & 10.8 & 17.3 & 26.65 & 39.43 & 56.48 & 78.65 & 106.9 & 142.2 & 185.8 & 238.7 & 302.41 & 378.05 & 467.13 & 571.14 & 691.69 & 830.44 \\

			6 &	0 & 1 & 2 & 3+2/3 & 6.44 & \cellcolor{blue!25}11.0 & 18.5 & 30.02 & 47.10 & 71.68 & 106.0 & 152.9 & 215.4 & 297.4 & 403.1 & 537.21 & 705.25 & 913.31 & 1168.2 & 1477.4 & 1849.1 \\

			7 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & \cellcolor{blue!25}18.7 & 31.21 & 50.83 & 80.80 & 125.3 & 189.7 & 280.8 & 407.0 & 578.6 & 808.13 & 1110.2 & 1502.6 & 2005.6 & 2643.2 & 3443.1 \\

			8 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & \cellcolor{blue!25}31.44 & 52.08 & 84.95 & 136.0 & 213.6 & 328.9 & 496.5 & 735.6 & 1070.7 & 1532.5 & 2159.5 & 2998.8 & 4108.1 & 5556.7 \\

			9 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & \cellcolor{blue!25}52.30 & 86.27 & 140.7 & 226.3 & 358.4 & 558.4 & 855.4 & 1289.0 & 1911.5 & 2791.4 & 4017.2 & 5701.4 & 7985.9 \\

			10&	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & 52.30 & \cellcolor{blue!25}86.49 & 142.1 & 231.6 & 373.4 & 594.8 & 934.4 & 1447.1 & 2209.0 & 3324.6 & 4934.8 & 7226.9 & 10447. \\

            \vdots \\

            15& 0 & 1 & 2 & 3+2/3 & 6.44 & 11.08 & 18.76 & 31.45 & 52.31 & 86.49 & 142.33 & 233.31 & 381.17 & 621.02 & \cellcolor{blue!25}1009.38 & 1637.13 & % 2650.74 & 4285.68 & 6913.55 & 11171.2 & 18052.2

        \end{tabular}

	}

	\end{table}

	We observe that this is a power series in $p$. We discovered a very regular structure in this power series. It seems that for all $k\in\mathbb{N}$ and for all $n>k$ we have that $a^{(n)}_k$ is constant, this conjecture we verified using a computer up to $n=14$. 

	\newpage

	\noindent Based on our calculations presented in Table~\ref{tab:coeffs} and Figure~\ref{fig:coeffs_conv_radius} we make the following conjectures:

	\begin{enumerate}[label=(\roman*)]

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

        (A simpler version: $\forall k>0: a_k^{(3)}=(k+1)(k+2)/6$)

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

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

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

	\end{enumerate}

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

	\begin{figure}[!htb]\centering

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

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

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

	\label{fig:coeffs_conv_radius}

	\end{figure}

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

    \begin{align*}

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

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

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

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

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

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

    \end{align*}

    For $n=3$ the system becomes very simple because regardless of the current state, the probability of going to $111$ is always equal to $(1-p)^3$. Therefore the expected number of resamplings is simply the expectation of a geometric distribution. This gives the formula for $R^{(3)}(p)$ as shown above. Note that the $k$-th coefficient of the powerseries of a function $f(p)$ is given by $\frac{1}{k!}\left.\frac{d^k f}{dp^k}\right|_{p=0}$, i.e. the $k$-th derivative to $p$ evaluated at $0$ divided by $k!$. For the function $R^{(3)}(p) = (1-p)^{-3} - 1$ this yields $a^{(3)}_k = (k+2)(k+1)/6$ for $k\geq 1$ and $a^{(3)}_0=0$.

    ~

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