\DeclarePairedDelimiter\bra{\langle}{\rvert}

\DeclarePairedDelimiter\ket{\lvert}{\rangle}

\DeclarePairedDelimiterX\braket[2]{\langle}{\rangle}{#1 \delimsize\vert #2}

\newcommand{\underflow}[2]{\underset{\kern-60mm \overbrace{#1} \kern-60mm}{#2}}

\def\Ind(#1){{{\tt Ind}({#1})}}

\def\Id{\mathrm{Id}}

\def\Pr{\mathrm{Pr}}

\def\Tr{\mathrm{Tr}}

\def\im{\mathrm{im}}

\newcommand{\bOt}[1]{\widetilde{\mathcal O}\left(#1\right)}

\newcommand{\bigO}[1]{\mathcal O\left(#1\right)}

\newcommand{\QMAo}{\textsf{QMA$_1$}}

\newcommand{\BQP}{\textsf{BQP}}

\newcommand{\NP}{\textsf{NP}}

\newcommand{\SharpP}{\textsf{\# P}}

\newcommand{\diam}[1]{\mathcal{D}\left(#1\right)}

\newcommand{\paths}[1]{\mathcal{P}\left(#1\to\mathbf{1}\right)}

\newcommand{\start}[1]{\textsc{start}\left(#1\right)}

\newcommand{\patch}[1]{\textsc{Patch}\left(#1\right)}

\newcommand{\patches}[1]{\textsc{Patches}\left(#1\right)}

\newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}

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

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

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

\newpage

\section{General graphs proof}

We consider the following generalization of the Markov Chain.

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

\begin{definition}[Events and notation] \label{def:events}

    \begin{itemize}

        \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 $\Z{S}$ as the complement of $\NZ{S}$, i.e. the event that \emph{there exists} a vertex in $S$ that becomes zero at some 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 distant-$k$ boundary $\overline{\partial}(S,k):=B(S,k)\setminus B(S,k-1)$ as the set of vertices lying at exactly distance $k$ from $S$.

    \end{itemize}

\end{definition}

The following Lemma says that if a set $S$ splits the graph in two, then those two parts become independent if the vertices in $S$ never become zero.

	First we assume, that $\NZ{X}\subseteq\overline{A^X}$, i.e., $A^X\subseteq \Z{X}$.

	For $i\in[d]$ we define $A_i^X:=A^X\cap{\NZ{\overline{\partial}(X,i)}}\cap\bigcap_{j\in[i-1]}\Z{\overline{\partial}(X,j)}$, 

	and define $A_{d+1}^X:=A^X\cap\bigcap_{j\in[d]}\Z{\overline{\partial}(X,j)}$,

	so that they form a partition $A^X=\dot\bigcup_{i\in [d+1]}A_i^X$. 

	It is easy to see that for all $i\in[d+1]$ we have $A_{i}^X\subseteq\Z{X}\cap\bigcap_{j\in[i-1]}\Z{\overline{\partial}(X,j)}$, and therefore 

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

		\P^G(A_{i}^X)=\bigO{p^{i}}.

	\end{equation}

	Now we use the Splitting lemma~\ref{lemma:splitting} to show that for all $i\in[d]$

	\begin{align}

		\P^G(A_{i}^X)

		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d+1}} \tag{by Lemma~\ref{lemma:splitting}}\\

		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d(Y,Y)}}. \label{eq:indStep}

	\end{align}

	Therefore 

	$$\P^G(A^X)

	\overset{\eqref{eq:AXorder}}{=}\sum_{i\in[d]}\P^G(A_i^X)+\bigO{p^{d(Y,Y)}}

	\overset{\eqref{eq:indStep}}{=}\sum_{i\in[d]}\P^{G\setminus Y}(A_i^X)+\bigO{p^{d(Y,Y)}}

	\overset{\eqref{eq:AXorder}}{=}\P^{G\setminus Y}(A^X)+\bigO{p^{d(Y,Y)}}.

	$$

	We finish the proof by observing that if $\NZ{X}\nsubseteq\overline{A^X}$,

	then we necessarily have $\NZ{X}\subseteq A^X$, and therefore we can use the above proof with $B^X:=\overline{A^X}$ and use that $\P(A^X)=1-\P(B^X)$.

\end{proof}