\caption{\label{fig:diametergap} Illustration of Definition \ref{def:diameter}. A set $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 positions is shown by the red dots. The smallest interval containing $C$ is $[1,9]$, so the diameter is $\diam{C}=9$. The blue squares denote the set $\gaps{C} = \{3,5,6,8\}$. The dotted line at the top depicts the rest of the cycle which may be much larger. The largest gap of $C$ is $\maxgap{C}=2$ which is the largest connected component of $\gaps{C}$.}

    Equivalently, on the infinite line $\xi_1$ and $\xi_2$ are independent if there is a site `inbetween' them that was never zero in $\xi_1$ and never zero in $\xi_2$. On the cycle $\xi_1$ and $\xi_2$ are independent if there are \emph{two} sites inbetween them that are never zero.

The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two halves of the cycle are independent. 

    From any path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ we can construct paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ as follows. Let us write the path $\xi$ as

    $$\xi=\left( (z_1, s_1, r_1), (z_2, s_2, r_2), ..., (z_{|\xi|}, s_{|\xi|}, r_{|\xi|}) \right)$$

    where $z_i\in[n]$ denotes the number of zeroes in the state before the $i$th step, $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. We have

    \begin{align*}

        \P_b[\xi] &= \P(\text{choose }s_1) \P(r_1) \P(\text{choose }s_2) \P(r_2) \cdots \P(\text{choose }s_{|\xi|}) \P(r_{|\xi|}) \\

                &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi|}} \P(r_{|\xi|}) .

    \end{align*}

    To construct $\xi_1$ and $\xi_2$, start with empty sequences $\xi_1,\xi_2$ and for each step $(z_i,s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add $(z^{(1)}_i,s_i,r_i)$ to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add $(z^{(2)}_i,s_i,r_i)$ to $\xi_2$. Here $z^{(1)}_i$ is the number of zeroes that were on the $b_1$ side and $z^{(2)}_i$ is the number of zeroes on the $b_2$ side so we have $z_i = z^{(1)}_i + z^{(2)}_i$.

    Let the resulting paths be

    \begin{align*}

        \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\

        \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right)

    \end{align*}

    Now $\xi_1$ is a valid (terminating) path from $b_1$ to $\mathbf{1}$, because in the original path $\xi$, all zeroes ``on the $b_1$ side'' have been resampled by resamplings ``on the $b_1$ side''. Since the sites $j_1,j_2$ inbetween never become zero, there can not be any zero ``on the $b_1$ side'' that was resampled by a resampling ``on the $b_2$ side''.

    The probability of $\xi_1$, started from $b_1$, is given by

    \begin{align*}

        \P_{b_1}[\xi_1] &= \P(\text{choose }s_{a_1}) \P(r_{a_1}) \P(\text{choose }s_{a_2}) \P(r_{a_2}) \cdots \P(\text{choose }s_{a_{|\xi|}}) \P(r_{a_{|\xi|}}) \\

                &= \frac{1}{z^{(1)}_{a_1}} \P(r_{a_1}) \frac{1}{z^{(1)}_{a_2}} \P(r_{a_2}) \cdots \frac{1}{z^{(1)}_{a_{|\xi|}}} \P(r_{a_{|\xi|}})

    \end{align*}

    and similar for $\xi_2$.

    Vice versa, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$. The following diagram illustrates all possible interleavings:

    \begin{center}

        \includegraphics{diagram_paths.pdf}

    \end{center}

    A particular interleaving is a path through the above grid. So for a fixed $\xi_1,\xi_2$ there are $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ possible interleavings $\xi$, and vice versa there are $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ that decompose into the same $\xi_1$ and $\xi_2$. For a fixed $\xi_1,\xi_2$ we now show the following:

    \begin{align*}

        \sum_{\substack{\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P_b[\xi] &=

        \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2] \\

        &= \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2]

    \end{align*}

    This is best explained by an example. We have, for an example interleaving:

    \begin{align*}

        \xi   &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4), \cdots \right) \\

        \xi_1 &= \left( (z^{(1)}_1, s_1, r_1), \phantom{(z^{(2)}_2, s_2, r_2), (z^{(1)}_3, s_3, r_3),} (z^{(1)}_4, s_4, r_4),\cdots  \right) \\

        \xi_2 &= \left( \phantom{(z^{(1)}_1, s_1, r_1),} (z^{(2)}_2, s_2, r_2), (z^{(2)}_3, s_3, r_3),\phantom{(z^{(2)}_4, s_4, r_4), } \cdots \right)

    \end{align*}

    Remember $z^{(1)}_i + z^{(2)}_i = z_i$.

    The probability associated to this interleaving is

    \begin{align*}

        \P_b[\xi] &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \frac{1}{z_3} \P(r_3) \frac{1}{z_4} \P(r_4) \cdots \\

        &=

        \frac{z^{(1)}_1}{z_1} \frac{1}{z^{(1)}_1} \P(r_1) \;

        \frac{z^{(2)}_2}{z_2} \frac{1}{z^{(2)}_2} \P(r_2) \;

        \frac{z^{(2)}_3}{z_3} \frac{1}{z^{(2)}_3} \P(r_3) \;

        \frac{z^{(1)}_4}{z_4} \frac{1}{z^{(1)}_4} \P(r_4)

        \cdots \\

        &=

        \frac{z^{(1)}_1}{z_1}

        \frac{z^{(2)}_2}{z_2}

        \frac{z^{(2)}_3}{z_3}

        \frac{z^{(1)}_4}{z_4}

        \cdots

        \P_{b_1}[\xi_1] \P_{b_2}[\xi_2]

    \end{align*}

    \todo{write more}

    \begin{align*}

        \P(\text{interleaving}) = \P(\text{choose step of }\xi_1) \P(\text{choose step of }\xi_2) \P(\text{choose step of }\xi_2) \P(\text{choose step of }\xi_1) \cdots

    \end{align*}

    These choices depend on the number of zeroes present in the state:

    \begin{align*}

        \P(\text{choose step of }\xi_1) &=

        \frac{z^{(1)}_1}{z^{(1)}_1 + z^{(2)}_1} \\

        \P(\text{choose step of }\xi_2) &=

        \frac{z^{(2)}_1}{z^{(1)}_1 + z^{(2)}_1}

    \end{align*}

    These are the $p_i$ and $1-p_i$ shown in the grid diagram. In $\P_{b_1}[\xi_1]$ we have a factor $\frac{1}{z^{(1)}_1}$, so together with the probability above this gives $\frac{z^{(1)}_1}{z^{(1)}_1 + z^{(2)}_1} \frac{1}{z^{(1)}_1} = \frac{1}{z_1}$, as in the original expression for $\P_b[\xi]$. 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 means the sum of all $\P(\text{interleaving})$ is equal to 1.

    We obtain

    For the third equality, by the same reasoning we can decompose the paths

        &\equiv \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\

	Also this claim finally ``sees'' how many empty places are between slots. These properties make it possible to use this lemma to prove the sought linear bound. We show it for the infinite chain, but with a little care it should also translate to the cycle.

Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the infinite chain.

\begin{lemma}[Startingstate dependence] \label{lemma:probIndepCycle}

    Let $d(a,b)$ be the distance between $a,b\in[n]$ on the cycle, so $d(a,b)=\min(|a-b| , n-|a-b|)$. Let $\dist{s}(a,b)$ be the distance between $a,b$ when taking the path that does \emph{not} cross $s$. Let $I\subseteq [n]$ be a non-empty set of vertices. Let $i_* \in I$ and define $I' = I \setminus \{i_*\}$. Let $j,s\notin I$, with $j\neq s$ be any vertices not in $I$.

    When we refer to an interval $[a,b]$ on the cycle we could be referring to two possible intervals because of the periodicity of the cycle. Define $[a,b]_j$ as the interval with vertex $j$ on the \emph{inside}. Furthermore by $-a$ we mean the vertex $n-a$, as one would expect modulo $n$.