The main insight that Lemma~\ref{lemma:probIndep} gives is that if we separate the slots to two halves, in order to see the cancellation of the contribution of the expected resamples on the right, we can simply pair up the left configurations by the particle filling the leftmost slot. And similarly for cancelling the left expectations we pair up right configurations based on the rightmost filling. 

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

~

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

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

    Let $d(a,b)$ be the distance between $a,b\in[n]$ on the circle, 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$.

    Then

    \begin{align*}

        \P_{I}(\Z{j})        &= \P_{I'}(\Z{j})        + \mathcal{O}(p^{d(i_*,j) + 1 - |I|}) \\

    \end{align*}

\end{lemma}

\begin{proof}

    \begin{align*}

    \end{align*}

    When we refer to an interval $[a,b]$ on the circle we could be referring to two possible intervals because of the periodicity of the circle. 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$.

    For $l,r\geq 1$ and $l+r\leq n$, define the event ``zeroes patch'' $\mathrm{ZP}^{[-l,r]_0}$ as the event of getting zeroes inside the interval $[-l,r]_0$ but not on the boundary, i.e.

    $$\mathrm{ZP}^{[-l,r]_0} = \NZ{-l} \cap \Z{-l+1} \cap \cdots \cap \Z{0} \cap \cdots \cap \Z{r-1} \cap \NZ{r}$$

    Note that there are $r+l-1$ `zeroes' in this event, so $\P_{J}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{r+l-1-|J|})$ for $J\subseteq[-l,r]_0$ is a lower bound on the order of $p$.\\

    Claim:

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0}) &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{d(i_*,0)+1-|I|})

    \end{align*}

    If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ and also $\P_{I'}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$ so then the claim holds.

    If $-l\in I$ or $r\in I$ (and $-l,r$ are both not $i_*$ because of the previous point) then the probability of $\mathrm{ZP}^{[-l,r]_0}$ is zero for both $I$ and $I'$ so the claim holds.

    If $[-l,r]_0$ has no overlap with $I$ then both sides are also zero so it also holds. We are left with the case where: $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.

    The following diagram illustrates the situation

    \begin{center}

        \includegraphics{diagram_circle_lemma.pdf}

    \end{center}

    Note that by Claim~\ref{claim:eventindependence} we have

    \begin{align*}

    \end{align*}

    We have $i_*\in I \setminus[-l,r]_0$, and $I\cap[-l,r]_0 = I' \cap [-l,r]_0$. Define $J=I\setminus[-l,r]_0$ and $J'=I'\setminus[-l,r]_0$. We have $|J|<|I|$ so we can apply the induction hypothesis to $J$:

    \begin{align*}

        \P_{J}(\NZ{-l},\NZ{r})

        &=

        1

        - \P_{J}(\Z{-l},\NZ{r})

        - \P_{J}(\Z{r})

        \tag{partition of all events} \\

        &=

        1

        - \P_{J'}(\Z{-l},\NZ{r})

        - \P_{J'}(\Z{r}) \\

        + \mathcal{O}(p^{d(i_*,r)+1-|J|}) \\

        &=

        \P_{J'}(\NZ{-l},\NZ{b})

        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|})

    \end{align*}

    Note that the event $\mathrm{ZP}^{[-l,r]_0}$ contains $l+r-1$ zeroes, so $\P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{l+r-1-|I\cap[-l,r]_0|})$. This means

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0})

        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0})

        \left( \P_{I' \setminus [-l,r]_0}(\NZ{a},\NZ{b}) + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|}) \right) \\

        &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I'\setminus [-l,r]_0}(\NZ{a},\NZ{b}) \\

        &\qquad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J| + l+r-1-|I\cap[-l,r]_0|}) \\

        &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})

    \end{align*}

    Where we used Claim~\ref{claim:eventindependence} again.

    Case separation shows that

    $$\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) + l +r \geq d(i_*,0) + 1$$

    The first equality that we have to prove now follows from the fact that the ``zeroes patch'' events are a partition of $\Z{0}$:

    \begin{align*}

        \P_{I}(\Z{0})

        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}

        \P_I(\mathrm{ZP}^{[-l,r]_0})

        \tag{the events are a partition of $\Z{0}$}\\

        &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}

        \P_{I'}(\mathrm{ZP}^{[-l,r]_0})

        + \mathcal{O}(p^{d(i_*,0)+1-|I|})

        \tag{by claim} \\

        &= \P_{I'}(\Z{0}) + \mathcal{O}(p^{d(i_*,0)+1-|I|})

    \end{align*}

    Similarly, we have

    \begin{align*}

        \P_{I}(\Z{0} , \NZ{s})

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})

        \tag{partition of $\Z{0}$}\\

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})

        &=\sum_{l=1}^{n-s}\sum_{r=1}^{i_*-1}

        \P_{I\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})

        \tag{Claim~\ref{claim:eventindependence}}\\

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I\setminus [s,r]_0}(\NZ{r},\NZ{s})

        \tag{$i_*\in I \setminus[s,r]_0$}\\

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\

        &\qquad +\mathcal{O}(p^{\min\left( \dist{r}(i_*,s) , d(i_*,r)\right)+l+r-|I|})

        \tag{same argument as before}\\

        \P_{I'\cap[s,r]_0}(\mathrm{ZP}^{[-l,r]_0},\NZ{s}) \cdot

        \P_{I'\setminus [s,r]_0}(\NZ{r},\NZ{s}) \\

        &\qquad

        &= \P_{I'}(\Z{0} , \NZ{s})

    \end{align*}

    This finishes the proof.

\end{proof}

\begin{definition}[Connected patches]

	Let $\mathcal{P}\subset 2^{\mathbb{Z}}$ be a finite system of finite subsets of $\mathbb{Z}$. We say that the patch set of a resample sequence is $\mathcal{P}$,

	if the connected components of the vertices that have ever become $0$ are exactly the elements of $\mathcal{P}$. We denote by $A^{(\mathcal{P})}$ the event that the set of patches is $\mathcal{P}$. For a patch $P$ let $A^{(P)}=\bigcup_{\mathcal{P}:P\in \mathcal{P}}A^{(\mathcal{P})}$.

\end{definition} 

Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is \emph{exactly} $\mathcal{P}$ whereas $A^{(P)}$ is the event that one of the patches is equal to $P$ but there can be other patches as well.

\begin{definition}[Conditional expectations]

	Let $S\subset\mathbb{Z}$ be a finite slot configuration, and for $f\in\{0,1'\}^{|S|}$ let $I:=S(f)$ be the set of vertices filled with particles.