Changeset - 241841a8e5cd
Parent rev.
Child rev.
[Not reviewed]
0 1 0
Andras Gilyen - 8 years ago 2017-09-06 21:13:54
gilyen@clayoquot.swat.cwi.nl
n=2k stabilization
1 file changed with 183 insertions and 121 deletions:
main.tex
183
121
0 comments (0 inline, 0 general)
main.tex
➞
Show inline comments
 
@@ -187,13 +187,13 @@
 
        			= \frac{1-q^3}{3q^3}\\
 
    	R^{(4)}(p) &= \frac{p(6-12p+10p^2-3p^3)}{6(1-p)^4}
 
                    = \frac{(1-q)(1+q+q^2+3q^3)}{6q^4}\\
 
        R^{(5)}(p) &= \frac{p(90-300p+435p^2-325p^3+136p^4-36p^5+6p^6)}{15(1-p)^5(6-2p+p^2)}\\
 
                   &= \frac{(1-q)(6+5q+6q^2+21q^3+46q^4+6q^6)}{15q^5(5+q^2)}
 
    \end{align*}
 
    For $n=3$ the system becomes very simple because regardless of the current state, the probability of going to $111$ is always equal to $(1-p)^3$. Therefore the expected number of resamplings is simply the expectation of a geometric distribution. This gives the formula for $R^{(3)}(p)$ as shown above. Note that the $k$-th coefficient of the powerseries of a function $f(p)$ is given by $\frac{1}{k!}\left.\frac{d^k f}{dp^k}\right|_{p=0}$, i.e. the $k$-th derivative to $p$ evaluated at $0$ divided by $k!$. For the function $R^{(3)}(p) = (1-p)^{-3} - 1$ this yields $a^{(3)}_k = (k+2)(k+1)/6$ for $k\geq 1$ and $a^{(3)}_0=0$.
 
    For $n=3$ the system becomes very simple because regardless of the current state, the probability of going to $111$ is always equal to $(1-p)^3$. Therefore the expected number of resamplings is simply the expectation of a geometric distribution. This gives the formula for $R^{(3)}(p)$ as shown above. Note that the $k$-th coefficient of the powerseries of a function $f(p)$ is given by $\frac{1}{k!}\left.\frac{d^k f}{dp^k}\right|_{p=0}$, i.e. the $k$-th derivative to $p$ evaluated at $0$ divided by $k!$. For the function $R^{(3)}(p) =\frac{(1-p)^{-3} - 1}{3} $ this yields $a^{(3)}_k = (k+2)(k+1)/6$ for $k\geq 1$ and $a^{(3)}_0=0$.
 

			




	
	
	
		
 
    We can do the same for $n=4,5$, which gives, for $k\geq 1$ (with Mathematica):

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        a^{(3)}_k &= \frac{(k+2)(k+1)}{6}\\

			




	
	
	
		
 
        a^{(4)}_k &= \frac{1}{6}\left(2+\frac{(k+3)(k+2)(k+1)}{6}\right)\\

			




	
	
	
		
 
        a^{(5)}_k &= \frac{1}{15}\left(\frac{(k+4)(k+3)(k+2)(k+1)}{20} - \frac{(k+3)(k+2)(k+1)}{30} - \frac{(k+2)(k+1)}{50} + \frac{76(k+1)}{25}\right.\\

			




	
	
		
 
@@ -611,52 +611,202 @@ Consider the chain (instead of the cycle) for simplicity with vertices identifie

			




	
	
	
		
 
\end{definition}

			




	
	
	
		
 

			




	
	
	
		
 
The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.

			




	
	
	
		
 
\begin{lemma}\label{lemma:probIndep}

			




	
	
	
		
 
	Suppose we have a finite set $I\subset\mathbb{N}_+$ of vertices.

			




	
	
	
		
 
    Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$. These definitions are illustraded in Figure \ref{fig:lemmaillustration}.

			




	
	
	
		
 
	Then $P_{I}(Z^{(0)})=P_{I'}(Z^{(0)}) + O(p^{I_{\max}+1-|I|})$.

			




	
	
	
		
 
	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{I'}(\Z{0}) = O(p^{I_{\max}-|I'|})$.

			




	
	
	
		
 
\end{lemma}

			




	
	
	
		
 
\begin{proof}

			




	
	
	
		
 
\begin{figure}

			




	
	
	
		
 
	\begin{center}

			




	
	
	
		
 
    	\includegraphics{diagram_proborders.pdf}

			




	
	
	
		
 
    \end{center}

			




	
	
	
		
 
    \caption{\label{fig:lemmaillustration} Illustration of setup of Lemma \ref{lemma:probIndep}.}

			




	
	
	
		
 
\end{figure}

			




	
	
	
		
 
	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples vertex $0$ to zero must produce at least $I_{\max}$ zeroes in-between.

			




	
	
	
		
 
	

			




	
	
	
		
 
    Induction step: For an event $A$ and $k>0$ let us denote $A_k = A\cap\left(\cap_{j=0}^{k-1} \mathrm{Z}^{(j)}\right)\cap \mathrm{NZ}^{(k)}$, i.e. $A_k$ is the event $A$ \emph{and} ``Each vertex in $0,1,2,\ldots, k-1$ becomes $0$ at some point before termination (either by resampling or initialisation), but vertex $k$ does not''. Observe that these events form a partition, so $Z^{(0)}=\dot{\bigcup}_{k=1}^{\infty}Z^{(0)}_k$.

			




	
	
	
		
 
    Induction step: For an event $A$ and $k>0$ let us denote $A_k = A\cap\left(\cap_{j=0}^{k-1} \mathrm{Z}^{(j)}\right)\cap \mathrm{NZ}^{(k)}$, i.e. $A_k$ is the event $A$ \emph{and} ``Each vertex in $0,1,2,\ldots, k-1$ becomes $0$ at some point before termination (either by resampling or initialisation), but vertex $k$ does not''. Observe that these events form a partition, so $\Z{(0)}=\dot{\bigcup}_{k=1}^{\infty}\Z{(0)}_k$.

			




	
	
	
		
 
    Let $I_{<k}:=I\cap[1,k-1]$ and similarly $I_{>k}:=I\setminus[1,k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$ (note that $I_{><} = \gaps{I}$ as shown in Figure \ref{fig:diametergap}). Suppose we have proven the claim up to $|I|-1$, then the induction step can be shown by

			




	
	
	
		
 
	\begin{align*}

			




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

			




	
	
	
		
 
		&=\sum_{k=1}^{\infty}P(Z^{(0)}_k) \tag{the events are a partition}\\

			




	
	
	
		
 
        &=\sum_{k\in \mathbb{N}\setminus I}P(Z^{(0)}_k) \tag{$\mathbb{P}(A_k)=0$ for $k\in I$}\\

			




	
	
	
		
 
        &=\sum_{k\in\mathbb{N}\setminus I}P_{I_{<k}}(Z^{(0)}_k)\cdot P_{I_{>k}}(\mathrm{NZ}^{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\

			




	
	
	
		
 
        &=\sum_{k\in I_{><}}P_{I_{<k}}(Z^{(0)}_k)\cdot P_{I_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})

			




	
	
	
		
 
		\tag{$k<I_{\min}\Rightarrow P_{I_{<k}}(Z^{(0)}_k)=0$}\\

			




	
	
	
		
 
        &=\sum_{k\in I_{><}}P_{I'_{<k}}(Z^{(0)}_k)\cdot P_{I_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})	

			




	
	
	
		
 
		\P^\infty_{I}(\Z{(0)})

			




	
	
	
		
 
		&=\sum_{k=1}^{\infty}\P^\infty(\Z{(0)}_k) \tag{the events are a partition}\\

			




	
	
	
		
 
        &=\sum_{k\in \mathbb{N}\setminus I}\P^\infty(\Z{(0)}_k) \tag{$\mathbb{\P^\infty}(A_k)=0$ for $k\in I$}\\

			




	
	
	
		
 
        &=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\mathrm{NZ}^{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\

			




	
	
	
		
 
        &=\sum_{k\in I_{><}}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})

			




	
	
	
		
 
		\tag{$k<I_{\min}\Rightarrow \P^\infty_{I_{<k}}(\Z{(0)}_k)=0$}\\

			




	
	
	
		
 
        &=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})	

			




	
	
	
		
 
		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\

			




	
	
	
		
 
		&=\sum_{k\in I_{><}}P_{I'_{<k}}(Z^{(0)}_k)\cdot

			




	
	
	
		
 
        \left(P_{I'_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}-k+1-|I_{>k}|})\right) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{by induction, since for $k>I_{\min}$ we have $|I_{<k}|<|I|$}\\

			




	
	
	
		
 
		&=\sum_{k\in I_{><}}P_{I'_{<k}}(Z^{(0)}_k)\cdot

			




	
	
	
		
 
        P_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	

			




	
	
	
		
 
		\tag{as $P_{I'_{<k}}(Z^{(0)}_k)=\mathcal{O}(p^{k-|I'_{<k}|})$}\\

			




	
	
	
		
 
		&=\sum_{k\in\mathbb{N}\setminus I}P_{I'_{<k}}(Z^{(0)}_k)\cdot

			




	
	
	
		
 
        P_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\

			




	
	
	
		
 
		&=\sum_{k\in\mathbb{N}\setminus I'}P_{I'_{<k}}(Z^{(0)}_k)\cdot

			




	
	
	
		
 
        P_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow P_{I'_{<k}}(Z^{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\

			




	
	
	
		
 
		&=P_{I'}(Z^{(0)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{analogously to the beginning}			

			




	
	
	
		
 
		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

			




	
	
	
		
 
        \left(\P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}-k+1-|I_{>k}|})\right) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{by induction, since for $k>I_{\min}$ we have $|I_{<k}|<|I|$}\\

			




	
	
	
		
 
		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

			




	
	
	
		
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	

			




	
	
	
		
 
		\tag{as $\P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{k-|I'_{<k}|})$}\\

			




	
	
	
		
 
		&=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

			




	
	
	
		
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\

			




	
	
	
		
 
		&=\sum_{k\in\mathbb{N}\setminus I'}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot

			




	
	
	
		
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\

			




	
	
	
		
 
		&=\P^\infty_{I'}(\Z{(0)}) +\mathcal{O}(p^{I_{\max}-|I'|})	\tag{analogously to the beginning}			

			




	
	
	
		
 
	\end{align*}

			




	
	
	
		
 
\end{proof}

			




	
	
	
		
 
\begin{corollary}\label{cor:probIndep}

			




	
	
	
		
 
	Suppose $I,J\subset\mathbb{N}_+$ are finite sets of vertices, and let $m=\min(\Delta(I,J))$.

			




	
	
	
		
 
	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{J}(\Z{0}) = O(p^{|[m]\cap I\cap J|})$.

			




	
	
	
		
 
\end{corollary}

			




	
	
	
		
 

			




	
	
	
		
 
	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. 

			




	
	
	
		
 
	%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 cycle.

			




	
	
	
		
 

			




	
	
	
		
 
\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})}$ denote the event that one of the patches is equal to $P$ but there can be other patches as well.

			




	
	
	
		
 
	As a shorthand we are going to use the notation $P\in \mathcal{P}$ for the event $A^{(P)}$.

			




	
	
	
		
 
\end{definition} 

			




	
	
	
		
 

			




	
	
	
		
 
\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 a particle (i.e. $1'$). 

			




	
	
	
		
 
	Then we define

			




	
	
	
		
 
	$$R_I:=\mathbb{E}[\#\{\text{resamplings when started from inital state }I\}],$$ 

			




	
	
	
		
 
	and similarly for a patch $P$ we define

			




	
	
	
		
 
	$$R^{(P)}_I:=\mathbb{E}[\#\{\text{resamplings inside }P\text{ when started from inital state }I\}|A^{(P)}].$$	

			




	
	
	
		
 
\end{definition} 

			




	
	
	
		
 

			




	
	
	
		
 
 	\begin{lemma}Suppose $I\subseteq [k]$, then on the infinite chain

			




	
	
	
		
 
		$$\P^\infty_I(\Z{1}\cap \Z{k})=\P^\infty_I(\Z{1})\P^\infty_I(\Z{k})+\mathcal{O}(p^{k-|I|}).$$

			




	
	
	
		
 
	\end{lemma}   

			




	
	
	
		
 
	Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:

			




	
	
	
		
 
	$$\P^\infty_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1})\P^\infty_I(\NZ{k})+\mathcal{O}(p^{k-|I|}).$$

			




	
	
	
		
 
	\begin{proof}

			




	
	
	
		
 
		We proceed by induction on $|I|$. For $|I|=0$ the statement is trivial.

			




	
	
	
		
 
		

			




	
	
	
		
 
		Now observe that:

			




	
	
	
		
 
		$$\P^\infty_I(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^\infty_I(P\in\mathcal{P})$$

			




	
	
	
		
 
		$$\P^\infty_I(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^\infty_I(P\in\mathcal{P})$$

			




	
	
	
		
 
		

			




	
	
	
		
 
		Suppose we proved the statement for all $\ell< |I|$, then we proceed using induction similarly to the above (let us use the notation $>I<:=I\cap \overline{P_l}\cap \overline{P_r}$ for simplicity)

			




	
	
	
		
 
		\begin{align*}

			




	
	
	
		
 
		&\P^\infty_I(\Z{1}\cap \Z{k})=\\

			




	
	
	
		
 
		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_I(P_l,P_r\in\mathcal{P})

			




	
	
	
		
 
		+\sum_{P\text{ patch}\,:\,1,k\in P}\P^\infty_I(P\in\mathcal{P})\\

			




	
	
	
		
 
		&=\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_I(P_l,P_r\in\mathcal{P})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
		\P^\infty_{>I<}(\NZ{P_l^{\max}+1}\cap \NZ{P_r^{\min}-1})

			




	
	
	
		
 
		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&\overset{\text{induction}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
		\P^\infty_{> I <}(\NZ{P_l^{\max}+1})\P^\infty_{> I <}(\NZ{P_r^{\min}-1})

			




	
	
	
		
 
		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&\overset{Corrolary~\ref{cor:probIndep}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
		\P^\infty_{I\setminus P_l}(\NZ{P_l^{\max}+1})\P^\infty_{I\setminus P_r}(\NZ{P_r^{\min}-1})

			




	
	
	
		
 
		\P^\infty_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{P_l\neq P_r\text{ patches}\,:\,1\in P_l,k\in P_r}

			




	
	
	
		
 
		\P^\infty_{I}(P_l\in\mathcal{P})

			




	
	
	
		
 
		\P^\infty_{I}(P_r\in\mathcal{P})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&=\left(\sum_{P_l\text{ patch}\,:\,1\in P_l}\P^\infty_{I}(P_l\in\mathcal{P})\right)

			




	
	
	
		
 
		\left(\sum_{P_r\text{ patch}\,:\,k\in P_r}\P^\infty_{I}(P_r\in\mathcal{P})\right)

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|})\\

			




	
	
	
		
 
		&=\P^\infty_I(\Z{1})\P^\infty_I(\Z{k})

			




	
	
	
		
 
		+\mathcal{O}(p^{k-|I|}).	

			




	
	
	
		
 
		\end{align*}

			




	
	
	
		
 
	\end{proof}

			




	
	
	
		
 
	

			




	
	
	
		
 
	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.

			




	
	
	
		
 
	\begin{corollary}\label{cor:independenetSides}

			




	
	
	
		
 
		Let $k>0$ and $d:=\lfloor\frac{k}{2}\rfloor$, then 

			




	
	
	
		
 
		\begin{align*}

			




	
	
	
		
 
		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

			




	
	
	
		
 
		=\left(\sum_{\underset{|S|<\infty}{S\subseteq \mathbb{N}_+}}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!\!2}

			




	
	
	
		
 
		+\mathcal{O}(p^{d}).

			




	
	
	
		
 
		\end{align*}

			




	
	
	
		
 
	\end{corollary}

			




	
	
	
		
 
	(Question: is the above is true with $d=k$?)

			




	
	
	
		
 
	

			




	
	
	
		
 
	\begin{proof}

			




	
	
	
		
 
		Let $[-d]:=\{k-d+1,\ldots, k\}$ and $[\pm d]:=[d]\cup [-d]$. By the above statement we know that

			




	
	
	
		
 
		\begin{align}\label{eq:intervalIndep}

			




	
	
	
		
 
		\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1}\cap \NZ{k})

			




	
	
	
		
 
		=\sum_{S\subseteq [k]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{k}).

			




	
	
	
		
 
		\end{align}

			




	
	
	
		
 
		Now suppose $s\in S\subseteq[k]$ such that $s\notin [\pm d]$, then 

			




	
	
	
		
 
		\begin{align*}

			




	
	
	
		
 
		&\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{k})\\

			




	
	
	
		
 
		&=\sum_{f_{\overline{s}}\in\{0,1'\}^{|S|-1}}\rho_{S\setminus\{s\}(f_{\overline{s}})} \left(p\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=0)}(\NZ{k})-p\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{1})\P^\infty_{S(f_{\overline{s}},f_s=1)}(\NZ{k})\right)\\

			




	
	
	
		
 
		&=\mathcal{O}(p^{d}). \tag{by Corollary~\ref{cor:probIndep}}

			




	
	
	
		
 
		\end{align*}

			




	
	
	
		
 
		Therefore we can see that 

			




	
	
	
		
 
		\begin{align*}

			




	
	
	
		
 
		\eqref{eq:intervalIndep}&=\sum_{S\subseteq [\pm d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\mathcal{O}(p^{d})\\

			




	
	
	
		
 
		&=\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\sum_{S'\subseteq [d]}\sum_{f'\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\rho_{S'(f')}\P^\infty_{S'(f')}(\NZ{k})+\mathcal{O}(p^{d}) \tag{Corollary \ref{cor:probIndep}}\\

			




	
	
	
		
 
		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)

			




	
	
	
		
 
		\left(\sum_{S'\subseteq [-d]}\sum_{f'\in\{0,1'\}^{|S'|}}\rho_{S'(f')} \P^\infty_{S'(f')}(\NZ{k})\right)

			




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

			




	
	
	
		
 
		&=\left(\sum_{S\subseteq [d]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!2}

			




	
	
	
		
 
		+\mathcal{O}(p^{d})\tag{by symmetry}\\		

			




	
	
	
		
 
		&=\left(\sum_{\underset{|S|<\infty}{S\subseteq \mathbb{N}_+}}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\right)^{\!\!2}

			




	
	
	
		
 
		+\mathcal{O}(p^{d}).\tag{Corollary \ref{cor:probIndep}}

			




	
	
	
		
 
		\end{align*}

			




	
	
	
		
 
	\end{proof}

			




	
	
	
		
 
	

			




	
	
	
		
 
	\begin{remark}\label{rem:cycleContained}

			




	
	
	
		
 
		For all $n\geq k$ and $I\subseteq [k]$ we have that 

			




	
	
	
		
 
		$$\P^n_I(\NZ{1}\cap \NZ{k})=\P^\infty_I(\NZ{1}\cap \NZ{k}).$$

			




	
	
	
		
 
	\end{remark}

			




	
	
	
		
 
	

			




	
	
	
		
 
	

			




	
	
	
		
 
	\begin{theorem}

			




	
	
	
		
 
		Suppose $n,m\geq 2k$, then $R^{(n)}-R^{(m)}=\mathcal{O}(p^{k})$.

			




	
	
	
		
 
	\end{theorem}

			




	
	
	
		
 
	\begin{proof}

			




	
	
	
		
 
		\begin{align*}

			




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

			




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

			




	
	
	
		
 
		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \sum_{v\in[n]}\sum_{t=1}^{\infty}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step})\\

			




	
	
	
		
 
		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}\rho_{S(f)} \sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}\P_{S(f)}(v \text{ is resampled in the }t\text{-th step and }P\text{ is a patch})\\

			




	
	
	
		
 
		&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
		\rho_{S(f)} \sum_{P\text{ patch}} R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\  

			




	
	
	
		
 
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
		\rho_{S(f)}  R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) + \mathcal{O}(p^{k}) \tag{by translation symmetry}\\   

			




	
	
	
		
 
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
		\rho_{S(f)}  R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \mathcal{O}(p^{k})  \tag{by Lemma~\ref{claim:eventindependence}}\\   	

			




	
	
	
		
 
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq P}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})

			




	
	
	
		
 
		\sum_{S'\subseteq \overline{P}}\sum_{f'\in\{0,1'\}^{|S'|}}\P_{S'(f')}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \mathcal{O}(p^{k}) \\  

			




	
	
	
		
 
		&= \sum_{\underset{P_{\max}\leq k}{\underset{P_{\min}=1}{P\text{ patch}}}}\sum_{S\subseteq P}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
		\rho_{S(f)}  R^{(P)}_{S(f)}\P_{S(f)}(A^{(P)})\left(\sum_{\underset{|S'|<\infty}{S'\subseteq \mathbb{N}_+}}\sum_{f'\in\{0,1'\}^{|S'|}}\rho_{S'(f')} \P^\infty_{S'(f')}(\NZ{1})\right)^{\!\!2}

			




	
	
	
		
 
		+\mathcal{O}(p^{k}).\tag{By Corollary \ref{cor:independenetSides} with $k=|\overline{P}|$ observing			$p^{k}=\mathcal{O}(p^{|P|+\lfloor\frac{|\overline{P}|}{2}\rfloor})$.}	

			




	
	
	
		
 
		\end{align*}

			




	
	
	
		
 
		Since the above expression is independent of $n$ the statement follows.

			




	
	
	
		
 
	\end{proof}

			




	
	
	
		
 
	

			




	
	
	
		
 
	

			




	
	
	
		
 
	%Final observation: Suppose $S={a,b}$ 

			




	
	
	
		
 
	%    \begin{align*}

			




	
	
	
		
 
	%    &\sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)}\cap \NZ{(P_{\max}+1)})  \\

			




	
	
	
		
 
	%    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)}) \mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\

			




	
	
	
		
 
	%    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}}  \rho_{a_f}\mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\min}-1)})  \rho_{b_f}\mathbb{P}_{S(f_{\overline{P}})}(\NZ{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\

			




	
	
	
		
 
	%    \end{align*}

			




	
	
	
		
 
	

			




	
	
	
		
 
	~

			




	
	
	
		
 
	

			




	
	
	
		
 
	Questions:

			




	
	
	
		
 
	\begin{itemize}

			




	
	
	
		
 
		\item Can we generalise the proof to other translationally invariant spaces, like the torus?

			




	
	
	
		
 
		\item In view of this proof, can we better characterise $a_k^{(k+1)}$?

			




	
	
	
		
 
		\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

			




	
	
	
		
 
	\end{itemize} 

			




	
	
	
		
 

			




	
	
	
		
 
~

			




	
	
	
		
 
	%I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.

			




	
	
	
		
 

			




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

			




	
	
	
		
 
    Then

			




	
	
	
		
 
    \begin{align*}

			




	
	
		
 
@@ -778,30 +928,12 @@ Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the in

			




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

			




	
	
	
		
 
        +\mathcal{O}(p^{\min\left( i_* , s-i_* \right) +1-|I|})

			




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

			




	
	
	
		
 
	Then we define

			




	
	
	
		
 
	$$R_I:=\mathbb{E}[\#\{\text{resamplings when started from inital state }I\}].$$

			




	
	
	
		
 
	For a patch set $\mathcal{P}$ and some $P\in\mathcal{P}$ we define

			




	
	
	
		
 
	$$R^{(\mathcal{P})}_I:=\mathbb{E}[\#\{\text{resamplings when started from inital state }I\}|A^{(\mathcal{P})}]$$	

			




	
	
	
		
 
	and 

			




	
	
	
		
 
	$$R^{(P,\mathcal{P})}_I:=\mathbb{E}[\#\{\text{resamplings inside }P\text{ when started from inital state }I\}|A^{(\mathcal{P})}]$$		

			




	
	
	
		
 
	finally

			




	
	
	
		
 
	$$R^{(P)}_I:=\mathbb{E}[\#\{\text{resamplings inside }P\text{ when started from inital state }I\}|A^{(P)}].$$	

			




	
	
	
		
 
\end{definition} 

			




	
	
	
		
 

			




	
	
	
		
 
    Similarly to Mario's proof I use the observation that 

			




	
	
	
		
 
    \begin{align*}

			




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

			




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

			




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

			




	
	
	
		
 
    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{(\mathcal{P})}) R^{(\mathcal{P})}_{S(f)} \\

			




	
	
		
 
@@ -811,16 +943,16 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is

			




	
	
	
		
 
    \sum_{\mathcal{P}\text{ patches}} \mathbb{P}_{S(f)}(A^{\mathcal{P}}) \sum_{P\in\mathcal{P}} R^{(P)}_{S(f)\cap P}\tag{by Claim~\ref{claim:eventindependence}}\\ 

			




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

			




	
	
	
		
 
    \sum_{P\text{ patch}} R^{(P)}_{S(f)\cap P}\sum_{\mathcal{P}:P\in\mathcal{P}}\mathbb{P}_{S(f)}(A^{\mathcal{P}})\\     

			




	
	
	
		
 
    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
     \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)}(A^{(P)}) \tag{by definition}\\        

			




	
	
	
		
 
    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f\in\{0,1'\}^{|S|}}

			




	
	
	
		
 
    \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \tag{remember Definition~\ref{def:visitingResamplings} and use Claim~\ref{claim:eventindependence}}\\    

			




	
	
	
		
 
    \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)\cap P}(A^{(P)})\mathbb{P}_{S(f)\cap \overline{P}}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}}) \tag{remember Definition~\ref{def:visitingResamplings} and use Claim~\ref{claim:eventindependence}}\\    

			




	
	
	
		
 
    &= \frac{1}{n}\sum_{S\subseteq [n]} \sum_{P\text{ patch}} \sum_{f_P\in\{0,1'\}^{|S\cap P|}}

			




	
	
	
		
 
    \rho_{S(f_P)} R^{(P)}_{S(f_P)} \mathbb{P}_{S(f_P)}(A^{(P)})

			




	
	
	
		
 
    \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}}) \\   

			




	
	
	
		
 
    \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}}) \\   

			




	
	
	
		
 
	&= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{P\text{ patch}}\sum_{f_P\in\{0,1'\}^{|S\cap P|}}

			




	
	
	
		
 
	\rho_{S(f_P)}

			




	
	
	
		
 
        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}|}}\rho_{S(f_{\overline{P}})}\mathcal{O}(p^{|S_{><}|}) \tag{see below} \\

			




	
	
	
		
 
	&= \frac{1}{n}\sum_{S\subseteq [n]}\mathcal{O}(p^{|S|+|S_{><}|}).

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
\begin{figure}

			




	
	
		
 
@@ -828,37 +960,37 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is

			




	
	
	
		
 
    	\includegraphics{diagram_patches.pdf}

			




	
	
	
		
 
    \end{center}

			




	
	
	
		
 
    \caption{\label{fig:patches} Illustration of last steps of the proof.}

			




	
	
	
		
 
\end{figure}

			




	
	
	
		
 
    The penultimate inequality can be seen by case separation as follows: If $S\subseteq P$ then there is no splitting into $S\cap P$ and $S\setminus P$, and we already have $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$ simply because the patch $P$ must be filled with zeroes that were not yet in $S$, so this is at least $|S_{><}|$ resampled zeroes. For the more general case, assume that $S$ is larger than $P$ on both sides of $P$. This is illustrated in Figure \ref{fig:patches}. We will focus on the following sum that was in the above equations:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S \cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})

			




	
	
	
		
 
        \sum_{f_{\overline{P}}\in\{0,1'\}^{|S \cap \overline{P}|}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    By Lemma \ref{lemma:eventindependence} we can split this sum into two parts: the part to the left of $P$ and the part to the right of $P$. Define $S_\mathrm{left}=S\cap[S_\mathrm{min},P_{\mathrm{min}}-1]$ and $S_\mathrm{right}=S\cap[P_{\mathrm{max}}+1,S_\mathrm{max}]$, so that $S\cap\overline{P} = S_\mathrm{left} \cup S_\mathrm{right}$. These are also illustrated in Figure \ref{fig:patches}. Then we have

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \mathbb{P}_{S(f_{\overline{P}})}(\overline{Z^{(P_{\min}-1)}}\cap\overline{Z^{(P_{\max}+1)}})

			




	
	
	
		
 
        &= \mathbb{P}_{S(f_{\mathrm{left}})}(\overline{Z^{(P_{\min}-1)}}) \;\cdot\; \mathbb{P}_{S(f_{\mathrm{right}})}(\overline{Z^{(P_{\max}+1)}})

			




	
	
	
		
 
        \mathbb{P}_{S(f_{\overline{P}})}(\overline{\Z{(P_{\min}-1)}}\cap\overline{\Z{(P_{\max}+1)}})

			




	
	
	
		
 
        &= \mathbb{P}_{S(f_{\mathrm{left}})}(\overline{\Z{(P_{\min}-1)}}) \;\cdot\; \mathbb{P}_{S(f_{\mathrm{right}})}(\overline{\Z{(P_{\max}+1)}})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    and hence we can split the sum. Without loss of generality we now only consider the `right' part of the sum:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}} \rho_{S_\mathrm{right}(f)} \mathbb{P}_{S_\mathrm{right}(f)}(\overline{Z^{(P_{\max}+1)}})

			




	
	
	
		
 
        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}} \rho_{S_\mathrm{right}(f)} \mathbb{P}_{S_\mathrm{right}(f)}(\overline{\Z{(P_{\max}+1)}})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Now further split this sum over the value of $f$ at position $S_\mathrm{max}$:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}} \sum_{f'\in\{0,1'\}}

			




	
	
	
		
 
        \rho_{S_\mathrm{right}(f\,f')} \mathbb{P}_{S_\mathrm{right}(f\,f')}(\overline{Z^{(P_{\max}+1)}})

			




	
	
	
		
 
        \rho_{S_\mathrm{right}(f\,f')} \mathbb{P}_{S_\mathrm{right}(f\,f')}(\overline{\Z{(P_{\max}+1)}})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    and we use the definition of $\rho$ for the sum over $f'$:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

			




	
	
	
		
 
        \rho_{S_\mathrm{right}(f)} \left(p \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) + (-p) \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) \right)

			




	
	
	
		
 
        \rho_{S_\mathrm{right}(f)} \left(p \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{\Z{(P_{\max}+1)}}) + (-p) \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) \right)

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Now we recognize the setup of Lemma~\ref{lemma:probIndep} with $I=S_\mathrm{right}(f\,0)$ and $I'=S_\mathrm{right}(f\,1)$. The lemma yields

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{Z^{(P_{\max}+1)}}) &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-(P_{\mathrm{max}}+1)+1-|S_\mathrm{right}|}) \\

			




	
	
	
		
 
        &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{Z^{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) .

			




	
	
	
		
 
        \mathbb{P}_{S_\mathrm{right}(f\, 0)}(\overline{\Z{(P_{\max}+1)}}) &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-(P_{\mathrm{max}}+1)+1-|S_\mathrm{right}|}) \\

			




	
	
	
		
 
        &= \mathbb{P}_{S_\mathrm{right}(f\, 1)}(\overline{\Z{(P_{\max}+1)}}) + \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) .

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Entering this back into the sum gives

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
         \sum_{f\in\{0,1'\}^{|S_\mathrm{right}\setminus\{S_\mathrm{max}\}|}}

			




	
	
	
		
 
        \rho_{S_\mathrm{right}(f)} \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|+1})

			




	
	
	
		
 
         = \sum_{f\in\{0,1'\}^{|S_\mathrm{right}|}}

			




	
	
		
 
@@ -870,82 +1002,12 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is

			




	
	
	
		
 
\mathcal{O}(p^{P_\mathrm{min}-S_{\mathrm{min}}-|S_\mathrm{left}|}) \cdot \mathcal{O}(p^{P_\mathrm{max}-P_\mathrm{min}+1-|S\cap P|}) \cdot \mathcal{O}(p^{S_\mathrm{max}-P_{\mathrm{max}}-|S_\mathrm{right}|}) \\

			




	
	
	
		
 
        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S_\mathrm{left}\cup S_\mathrm{right}\cup (S\cap P)|})\\

			




	
	
	
		
 
        &= \mathcal{O}(p^{S_\mathrm{max}-S_\mathrm{min}+1-|S|})

			




	
	
	
		
 
        = \mathcal{O}(p^{|S_{><}|})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    as required. This finishes the proof.

			




	
	
	
		
 

			




	
	
	
		
 
    ~

			




	
	
	
		
 

			




	
	
	
		
 
	I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.

			




	
	
	
		
 
    

			




	
	
	
		
 
    Questions:

			




	
	
	
		
 
    \begin{itemize}

			




	
	
	
		
 
    	\item Is this proof finally flawless?

			




	
	
	
		
 
    	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?

			




	
	
	
		
 
    	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?

			




	
	
	
		
 
    	\item Can we prove the conjectured formula for $a_k^{(3)}$?		

			




	
	
	
		
 
    \end{itemize} 

			




	
	
	
		
 
    

			




	
	
	
		
 
	\begin{lemma}On the infinite chain

			




	
	
	
		
 
		$$\P_I(Z^{0}\cap Z^{k})=\P_I(Z^{0})\P_I(Z^{k})+\mathcal{O}(p^{k-|I|+1})$$

			




	
	
	
		
 
	\end{lemma}   

			




	
	
	
		
 
    Note that using De Morgan's law and the inclusion-exclusion formula we can see that this is equivalent to saying:

			




	
	
	
		
 
    $$\P_I(NZ^{0}\cap NZ^{k})=\P_I(NZ^{0})\P_I(NZ^{k})+\mathcal{O}(p^{k-|I|+1})$$

			




	
	
	
		
 
    \begin{proof}

			




	
	
	
		
 
    We proceed by induction on $|I|$. For $|I|=0,1$ the statement is trivial.

			




	
	
	
		
 
    

			




	
	
	
		
 
    Now observe that:

			




	
	
	
		
 
    $$\P_I(Z^{0})=\sum_{P\text{ patch}\,:\,0\in P}\P_I(P\in\mathcal{P})$$

			




	
	
	
		
 
    $$\P_I(Z^{k})=\sum_{P\text{ patch}\,:\,k\in P}\P_I(P\in\mathcal{P})$$

			




	
	
	
		
 
    

			




	
	
	
		
 
    Suppose $|I|\geq 2$, then we proceed using induction similarly to the above

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
    &\P_I(Z^{0}\cap Z^{k})\\

			




	
	
	
		
 
    &=\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_I(P_l,P_r\in\mathcal{P})

			




	
	
	
		
 
    +\sum_{P\text{ patch}\,:\,0,k\in P}\P_I(P\in\mathcal{P})\\

			




	
	
	
		
 
    &=\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_I(P_l,P_r\in\mathcal{P})

			




	
	
	
		
 
    +\mathcal{O}(p^{k+1})\\

			




	
	
	
		
 
    &\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
    \P_{> I <}(NZ^{P_l^{\max}+1}\cap NZ^{P_r^{\min}-1})

			




	
	
	
		
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
    +\mathcal{O}(p^{k+1})\\

			




	
	
	
		
 
    &\overset{\text{induction}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
    \P_{> I <}(NZ^{P_l^{\max}+1})\P_{> I <}(NZ^{P_r^{\min}-1})

			




	
	
	
		
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
    +\mathcal{O}(p^{k-|I|+1})\\

			




	
	
	
		
 
    &\overset{Lemma~\ref{lemma:probIndep}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_{I\cap P_l}(P_l\in\mathcal{P})

			




	
	
	
		
 
    \P_{I\setminus P_l}(NZ^{P_l^{\max}+1})\P_{I\setminus P_r}(NZ^{P_r^{\min}-1})

			




	
	
	
		
 
    \P_{I\cap P_r}(P_r\in\mathcal{P})

			




	
	
	
		
 
    +\mathcal{O}(p^{k-|I|+1})\\

			




	
	
	
		
 
    &\overset{Lemma~\ref{claim:eventindependence}}{=}\sum_{\underset{P_l^{\max}+1<P_r^{\min}}{P_l,P_r\text{ patches}\,:\,0\in P_l,k\in P_r}}

			




	
	
	
		
 
    \P_{I}(P_l\in\mathcal{P})

			




	
	
	
		
 
    \P_{I}(P_r\in\mathcal{P})

			




	
	
	
		
 
    +\mathcal{O}(p^{k-|I|+1})\\

			




	
	
	
		
 
    &=\left(\sum_{P_l\text{ patch}\,:\,0\in P_l}

			




	
	
	
		
 
    \P_{I}(P_l\in\mathcal{P})\right)\left(\sum_{P_l\text{ patch}\,:\,0\in P_l}

			




	
	
	
		
 
    \P_{I}(P_l\in\mathcal{P})\right)

			




	
	
	
		
 
    +\mathcal{O}(p^{k-|I|+1})\\

			




	
	
	
		
 
    &=\P_I(Z^{0})\P_I(Z^{k})

			




	
	
	
		
 
    +\mathcal{O}(p^{k-|I|+1}).	

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    \end{proof}

			




	
	
	
		
 

			




	
	
	
		
 
	Final observation: Suppose $S={a,b}$ 

			




	
	
	
		
 
	    \begin{align*}

			




	
	
	
		
 
	    &\sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)}\cap NZ^{(P_{\max}+1)})  \\

			




	
	
	
		
 
	    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}} \rho_{S(f_{\overline{P}})} \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)}) \mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\

			




	
	
	
		
 
 	    &= \sum_{f_{\overline{P}}\in\{0,1'\}^{2}}  \rho_{a_f}\mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\min}-1)})  \rho_{b_f}\mathbb{P}_{S(f_{\overline{P}})}(NZ^{(P_{\max}+1)})   +\mathcal{O}(p^{|\overline{P}|-|S|})\\

			




	
	
	
		
 
	    \end{align*}

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
    

			




	
	
	
		
 
\begin{comment}

			




	
	
	
		
 
    \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}}

			




	
	
	
		
 
    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.

			




	
	
	
		
 
    %\begin{definition}[Resample sequences]

			




	
	
	
		
 
    %	A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-2430102
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support