\draw (-1,0)+(-0.5,-1) rectangle +(2.6,1);

    \draw[anchor=west] (-1,0)    node {$I\cap [{\color{gray}n}{-l},r]_0$};

    \draw[anchor=west] (-1,-0.5) node {$I\setminus[{\color{gray}n}{-l},r]_0$};

    \draw ({-5*\step}:\r+1) +(0.2,-0.2) node {${\color{gray}n}{-l}$};

    \draw ({4*\step}:\r+1) +(0.2,0.2) node {$r$};

    % n-1

    \draw ({-1*\step}:\r-0.3) +(-0.4,0) node {${\color{gray}n}{-1}$};

    % j

    \draw[->] ({0*\step}:\r-1.3) -- ({0*\step}:\r-0.8);

    \draw ({0*\step}:\r-1) +(-0.4,0) node {$j$};

\renewcommand{\P}{\mathbb{P}}

\newcommand{\NZ}[1]{\mathrm{NZ}^{(#1)}}

\newcommand{\Z}[1]{\mathrm{Z}^{(#1)}}

%\newcommand{\dist}[1]{d_{\!\!\not\,#1}}

\newcommand{\dist}[1]{d_{\neg #1}}

\newcommand{\todo}[1]{{\color{red}\textbf{TODO:} #1}}

It is useful to introduce some new notation. Note that an \emph{event} is a subset of all possible paths of the Markov Chain.

    For any state $b\in\{0,1\}^n$, define $\textsc{start}(b)$ as the event that the starting state of the chain is the state $b$. For any event $A$, define

        \mathbb{P}_b(A) &= \mathbb{P}(A \;|\; \textsc{start}(b)) \\

        R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b))

    The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.

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

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

    \end{align*}

\end{lemma}

\begin{proof}

    We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{j})=0$ and

    \begin{align*}

        \P_{I}(\Z{j})       &= \mathcal{O}(p^{d(i_*,j)}) \\

        \P_{I}(\Z{j},\NZ{s}) &= \mathcal{O}(p^{\dist{s}(i_*,j)})

    \end{align*}

    simply because a chain of zeroes has to be formed between $i_*$ and $j$, and in the second case this chain can not go through $s$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.

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

    %If we refer to only $[a,b]$ then we mean $\{a,a+1,...,b\}$ where numbers are considered modulo $n$. So $[a,b]$ and $[b,a]$ are different intervals that cover the circle together.

    Without loss of generality, we can assume that $0=j < i_* < s < n$. We will now consider intervals around vertex 0.

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

    Claim:

    \begin{align*}

        \P_{I}(\mathrm{ZP}^{[-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*}

    \todo{These special cases.}

    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|})$.

    If $-l\in I$ or $r\in I$ then the left hand side is zero so the claim holds.

    If $[-l,r]_0$ has no overlap with $I$ then both sides of the above expression are 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*}

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

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

        &\quad + \mathcal{O}(p^{\dist{r}(i_*,-l)+1-|J|})

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

    Case separation shows that $\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) \geq d(i_*,0) + 1$ \todo{prove.}

    Now we can prove the required equalities:

    \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^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|}) \\

        &= \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}^{s}

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

        + \mathcal{O}(p^{something}) \\

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

        + \sum_{l=1}^{n-s}\sum_{r=1}^{s} + \mathcal{O}(p^{something})

    \end{align*}

    \todo{finish details}

\end{proof}