\newpage

\subsection{Proving the strong cancellation claim}

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

\begin{definition}[Events conditioned on starting state] \label{def:conditionedevents}

    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

    \begin{align*}

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

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

    \end{align*}

\end{definition}

\begin{definition}[Vertex visiting event] \label{def:visitingResamplings}

    Denote by $\mathrm{Z}^{(j)}$ the event that site $j$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(j)}$, i.e. the event that site $j$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(j_1,j_2)} := \mathrm{NZ}^{(j_1)} \cap \mathrm{NZ}^{(j_2)}$, i.e. the event that \emph{both} $j_1$ and $j_2$ do not become zero before termination.

\end{definition}

\begin{figure}

	\begin{center}

    	\includegraphics{diagram_groups.pdf}

    \end{center}

    \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependence}. Here $b_1,b_2\in\{0,1\}^n$ are bitstrings such that all zeroes of $b_1$ and all zeroes of $b_2$ are separated by two indices $j_1,j_2$.}

\end{figure}

\begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}

    Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. Let $j_1$, $j_2$ be any indices inbetween the groups, such that $b_1$ lies on one side of them and $b_2$ on the other, as shown in the figure. Furthermore, let $A_1$ be any event that depends only on the sites ``on the $b_1$ side of $j_1,j_2$'', and similar for $A_2$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have

    \begin{align*}

        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)}, A_1, A_2)

        &=

        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)}, A_1)

        \; \cdot \;

        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)}, A_2) \\

        \mathbb{P}_b(A_1, A_2 \mid \mathrm{NZ}^{(j_1,j_2)})

        &=

        \mathbb{P}_{b_1}(A_1 \mid \mathrm{NZ}^{(j_1,j_2)})

        \; \cdot \;

        \mathbb{P}_{b_2}(A_2 \mid \mathrm{NZ}^{(j_1,j_2)}) \\

        R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}

        &=

        R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1}

        \; + \;

        R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2}

    \end{align*}

    up to any order in $p$.

\end{lemma}

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

\begin{proof}

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

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

    Vice versa, any two 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$.

    For a fixed $\xi_1,\xi_2$ we will 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*}

    where both sums are over $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ terms.

    This is best explained by an example. Lets consider the following fixed $\xi_1,\xi_2$ and an example interleaving where we choose steps from $\xi_2,\xi_1,\xi_1,\xi_2,\cdots$:

    \begin{align*}

        \xi_1 &= \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_2 &= \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   &= \left( (z_1 + z_1', s_1', r_1'), (z_1+z_2', s_1, r_1), (z_2+z_2', s_2, r_2), (z_3+z_2', s_2', r_2'), \cdots \right)

    \end{align*}

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

    \begin{align*}

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

    \end{align*}

    and similar for $\xi_2$ but with primes.

    The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $\xi$ in the example above.

    \begin{center}

        \includegraphics{diagram_paths2.pdf}

    \end{center}

    For the labels shown within the grid, define $p_{ij} = \frac{z_i}{z_i + z_j'}$.

    The probability of $\xi$ is given by

    \begin{align*}

        \P_b[\xi] &= \frac{1}{z_1+z_1'} \P(r_1') \frac{1}{z_1+z_2'} \P(r_1) \frac{1}{z_2+z_2'} \P(r_2) \frac{1}{z_3+z_2'} \P(r_2') \cdots \tag{by definition}\\

        &=

        \frac{z_1'}{z_1+z_1'} \frac{1}{z_1'} \P(r_1') \;

        \frac{z_1 }{z_1+z_2'} \frac{1}{z_1 } \P(r_1 ) \;

        \frac{z_2 }{z_2+z_2'} \frac{1}{z_2 } \P(r_2 ) \;

        \frac{z_2'}{z_3+z_2'} \frac{1}{z_2'} \P(r_2')

        \cdots \tag{rewrite fractions}\\

        &=

        \frac{z_1'}{z_1+z_1'} \;

        \frac{z_1 }{z_1+z_2'} \;

        \frac{z_2 }{z_2+z_2'} \;

        \frac{z_2'}{z_3+z_2'}

        \cdots

        \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $\P_{b_i}[\xi_i]$} \\

        &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $p_{i,j}$} \\

        &= \P(\text{path in grid}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2]

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

        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2)

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

        &= \sum_{\substack{\xi_1\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1}} \;\;

          \sum_{\substack{\xi_2\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}

        \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\

        &=

        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)

        \; \cdot \;

        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).

    \end{align*}

    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.

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

    \begin{align*}

        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}

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

        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}

          \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}

	   	For a configuration $C\subseteq [n]$ we call the connected components of $[n]\setminus N_1(C)$ the gaps. We denote by $m_C$ the number of gaps.

	   	We call a non-empty subset $B\subset C$ a block if $N_3(B)\cap C=B$ and $B$ is minimal, i.e., there is no proper subset $\emptyset\neq B'\subsetneq B$ satisfying $N_3(B')\cap C=B'$. 

	   	Observe that whenever $m_C\geq 2$ the number of blocks is the same as the number of gaps.  

    \end{definition}

    \begin{definition}[Crossings]

    	We say that a run (path) of the resampling procedure crosses $i\in[n]$ if there is ever a $0$ in $N_1({i})$ during the run.

    \end{definition}

    \begin{definition}[Enumerating gaps and mid points]

		Let $G_1,G_2,\ldots, G_{m_C}$ be an enumeration of the gaps respecting the cyclic ordering, and let $g_i$ be the middle element of $G_i$, if there are two middle elements we choose the smaller according to the cyclic ordering. (If $m_C=1$ and $G_1=[n]$ let $g_1=1$.)

		If $m_C\geq 2$ then for all $i\in[m_C]$ let $B_i$ be the block between $G_i$ and $G_{i+1}$.

    \end{definition}

    As in Mario's proof I use the observation that 

    \begin{align*}

    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_b(p)\\

    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p),

    \end{align*}

    where we denote by $C\subseteq[n]$ a slot configuration, whereas $C(f)$ denotes the slots of $C$ filled with the particles described by $f$. 

    For $a\in\{\text{crossed},\text{not crossed}\}^m$ we also introduce the notation $R^a_{C(f)}(p):=\mathbb{E}(\#\{\text{resamples before reaching }\mathbbm{1} \text{ from } C(f)\}|\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)\cdot\mathbb{P}(\bigwedge_{j\in[m_C]}g_j \text{ is } a_j)$, which we define as $0$ if the conditioning event has $0$ probability. 

    Since $$R_{C(f)}(p)=\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}R^a_{C(f)}(p),$$ we can further rewrite the expectation as

    \begin{align*}

	    R^{(n)}(p) &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{a\in\{\text{crossed},\text{not crossed}\}^{m_C}}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p).

    \end{align*}

    Suppose that $a$ contains at least two ``not crossed'', the we claim that $\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)=0$. Let $j_1\neq j_2$ be two distinct indexes such that $a_{j_1}$ and $a_{j_2}$ are both saying ``not crossed''. Let $B_l:=B_{j_1}\cup B_{j_1+1}\cup\cdots\cup B_{j_2-1}$ and $B_r:=B_{j_2}\cup B_{j_2+1}\cup\cdots\cup B_{j_1-1}$ (again we interpret indexes mod $m_C$).

    Then we claim that for all $f\in\{0,1'\}^{|C|}$ we have 

    that 

    \begin{equation}\label{eq:keyIndependceOld}

		R^a_{C(f)}(p)=R^a_{B_l(f)}(p)+R^a_{B_r(f)}(p).

    \end{equation} 

    The reason is as before that the halves are independent because neither $g_{j_1}$ nor $g_{j_2}$ is crossed. One could probably similarly prove it as the grid figure shows. 

    From here the proof goes just as in Mario's proof:

    \begin{align*}

    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R^a_{C(f)}(p)&=

    \sum_{f_l\in\{0,1'\}^{|B_l|}} \sum_{f_r\in\{0,1'\}^{|B_r|}}  (-1)^{|f_l|+|f_r|}p^{|B_l|+|B_r|} \left( R^a_{B_l(f)} + R^a_{B_r(f)} \right)\\

    &= p^{|C|}\sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} R^a_{B_l(f)} \sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} \\

    &\quad + p^{|C|}\sum_{f_r\in\{0,1'\}^{|B_r|}} (-1)^{|f_r|} R^a_{B_r(f)} \sum_{f_l\in\{0,1'\}^{|B_l|}} (-1)^{|f_l|} \\

    &= 0 

    \end{align*}

    From this it follows that the only contribution comes from paths that cross all but one (or all) of the mid gaps. This then implies that it is enough to consider $\mathcal{O}(k)$ length configurations. (We define the length of a configuration $C$ as $n-\max_{j\in[m_C]}|G_j|$.)

    Note that the heart of the proof is \eqref{eq:keyIndependceOld}, so this is what we should double check.

    In fact I think the independence that we use in \eqref{eq:keyIndependceOld} can be also proven when we define a crossing as crossing the actual point, and not its $1$-neighborhood. It then would make it possible to define blocks as consecutive slacks. Also then we could actually use all points of the gaps not only the mid points. The requirement for the cancellation would be that there are ``not crossed'' labels from at least two distinct gaps. This would probably lead to the optimal $k+1$ bound giving the actual statement \ref{it:const}. 

    Speculation: The $n=k$ case would then probably not work because the all $0$ starting configuration is invariant under rotations.

    To actually go below $2k$ one needs to be careful, because there are periodic configurations that are invariant under some rotations causing double counting issues. This can be probably resolved by showing that when a pattern becomes periodic for some $n$ it actually produces periodicity times more expectation due to symmetry. But this is all just speculation.

\end{comment}

	\bibliographystyle{alpha}

	\bibliography{Resample.bib}

\end{document}