From 241841a8e5cd33f7464a7eac30c77ad8e292291e 2017-09-06 21:13:54 From: Andras Gilyen Date: 2017-09-06 21:13:54 Subject: [PATCH] n=2k stabilization --- diff --git a/main.tex b/main.tex index 90cd09fe22be9c748fb4eeaf9dfa30c7beed2255..762170751a94fc4d4547cb041229115498c0a114 100644 --- a/main.tex +++ b/main.tex @@ -190,7 +190,7 @@ 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*} @@ -614,7 +614,7 @@ The intuition of the following lemma is that the far right can only affect the z \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} @@ -625,35 +625,185 @@ The intuition of the following lemma is that the far right can only affect the z \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\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}}(\mathrm{NZ}^{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\ - &=\sum_{k\in I_{><}}P_{I_{k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|}) - \tag{$k<}}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}}(\mathrm{NZ}^{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\ + &=\sum_{k\in I_{><}}\P^\infty_{I_{k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|}) + \tag{$k<}}\P^\infty_{I'_{k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|}) \tag{$k< I_{\max}\Rightarrow I_{<}}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_{<}}P_{I'_{k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|}) - \tag{as $P_{I'_{k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\ - &=\sum_{k\in\mathbb{N}\setminus I'}P_{I'_{k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|}) \tag{$k=I_{\max}\Rightarrow P_{I'_{<}}\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_{<}}\P^\infty_{I'_{k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|}) + \tag{as $\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}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|}) \tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{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} @@ -781,24 +931,6 @@ Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the in 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)\\ @@ -814,10 +946,10 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is &= \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} \\ @@ -831,31 +963,31 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is \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*} @@ -873,76 +1005,6 @@ Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is = \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 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 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