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

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

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

        &=

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

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

    \begin{align*}

    \end{align*}

    \begin{align*}

    \end{align*}

    \begin{center}

    \end{center}

    \begin{align*}

        \cdots \tag{rewrite fractions}\\

        &=

        \cdots

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

    \end{align*}

\end{proof}

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