AENC/resampling_chain Changeset - 3f50b7d8a179 · Centrum Wiskunde & Informatica (CWI)

@@ -49,6 +49,8 @@

\def\Tr{\mathrm{Tr}}

\def\im{\mathrm{im}}

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

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

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

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

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

@@ -370,7 +372,7 @@ Here we prove claim \ref{claim:weakcancel}, the weaker version of the claim. We

    Equivalently, on the infinite line $\xi_1$ and $\xi_2$ are independent if there is a site `inbetween' them that was never zero in $\xi_1$ and never zero in $\xi_2$. On the cycle $\xi_1$ and $\xi_2$ are independent if there are \emph{two} sites inbetween them that are never zero.

\end{definition}

\begin{claim}[Sum of expectation values] \label{claim:expectationsum}

When $b=b_1\land b_2\in\{0,1\}^n$ is a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes with $k$ $1$s inbetween the groups, then we have $R_b(p) = R_{b_1}(p) + R_{b_2}(p) + \mathcal{O}(p^{k})$ where $b_1$ and $b_2$ are the configurations where only one of the groups is present and the other group has been replaced by $1$s. To be precise, the sums agree up to and including order $p^{k-1}$.

When $b=b_1\land b_2\in\{0,1\}^n$ is a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes with $k$ $1$s inbetween the groups, then we have $R_b(p) = R_{b_1}(p) + R_{b_2}(p) + \bigO{p^{k}}$ where $b_1$ and $b_2$ are the configurations where only one of the groups is present and the other group has been replaced by $1$s. To be precise, the sums agree up to and including order $p^{k-1}$.

\end{claim}

\textbf{Example}: For $b_1 = 0111111$ and $b_2 = 1111010$ we have $b=0111010$ and $k=3$. The claim says that the expected time to reach $\mathbf{1}$ from $b$ is the time to make the first group $1$ plus the time to make the second group $1$, as if they are independent. Simulation shows that

\begin{align*}

@@ -614,51 +616,54 @@ Consider the chain (instead of the cycle) for simplicity with vertices identifie

New:

\begin{lemma}[Conditional independence] \label{lemma:eventindependenceNew}

	Let $i\neq j\in [n]$, and let $A_1$ be any event that depends only on the sites $[i,j]$ (meaning the initialization and resamples) and similarly $A_2$ an event that depends only on the sites $[j,i]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have

	Let $i,j \in [n]$, and let $A$ be any event that depends only on the sites $[i,j]$ (meaning the initialization and resamples) and similarly $B$ an event that depends only on the sites $[j,i]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have

	\begin{align*}

	\P^{(n)}(\mathrm{NZ}^{(i,j)}\cap A_1\cap A_2)

&=

	\P^{[i,j]}(\mathrm{NZ}^{(i,j)}\cap A_1)

	\; \cdot \;

	\P^{[j,i]}(\mathrm{NZ}^{(i,j)}\cap A_2)/(1-p)^2 \\

	\P^{(n)}(A_1\cap A_2|\mathrm{NZ}^{(i,j)})

&=

	\P^{[i,j]}(A_1|\mathrm{NZ}^{(i,j)})

	\; \cdot \;

	\P^{[j,i]}(A_2|\mathrm{NZ}^{(i,j)})

		\P^{(n)}(\mathrm{NZ}^{(i,j)}\cap A\cap B)

		\P_{b_i=b_j=1}^{[i,j]}(\mathrm{NZ}^{(i,j)}\cap A)

		\; \cdot \;

		\P^{[j,i]}(\mathrm{NZ}^{(i,j)}\cap B),

	\end{align*}

	and similarly

	\begin{align*}

		\P^{[n]}(\mathrm{NZ}^{(i)}\cap A\cap B)

		\P_{b_i=1}^{[i]}(\mathrm{NZ}^{(i)}\cap A)

		\; \cdot \;

		\P^{[i,n]}(\mathrm{NZ}^{(i)}\cap B)

	\end{align*}

	up to any order in $p$.

\end{lemma}

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:probIndepNew}

	$\forall n\in \mathbb{N}_+:\P^{[n]}(\Z{1})-\P^{[n+1]}(\Z{1}) = O(p^{n})$. (Should be true with $O(p^{n+1})$ as well.)

	$\forall n\in \mathbb{N}_+:\P^{[n]}(\Z{1})-\P^{[n+1]}(\Z{1}) = \bigO{p^{n}}$. (Should be true with $\bigO{p^{n+1}}$ as well.)

\end{lemma}

\begin{proof}

	The proof uses induction on $n$. For $n=1$ the statement is easy, since $\P^{[1]}(\Z{1})=p$ and $\P^{[2]}(\Z{1})=p+p^2+O(p^{3})$.

	The proof uses induction on $n$. For $n=1$ the statement is easy, since $\P^{[1]}(\Z{1})=p$ and $\P^{[2]}(\Z{1})=p+p^2+\bigO{p^{3}}$.

	Induction step: suppose we proved the claim for $n-1$, then

	\begin{align*}

	\P^{[n+1]}(\Z{1})

	&=\sum_{k=1}^{n+1}\P^{[n]}([k]\in\mathcal{P}) \tag{the events are a partition}\\

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P}) + O(p^{n})\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k+1]}(\NZ{1})/(1-p)+ O(p^{n}) \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \left(\P^{[n-k]}(\NZ{1})+O(p^{n-k})\right)/(1-p)+ O(p^{n}) \tag{by induction} \\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})/(1-p)+ O(p^{n}) \\

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P})+ O(p^{n}) \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ O(p^{n}) \\

	&=\P^{[n]}(\Z{1})	+ O(p^{n})

	&=\sum_{k=1}^{n+1}\P^{[n+1]}([k]\in\mathcal{P}) \tag{the events are a partition}\\

	&=\sum_{k=1}^{n-1}\P^{[n+1]}([k]\in\mathcal{P}) + \bigO{p^{n}}\tag*{$\left(\P^{[n+1]}([k]\in\mathcal{P})=O(p^{k})\right)$}\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k+1]}(\NZ{1})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \left(\P^{[n-k]}(\NZ{1})+\bigO{p^{n-k}}\right)+ \bigO{p^{n}} \tag{by induction} \\

	&=\sum_{k=1}^{n-1}\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})\cdot \P^{[n-k]}(\NZ{1})+ \bigO{p^{n}} \tag*{$\left(\P^{[k+1]}_{b_{k+1}=1}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\

	&=\sum_{k=1}^{n-1}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag{by Claim~\ref{lemma:eventindependenceNew}}\\

	&=\sum_{k=1}^{n}\P^{[n]}([k]\in\mathcal{P})+ \bigO{p^{n}} \tag*{$\left(\P^{[n]}([n]\in\mathcal{P})=\bigO{p^{n}}\right)$}\\

	&=\P^{[n]}(\Z{1})	+ \bigO{p^{n}}

	\end{align*}

\end{proof}

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

	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = O(p^{\min(n,m)})$. (Should be true with $O(p^{\min(n,m)+1})$ too.)

	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = \bigO{p^{\min(n,m)}}$. (Should be true with $\bigO{p^{\min(n,m)+1}}$ too.)

\end{corollary}

 	\begin{lemma}\label{lemma:independenetSidesNew}

 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\mathcal{O}(p^{k})=\left(\P^{[k]}(\Z{1})\right)^2+\mathcal{O}(p^{k}).$$

 		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\bigO{p^{k}}=\left(\P^{[k]}(\Z{1})\right)^2+\bigO{p^{k}}.$$

 	\end{lemma}

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

 	$$\P^{[k]}(\NZ{1}\cap \NZ{k})=\P^{[k]}(\NZ{1})\P^{[k]}(\NZ{k})+\mathcal{O}(p^{k}).$$

 	$$\P^{[k]}(\NZ{1}\cap \NZ{k})=\P^{[k]}(\NZ{1})\P^{[k]}(\NZ{k})+\bigO{p^{k}}.$$

 	\begin{proof}

 		We proceed by induction on $k$. For $k=1,2$ the statement is trivial.

@@ -669,41 +674,41 @@ The intuition of the following lemma is that the far right can only affect the z

 		Suppose we proved the statement up to $k-1$, then we proceed using induction similarly to the above

 		\begin{align*}

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

 		&=\sum_{\ell, r\in [k]: \ell<r-1}\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\P^{[k]}([k]\in\mathcal{P})\\

 		&=\sum_{\ell, r\in [k]: \ell<r-1}\P^{[k]}([\ell],[r,k]\in\mathcal{P})

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

 		&\overset{Lemma~\ref{lemma:eventindependenceNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

 		\P^{[\ell+1]}([\ell]\in\mathcal{P})

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!\P^{[k]}([\ell],[r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([k]\in\mathcal{P})=\bigO{p^{k}}\right)$}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\P^{[\ell+1,r-1]}(\NZ{\ell+1}\cap \NZ{r-1})

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})/(1-p)^2

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

 		&\overset{\text{induction}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

 		\P^{[\ell+1]}([\ell]\in\mathcal{P})

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,r-1]}(\NZ{\ell+1})

		\P^{[\ell+1,r-1]}(\NZ{r-1})\right)

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})/(1-p)^2

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

 		&\overset{Corrolary~\ref{cor:probIndepNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

 		\P^{[\ell+1]}([\ell]\in\mathcal{P})

 		\P^{[r-1,k]}_{b_{r-1}=1}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by induction}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[\ell+1]}_{b_{\ell+1}=1}([\ell]\in\mathcal{P})

 		\left(\P^{[\ell+1,k]}(\NZ{\ell+1})

 		\P^{[1,r-1]}(\NZ{r-1})\right)

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})/(1-p)^2

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

 		&\overset{Lemma~\ref{lemma:eventindependenceNew}}{=}\sum_{\ell, r\in [k]: \ell<r-1}

 		\P^{[1,r-1]}_{b_{r-1}=1}(\NZ{r-1})\right)

 		\P^{[r-1,k]}([r,k]\in\mathcal{P})

 		+\bigO{p^{k}} \tag{by Corrolary~\ref{cor:probIndepNew}}\\

 		&=\!\!\!\sum_{\ell, r\in [k]: \ell<r-1}\!\!\!

 		\P^{[k]}([\ell]\in\mathcal{P})

 		\P^{[k]}([r,k]\in\mathcal{P})

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

 		+\bigO{p^{k}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

 		&=\left(\sum_{\ell\in [k]}\P^{[k]}([\ell]\in\mathcal{P})\right)

 		\left(\sum_{r\in [k]}\P^{[k]}([r,k]\in\mathcal{P})\right)

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

 		+\bigO{p^{k}} \tag*{$\left(\P^{[k]}([\ell]\in\mathcal{P})=\bigO{p^{\ell}}\right)$}\\

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

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

 		+\bigO{p^{k}}.

 		\end{align*}

 	\end{proof}

	\begin{theorem}

		$R^{(n)}-R^{(m)}=\mathcal{O}(p^{\min(n,m)})$.

		$R^{(n)}-R^{(m)}=\bigO{p^{\min(n,m)}}$.

	\end{theorem}

	\begin{proof}

        Some notation: let $P$ be an interval $[a,b]$. We say $P$ is a \emph{patch} when the $\Z{i}$ event holds for all $i \in [a,b]$ and $\NZ{a-1}$ and $\NZ{b+1}$ holds. We denote this event by $P\in\mathcal{P}$, so

@@ -716,23 +721,22 @@ The intuition of the following lemma is that the far right can only affect the z

        \end{align*}

		Let $N\geq \max(2n,2m)$, then

		\begin{align*}

            R^{(n)}

            &= \frac{1}{n}\sum_{v\in[n]}\E^{(n)}(\text{\# resamples of } v)

            \tag{by definition}\\

		    &= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}t\cdot \P^{(n)}(v \text{ is resampled }t\text{ times}) \\

            &= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}t\cdot\P^{(n)}(v \text{ is resampled }t\text{ times and }v\in P\text{ and } P\in\mathcal{P})

            \tag{partition}\\

            &= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}t\cdot\P^{(n)}(v \text{ is resampled }t\text{ times and }v\in P | P\in\mathcal{P}) \; \P^{(n)}(P\in\mathcal{P})\\

		    &= \frac{1}{n}\sum_{P\text{ patch}}\E^{(n)}(\# \text{ resamples in }P|P\in \mathcal{P}) \; \P^{(n)}(P\in\mathcal{P})\\

            &= \sum_{s=1}^{n-1}\E^{(n)}(\# \text{ resamples in }[s] \;|\; [s]\in \mathcal{P}) \; \P([s]\in\mathcal{P}) +\mathcal{O}(p^{n})

            \tag{by translation symmetry}\\

            &= ???? \\

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\P^{[s+1,n]}(\NZ{s+1}\cap\NZ{n})/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,n]}(\NZ{s+1})\right)^2/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\

		&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,N]}(\NZ{s+1})\right)^2/(1+p)^2+\mathcal{O}(p^{n}) \tag{by Corollary~\ref{cor:probIndepNew}}\\

		&= \sum_{s=1}^{n-1}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:eventindependenceNew}, Corollary~\ref{cor:probIndepNew}}\\

		&= \sum_{s=1}^{N}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}).

		\end{align*}

			R^{(n)}

			&= \E^{(n)}(\Res{1}) \tag{by translation invariance}\\

			&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{1}\geq 1) \\

			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{(n)}(\Res{1}\geq 1\& P\in\mathcal{P}) \tag{partition}\\

			&= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}\sum_{P\text{ patch}}t\cdot\P^{(n)}(v \text{ is resampled }t\text{ times and }v\in P | P\in\mathcal{P}) \; \P^{(n)}(P\in\mathcal{P})\\

			&= \frac{1}{n}\sum_{P\text{ patch}}\E^{(n)}(\# \text{ resamples in }P|P\in \mathcal{P}) \; \P^{(n)}(P\in\mathcal{P})\\

			&= \sum_{s=1}^{n-1}\E^{(n)}(\# \text{ resamples in }[s] \;|\; [s]\in \mathcal{P}) \; \P([s]\in\mathcal{P}) +\bigO{p^{n}}

			\tag{by translation symmetry}\\

			&= ???? \\

			&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\P^{[s+1,n]}(\NZ{s+1}\cap\NZ{n})/(1+p)^2+\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\

			&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,n]}(\NZ{s+1})\right)^2/(1+p)^2+\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\

			&= \sum_{s=1}^{n-1}\E^{[0,s+1]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})\left(\P^{[s+1,N]}(\NZ{s+1})\right)^2/(1+p)^2+\bigO{p^{n}} \tag{by Corollary~\ref{cor:probIndepNew}}\\

			&= \sum_{s=1}^{n-1}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}, Corollary~\ref{cor:probIndepNew}}\\

			&= \sum_{s=1}^{N}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\bigO{p^{n}}.

		\end{align*}

		Repeating the same calculation with $m$, and comparing the two expressions completes the proof.

	\end{proof}

@@ -861,11 +865,11 @@ The intuition of the following lemma is that the far right can only affect the z

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

		=\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})+\bigO{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\in\{0,1'\}^{|S|}}\rho_{S(f)} \P^\infty_{S(f)}(\NZ{1})\P^\infty_{S(f)}(\NZ{k})+\bigO{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*}

@@ -890,7 +894,7 @@ The intuition of the following lemma is that the far right can only affect the z

	\begin{theorem}

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

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

	\end{theorem}

	\begin{proof}

		\begin{align*}

@@ -901,15 +905,15 @@ The intuition of the following lemma is that the far right can only affect the z

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

		\rho_{S(f)}  R^{(P)}_{S(f)}\mathbb{P}_{S(f)}(A^{(P)}) + \bigO{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}}\\

		\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})+ \bigO{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_{S'\subseteq \overline{P}}\sum_{f'\in\{0,1'\}^{|S'|}}\P_{S'(f')}(\NZ{P_{\min}-1}\cap\NZ{P_{\max}+1})+ \bigO{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})$.}

		+\bigO{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}