\documentclass[a4paper,11pt,english,final]{article}

\pdfoutput=1

\usepackage[utf8]{inputenc}

\usepackage[english]{babel}

\usepackage{fullpage}

\usepackage{graphics}

\usepackage{diagbox}

\usepackage[table]{xcolor}% http://ctan.org/pkg/xcolor

\usepackage{graphicx}

\usepackage{caption}

\captionsetup{compatibility=false}

\graphicspath{{./}}

\usepackage{tikz}

\usepackage{amssymb}

\usepackage{mathtools}

\usepackage{bm}

\usepackage{bbm}

%\usepackage{bbold}

\usepackage{verbatim}

%for correcting large brackets spacing

\usepackage{mleftright}\mleftright

\usepackage{algorithm}

\usepackage{algorithmic}

\usepackage{enumitem}

\usepackage{float}

%\usepackage{titling}

%\setlength{\droptitle}{-5mm}  

%\usepackage{MnSymbol}

\newcommand{\cupdot}{\overset{.}{\cup}}

\newcommand{\pvp}{\vec{p}{\kern 0.45mm}'}

\DeclarePairedDelimiter\bra{\langle}{\rvert}

\DeclarePairedDelimiter\ket{\lvert}{\rangle}

\DeclarePairedDelimiterX\braket[2]{\langle}{\rangle}{#1 \delimsize\vert #2}

\newcommand{\underflow}[2]{\underset{\kern-60mm \overbrace{#1} \kern-60mm}{#2}}

\def\Ind(#1){{{\tt Ind}({#1})}}

\def\Id{\mathrm{Id}}

\def\Pr{\mathrm{Pr}}

\def\Tr{\mathrm{Tr}}

\def\im{\mathrm{im}}

\newcommand{\bOt}[1]{\widetilde{\mathcal O}\left(#1\right)}

\newcommand{\QMAo}{\textsf{QMA$_1$}}

\newcommand{\BQP}{\textsf{BQP}}

\newcommand{\NP}{\textsf{NP}}

\newcommand{\SharpP}{\textsf{\# P}}

\newcommand{\diam}[1]{\mathcal{D}\left(#1\right)}

\newcommand{\paths}[1]{\mathcal{P}\left(#1\to\mathbf{1}\right)}

\newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}

\newcommand{\gaps}[1]{#1_{\mathrm{gaps}}}

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

\long\def\ignore#1{}

\newtheorem{theorem}{Theorem}

\newtheorem{corollary}[theorem]{Corollary}%[theorem]

\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{prop}[theorem]{Proposition}

\newtheorem{definition}[theorem]{Definition}

\newtheorem{claim}[theorem]{Claim}

\newtheorem{remark}[theorem]{Remark}

\newenvironment{proof}

{\noindent {\bf Proof. }}

{{\hfill $\Box$}\\	\smallskip}

\usepackage[final]{hyperref}

\hypersetup{

	colorlinks = true,

	allcolors = {blue},

}

\usepackage{ifpdf} 

\ifpdf

	\typeout{^^J *** PDF mode *** } 

%	\input{myBiblatex.tex}

%	\addbibresource{LLL.bib}	

%\else

%	\typeout{^^J *** DVI mode ***} 

%	\hypersetup{breaklinks = true}

%	\usepackage[quadpoints=false]{hypdvips}

	\let\oldthebibliography=\thebibliography

	\let\endoldthebibliography=\endthebibliography

	\renewenvironment{thebibliography}[1]{%

		\begin{oldthebibliography}{#1}%

			\setlength{\itemsep}{-.3ex}%

	}%

	{%

		\end{oldthebibliography}%

	}

\fi 

%opening

\title{Criticality of resampling on the cycle / in the evolution model}

%\author{?\thanks{QuSoft, CWI and University of Amsterdam, the Netherlands. \texttt{?@cwi.nl} }

	%\and

	%?%

%}

%\thanksmarkseries{arabic}

%\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%\date{\vspace{-12mm}}

\begin{document}

	\maketitle

	\begin{abstract}

		The model we consider is the following~\cite{ResampleLimit}: We have a cycle of length $n\geq 3$. Initially we set each site to $0$ or $1$ independently at each site, such that we set it $0$ with probability $p$. After that in each step we select a random vertex with $0$ value and resample it together with its two neighbours assigning $0$ with probability $p$ to each vertex just as initially. The question we try to answer is what is the expected number of resamplings performed before reaching the all $1$ state. 

		We present strong evidence for a remarkable critical behaviour. We conjecture that there exists some $p_c\approx0.62$, such that for all $p\in[0,p_c)$ the expected number of resamplings is bounded by a $p$ dependent constant times $n$, whereas for all $p\in(p_c,1]$ the expected number of resamplings is exponentially growing in $n$.

	\end{abstract}

	%Let $R(n)$ denote this quantity for a length $n\geq 3$ cycle.

	We can think about the resampling procedure as a Markov chain. To describe the corresponding matrix we introduce some notation. For $b\in\{0,1\}^n$ let $r(b,i,(x_{-1},x_0,x_1))$ denote the bit string which differs form $b$ by replacing the bits at index $i-1$,$i$ and $i+1$ with the values in $x$, interpreting the indices $\!\!\!\!\mod n$. Also for $x\in\{0,1\}^k$ let $p(x)=p((x_1,\ldots,x_k))=\prod_{i=1}^{k}p^{(1-x_i)}(1-p)^{x_i}$. Now we can describe the matrix of the Markov chain. We use row vectors for the elements of the probability distribution indexed by bitstrings of length $n$. Let $M_{(n)}$ denote the matrix of the leaking Markov chain:

	$$

		M_{(n)}=\sum_{b\in\{0,1\}^n\setminus{\{1\}^n}}\sum_{i\in[n]:b_i=0}\sum_{x\in\{0,1\}^3}E_{(b,r(b,i,x))}\frac{p(x)}{n-|b|},

	$$

	where $E_{(i,j)}$ denotes the matrix that is all $0$ except $1$ at the $(i,j)$th entry.

	We want to calculate the average number of resamplings $R^{(n)}$, which we define as the expected number of resamplings divided by $n$. For this let $\rho,\mathbbm{1}\in[0,1]^{2^n}$ be indexed with elements of $\{0,1\}^n$ such that $\rho_b=p(b)$ and $\mathbbm{1}_b=1$. Then we use that the expected number of resamplings is just the hitting time of the Markov chain:

	\begin{align*}

		R^{(n)}:&=\mathbb{E}(\#\{\text{resampling before termination}\})/n\\

		&=\sum_{k=1}^{\infty}P(\text{at least } k \text{ resamplings are performed})/n\\

		&=\sum_{k=1}^{\infty}\rho M_{(n)}^k \mathbbm{1}/n\\

		&=\sum_{k=0}^{\infty}a^{(n)}_k p^k

	\end{align*}

	\begin{table}[]

	\centering

	\caption{Table of the coefficients $a^{(n)}_k$}

	\label{tab:coeffs}

	\resizebox{\columnwidth}{!}{%

		\begin{tabular}{c|ccccccccccccccccccccc}

			\backslashbox[10mm]{$n$}{$k$} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\		\hline

			3 &	0 & 1 & \cellcolor{blue!25}2 & 3+1/3 & 5.00 & 7.00 & 9.33 & 12.00 & 15.00 & 18.33 & 22.00 & 26.00 & 30.33 & 35.00 & 40.00 & 45.333 & 51.000 & 57.000 & 63.333 & 70.000 & 77.000 \\

			4 &	0 & 1 & 2 & \cellcolor{blue!25}3+2/3 & 6.16 & 9.66 & 14.3 & 20.33 & 27.83 & 37.00 & 48.00 & 61.00 & 76.16 & 93.66 & 113.6 & 136.33 & 161.83 & 190.33 & 222.00 & 257.00 & 295.50 \\

			5 &	0 & 1 & 2 & 3+2/3 & \cellcolor{blue!25}6.44 & 10.8 & 17.3 & 26.65 & 39.43 & 56.48 & 78.65 & 106.9 & 142.2 & 185.8 & 238.7 & 302.41 & 378.05 & 467.13 & 571.14 & 691.69 & 830.44 \\

			6 &	0 & 1 & 2 & 3+2/3 & 6.44 & \cellcolor{blue!25}11.0 & 18.5 & 30.02 & 47.10 & 71.68 & 106.0 & 152.9 & 215.4 & 297.4 & 403.1 & 537.21 & 705.25 & 913.31 & 1168.2 & 1477.4 & 1849.1 \\

			7 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & \cellcolor{blue!25}18.7 & 31.21 & 50.83 & 80.80 & 125.3 & 189.7 & 280.8 & 407.0 & 578.6 & 808.13 & 1110.2 & 1502.6 & 2005.6 & 2643.2 & 3443.1 \\

			8 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & \cellcolor{blue!25}31.44 & 52.08 & 84.95 & 136.0 & 213.6 & 328.9 & 496.5 & 735.6 & 1070.7 & 1532.5 & 2159.5 & 2998.8 & 4108.1 & 5556.7 \\

			9 &	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & \cellcolor{blue!25}52.30 & 86.27 & 140.7 & 226.3 & 358.4 & 558.4 & 855.4 & 1289.0 & 1911.5 & 2791.4 & 4017.2 & 5701.4 & 7985.9 \\

			10&	0 & 1 & 2 & 3+2/3 & 6.44 & 11.0 & 18.7 & 31.44 & 52.30 & \cellcolor{blue!25}86.49 & 142.1 & 231.6 & 373.4 & 594.8 & 934.4 & 1447.1 & 2209.0 & 3324.6 & 4934.8 & 7226.9 & 10447. \\

        &=

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

        \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\

        &=

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

        &\quad +

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

    \end{align*}

    Dividing by $\mathbb{P}_b(\mathrm{NZ}_{(j_1,j_2)},A_1,A_2)$ and using the first equality gives the desired result.

\end{proof}

\begin{comment}

TEST: Although a proof of claim \ref{claim:expectationsum} was already given, I'm trying to prove it in an alternate way using claim \ref{claim:eventindependence}.

~

Assume that $b_1$ ranges up to site $0$, the gap ranges from sites $1,...,k$ and $b_2$ ranges from site $k+1$ and onwards. For $j=1,...,k$ define the ``partial-zeros'' event $\mathrm{PZ}_j = \mathrm{Z}_1 \cap \mathrm{Z}_2 \cap ... \cap \mathrm{Z}_{j-1} \cap \mathrm{NZ}_j$ i.e. the first $j-1$ sites of the gap become zero and site $j$ does not become zero. Also define the ``all-zeros'' event $\mathrm{AZ} = \mathrm{Z}_1 \cap ... \cap \mathrm{Z}_k$, where all sites of the gap become zero. Note that these events partition the space, so we have for all $b$ that $\sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) = 1 - \mathbb{P}_b(\mathrm{AZ}) = 1 - \mathcal{O}(p^k)$.

~

Furthermore, if site $j$ becomes zero when starting from $b_1$ it means all sites to the left of $j$ become zero as well. Similarly, from $b_2$ it implies all the sites to the right of $j$ become zero.

Because of that, we have

\begin{align*}

    \mathbb{P}_{b_1}(\mathrm{PZ}_j) &= \mathbb{P}_{b_1}(\mathrm{Z}_{j-1} \cap \mathrm{NZ}_j) = \mathcal{O}(p^{j-1}) \\

    \mathbb{P}_{b_2}(\mathrm{NZ}_j) &= 1 - \mathbb{P}_{b_2}(\mathrm{Z}_j) = 1 - \mathcal{O}(p^{k-j+1})

\end{align*}

Following the proof of claim \ref{claim:eventindependence} we also have

\begin{align*}

    \mathbb{P}_b(\mathrm{PZ}_{j})

    &=

    \mathbb{P}_{b_1}(\mathrm{PZ}_{j})

    \; \cdot \;

    \mathbb{P}_{b_2}(\mathrm{NZ}_{j}) \\

    R_{b,\mathrm{PZ}_{j}}

    &=

    R_{b_1,\mathrm{PZ}_{j}}

    \; + \;

    R_{b_2,\mathrm{NZ}_{j}}

\end{align*}

Now observe that

\begin{align*}

    R_b &= \sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) R_{b,\mathrm{PZ}_j} + \mathbb{P}_b(\mathrm{AZ}) R_{b,\mathrm{AZ}} \\

        &= \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{NZ}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        - \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{Z}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &= R_{b_1}

        + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j}

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

        &\overset{???}{=} R_{b_1} + R_{b_2} + \mathcal{O}(p^k)

\end{align*}

\end{comment}

Consider the chain (instead of the cycle) for simplicity with vertices identified by $\mathbb{Z}$.

\begin{definition}[Starting state dependent probability distribution.]

	Let $I\subset\mathbb{Z}$ be a finite set of vertices.

    Let $b_I$ be the initial state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $P_I(A)=P_{b_I}(A)$ where the latter is defined in Definition \ref{def:conditionedevents}, i.e. the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$. 

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

    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^\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$}\\

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

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

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

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

		\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

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

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

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

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