\item Define the boundary $\overline{\partial} S$ of $S$ as the set of vertices adjacent to $S$, excluding $S$ itself. In other words $\overline{\partial} S = B(S;1) \setminus S$.

        \P(\text{pick }v_1 \mid z_1) \P(r_1)

        \P(\text{pick }v_2 \mid z_2) \P(r_2) \cdots \\ 

    This is best explained by an example. Lets consider the following fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ and an example interleaving where we choose vertices from $Y,X,X,Y,\cdots$:

    \begin{align*}

        \xi^{G\setminus Y} &= \left( (\text{initialize to }b^X\;1^S),

        (z^X_1, v^X_1, r^X_1),

        (z^X_2, v^X_2, r^X_2),

        (z^X_3, v^X_3, r^X_3),

        (z^X_4, v^X_4, r^X_4),

        \cdots  \right) \\

        \xi^{G\setminus X} &= \left( (\text{initialize to }1^S\;b^Y),

        (z^Y_1, v^Y_1, r^Y_1),

        (z^Y_2, v^Y_2, r^Y_2),

        (z^Y_3, v^Y_3, r^Y_3),

        (z^Y_4, v^Y_4, r^Y_4),

        \cdots  \right) \\

        \xi^G             &= \big( (\text{initialize to }b^X \; 1^S \; b^Y),

        (z^X_1+z^Y_1, v^Y_1, r^Y_1),

        (z^X_1+z^Y_2, v^X_1, r^X_1), \\

        &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad

        (z^X_2+z^Y_2, v^X_2, r^X_2),

        (z^X_3+z^Y_2, v^Y_2, r^Y_2),

        \cdots \big)

    \end{align*}

    Here $b^X\in \{0,1\}^{X}$ and $b^Y\in\{0,1\}^Y$. Since we condition on the event that $S$ is initialized to ones, we know the initial state is of the form $b^X\;1^S$ in $\xi^{G\setminus Y}$. Similarly, since these paths satisfy the $\NZ{S}$ event, we know all the vertices $v_i$ resampled in $\xi^{G\setminus Y}$ are vertices in $X$, and the resampled bits $r_i$ are bits corresponding to vertices in $X$.

    In the newly constructed path $\xi^G$ the number of zeroes is the number of zeroes in $X$ and $Y$ together, so this starts as $z^X_1 + z^Y_1$. Then in this example, after the first step the number of zeroes is $z^X_1+z^Y_2$ since a step of $\xi^{G\setminus X}$ was done (so a vertex in $Y$ was resampled).

    The probability of $\xi^{G\setminus Y}$ is given by

    \begin{align*}

        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) &=

        \P(\text{initialize }b^X\;1^S \mid \text{initialize $S$ to }1)

        \P(\text{pick }v^X_1 \mid z^X_1) \P(r^X_1)

        \P(\text{pick }v^X_2 \mid z^X_2) \P(r^X_2) \cdots \\ 

        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot

        \frac{1}{z^X_1} \P(r^X_1) \cdot

        \frac{1}{z^X_2} \P(r^X_2) \cdots

        \frac{1}{z^X_{|\xi^{G\setminus Y}|}} \P(r^X_{|\xi^{G\setminus Y}|}) .

    \end{align*}

    and similar for $\xi^{G\setminus X}$.

    Instead of choosing a step in $Y,X,X,Y,\cdots$ we could have chosen other orderings. The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $Y,X,X,Y$ in the example above.

        \includegraphics{diagram_paths3.pdf}

    For the labels shown within the grid, define $p_{ij} = \frac{z^X_i}{z^X_i + z^Y_j}$.

    The probability of this particular interleaving $\xi^G$ is given by

    \begin{align*}

        \P^{G}_S(\xi^{G})

        &= (1-p)^{|b^X\; b^Y|} p^{|X\cup Y|-|b^X\;b^Y|} \quad

        \frac{1}{z^X_1+z^Y_1} \P(r^Y_1) \cdot

        \frac{1}{z^X_1+z^Y_2} \P(r^X_1) \cdots \\

        &= (1-p)^{|b^X|} p^{|X|-|b^X|} \cdot (1-p)^{|b^Y|} p^{|Y|-|b^Y|} \\

        &\qquad \cdot

        \frac{z^Y_1}{z^X_1+z^Y_1} \frac{1}{z^Y_1} \P(r^Y_1) \;

        \frac{z^X_1}{z^X_1+z^Y_2} \frac{1}{z^X_1} \P(r^X_1) \;

        \frac{z^X_2}{z^X_2+z^Y_2} \frac{1}{z^X_2} \P(r^X_2)

        \frac{z^Y_1}{z^X_1+z^Y_1} 

        \frac{z^X_1}{z^X_1+z^Y_2} 

        \frac{z^X_2}{z^X_2+z^Y_2} 

        \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

        \tag{definition} \\

        &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

        \tag{definition of $p_{i,j}$} \\

        &= \P(\text{path in grid}) \; \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \; \P^{G\setminus X}_S(\xi^{G\setminus X})

        \P^{G}_S(\NZ{S} \cap A^X \cap A^Y)

        &= \sum_{\xi^G \in \NZ{S}\cap A^X \cap A^Y} \P^{G}_S(\xi^G) \\

        &= \sum_{\xi^{G\setminus Y} \in \NZ{S}\cap A^X}

           \sum_{\xi^{G\setminus X} \in \NZ{S}\cap A^Y}

            \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot

            \P^{G\setminus X}_S(\xi^{G\setminus X}) \\

        &= \P^{G\setminus Y}_S(\NZ{S} \cap A^X) \; \cdot \; \P^{G\setminus X}_S(\NZ{S} \cap A^Y)

\todo{rewrite from here}