From 5236ff40cd190efe1420252cd8d9a91d89a4db3e 2017-05-31 11:48:01
From: András Gilyén <gilyenandras@gmail.com>
Date: 2017-05-31 11:48:01
Subject: [PATCH] Update on Overleaf.
---

diff --git a/main.tex b/main.tex
index d3fb97508419c25186a0804b3ecbae40578a4e79..e4caa661cd51a3a26645d725c6409ea89455f997 100644
--- a/main.tex
+++ b/main.tex
@@ -507,6 +507,111 @@ Now observe that
 \end{align*}
 
 \newpage
+    \subsection{Attempt to prove the linear bound \ref{it:const}}
+    
+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$. For an event $A$ representing a subset of all possible resample sequences let $P_I(A)$ denote the probability of seeing a resample sequence from $A$ when the whole procedure started in state $b_I$. 
+\end{definition}
+\begin{definition}[Vertex visiting resamplings]\label{def:visitingResamplings}
+	Let $V^{(i)}$ be the event corresponding to ``Vertex $i$ gets resampled to $0$ before termination''.
+\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)$.
+	Then $P_{I}(V^{(0)})=P_{I'}(V^{(0)}) + O(p^{I_{\max}+1-|I|})$.
+\end{lemma}
+\begin{proof}
+	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples the $0$ vertex must produce at least $I_{\max}$ number of $0$-s during the resamplings.
+	
+	Induction step: For an event $A$ and $k>0$ let us denote by $A_k=A\cap$``Each vertex in $0,1,2,\ldots, k-1$ gets $0$ before termination (either by resampling or initialisation), but not $k$''. Observe that $V^{(0)}=\dot{\bigcup}_{k=1}^{\infty}V^{(0)}_k$.
+	Let $I_{<k}:=I\cap[k-1]$ and similarly $I_{>k}:=I\setminus[k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$. Suppose we proved the claim up to $|I|-1$, then the induction step can be shown by
+	\begin{align*}
+		P_{I}(V^{(0)})
+		&=\sum_{k=1}^{\infty}P(V^{(0)}_k)
+		=\sum_{k\in \mathbb{N}\setminus I}P(V^{(0)}_k)\\
+		&=\sum_{k\in\mathbb{N}\setminus I}P_{I_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}}) \tag{by Claim~\ref{claim:eventindependence}}\\
+		&=\sum_{k\in I_{><}}P_{I_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}+1-|I|})
+		\tag{$k<I_{\min}\Rightarrow P_{I_{<k}}(V^{(0)}_k)=0$}\\
+		&=\sum_{k\in I_{><}}P_{I'_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}+1-|I|})	
+		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\
+		&=\sum_{k\in I_{><}}P_{I'_{<k}}(V^{(0)}_k)\cdot
+		\left(P_{I'_{>k}}(\overline{V^{(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}}(V^{(0)}_k)\cdot
+		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})	
+		\tag{as $P_{I'_{<k}}(V^{(0)}_k)=\mathcal{O}(p^{k-|I'_{<k}|})$}\\
+		&=\sum_{k\in\mathbb{N}\setminus I}P_{I'_{<k}}(V^{(0)}_k)\cdot
+		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\
+		&=\sum_{k\in\mathbb{N}\setminus I'}P_{I'_{<k}}(V^{(0)}_k)\cdot
+		P_{I'_{>k}}(\overline{V^{(k)}}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow P_{I'_{<k}}(V^{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\
+		&=P_{I'}(V^{(0)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{analogously to the beginning}			
+	\end{align*}
+\end{proof}
+
+	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 circle.
+
+\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} 
+
+\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|}}\sum_{\mathcal{P}\text{ patches}} \rho_{S(f)} R^{(\mathcal{P})}_{S(f)}\mathbb{P}_{S(f)}(A^{(\mathcal{P})})\\
+    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}
+    \sum_{\mathcal{P}\text{ patches}}\sum_{P\in\mathcal{P}} \rho_{S(f)} R^{(P,\mathcal{P})}_{S(f)}\mathbb{P}_{S(f)}(A^{\mathcal{P}})\\
+    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}
+    \sum_{\mathcal{P}\text{ patches}}\sum_{P\in\mathcal{P}} \rho_{S(f)} R^{(P)}_{S(f)\cap P}\mathbb{P}_{S(f)}(A^{\mathcal{P}}) \tag{by Claim~\ref{claim:eventindependence}}\\ 
+    &= \frac{1}{n}\sum_{S\subseteq [n]}\sum_{f\in\{0,1'\}^{|S|}}
+    \sum_{P\text{ patch}} \rho_{S(f)} 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{V^{(P_{\min}-1)}}\cap\overline{V^{(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{V^{(P_{\min}-1)}}\cap\overline{V^{(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_{><}|}) \\             
+	&= \frac{1}{n}\sum_{S\subseteq [n]}\mathcal{O}(p^{|S|+|S_{><}|}).
+    \end{align*}
+   	
+   	The penultimate inequality can be seen by case separation.
+   	If $S_{><}\subseteq P$ then already $\mathbb{P}_{S(f_P)}(A^{(P)})=\mathcal{O}(p^{|S_{><}|})$.
+   	Otherwise if all elements of $S_{><}\setminus P$ are larger than $P_{\max}$ then we view the last summation as $\sum_{f'_{\overline{P}}\in\{0,1'\}^{|S\cap \overline{P}\setminus\{S_{\max}\}|}}\sum_{f''_{\overline{P}}\in\{0,1'\}^{1}}$ and use Lemma~\ref{lemma:probIndep} to conclude the cancellations pairwise regarding the filling of $S_{\max}$, i.e., the value of $f''_{\overline{P}}$. We proceed similarly when 
+   	all elements of $S_{><}\setminus P$ are smaller than $P_{\min}$. In the last case we again proceed similarly, but now the cancellations will come from the interplay of $4$ fillings, corresponding to the possible filling of $S_{\min}$ and $S_{\max}$ simultaneously.
+   	   
+	I think the same arguments would directly translate to the torus and other translationally invariant objects, so we could go higher dimensional as Mario suggested. Then 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.
+    
+    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{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]