Changeset - 5236ff40cd19
[Not reviewed]
0 1 0
András Gilyén - 8 years ago 2017-05-31 11:48:01
gilyenandras@gmail.com
Update on Overleaf.
1 file changed with 105 insertions and 0 deletions:
main.tex
105
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -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]
0 comments (0 inline, 0 general)