Changeset - 5e80cf059be7
[Not reviewed]
0 1 0
András Gilyén - 8 years ago 2017-09-07 01:31:24
gilyen@cwi.nl
simplified proof
1 file changed with 126 insertions and 8 deletions:
main.tex
126
8
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -60,6 +60,7 @@
 
\newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}
 
\newcommand{\gaps}[1]{#1_{\mathrm{gaps}}}
 
\renewcommand{\P}{\mathbb{P}}
 
\newcommand{\E}{\mathbb{E}}
 
\newcommand{\NZ}[1]{\mathrm{NZ}^{(#1)}}
 
\newcommand{\Z}[1]{\mathrm{Z}^{(#1)}}
 
%\newcommand{\dist}[1]{d_{\!\!\not\,#1}}
 
@@ -610,6 +611,123 @@ Consider the chain (instead of the cycle) for simplicity with vertices identifie
 
    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}
 

	
 
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]$ and similarly $A_2$ an event that depends only on the sites $[j,i]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled $k$ times before termination'' for an $s$ on the correct side). 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)})
 
	\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}
 
	$\P^{[n]}(\Z{1})-\P^{[n-1]}(\Z{1}) = O(p^{n})$.
 
\end{lemma}
 
\begin{proof}
 
	\begin{figure}
 
		\begin{center}
 
			\includegraphics{diagram_proborders.pdf}
 
		\end{center}
 
		\caption{\label{fig:lemmaillustrationNew} Illustration of setup of Lemma \ref{lemma:probIndep}.}
 
	\end{figure}
 
	The proof uses induction on $n$. For $n=1$ the statement is easy, since $\P^{\emptyset}(\Z{1})=0$ and $\P^{[1]}(\Z{1})=p$.
 
	
 
	Induction step: suppose we proved the claim for $n-1$
 
	\begin{align*}
 
	\P^{[n]}(\Z{1})
 
	&=\sum_{k=1}^{n}\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]}(\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-1]}(\NZ{1})+O(p^{n-k})\right)/(1-p)+ O(p^{n}) \tag{by induction} \\	
 
	&\overset{?}{=}\sum_{k=1}^{n-1}\P^{[k+1]}([k]\in\mathcal{P})\cdot \P^{[n-k-1]}(\NZ{1})/(1-p)+ O(p^{n}) \\	
 
	&\overset{?}{=}\sum_{k=1}^{n-1}\P^{[n-1]}([k]\in\mathcal{P})+ O(p^{n}) \tag{by Claim~\ref{lemma:eventindependenceNew}}\\
 
	&=\P^{[n-1]}(\Z{1})	+ O(p^{n}) 
 
	\end{align*}
 
\end{proof}
 
\begin{corollary}\label{cor:probIndepNew}
 
	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = O(p^{\min(n,m)+1})$.
 
\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}).$$
 
 	\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}).$$
 
 	\begin{proof}
 
 		We proceed by induction on $k$. For $k=1,2$ the statement is trivial.
 
 		
 
 		Now observe that:
 
 		$$\P^{[k]}(\Z{1})=\sum_{P\text{ patch}\,:\,1\in P}\P^{[k]}(P\in\mathcal{P})$$
 
 		$$\P^{[k]}(\Z{k})=\sum_{P\text{ patch}\,:\,k\in P}\P^{[k]}(P\in\mathcal{P})$$
 
 		
 
 		Suppose we proved the statement for all $\ell\leq k$, 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^{[k]}(\Z{1}\cap \Z{k})=\\
 
 		&=\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})
 
 		\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})
 
 		\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})
 
 		\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^{[k]}([\ell]\in\mathcal{P})
 
 		\P^{[k]}([r,k]\in\mathcal{P})
 
 		+\mathcal{O}(p^{k})\\
 
 		&=\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})\\
 
 		&=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})
 
 		+\mathcal{O}(p^{k}).	
 
 		\end{align*}
 
 	\end{proof}
 
 	
 
	\begin{theorem}
 
		$R^{(n)}-R^{(m)}=\mathcal{O}(p^{\min(n,m)})$.
 
	\end{theorem}
 
	\begin{proof}
 
		Let $N\geq \max(2n,2m)$, then
 
		\begin{align*}
 
		R^{(n)} &=  \\
 
		&= \frac{1}{n}\sum_{v\in[n]}\sum_{t=1}^{\infty}t\cdot \P^{(n)}(v \text{ is resampled in }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 in }t\text{ times and }P\text{ is a patch})\\	
 
		&= \frac{1}{n}\sum_{P\text{ patch}}\E^{(n)}(\# \text{ resamples in }P|P\in \mathcal{P})\\			
 
		&= \sum_{s=1}^{n-1}\E^{(n)}(\# \text{ resamples in }[s]|[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^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}) \tag{by Lemma~\ref{lemma:eventindependenceNew},~\ref{lemma:independenetSidesNew}}\\   	
 
		&= \sum_{s=1}^{N}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\mathcal{O}(p^{n}).
 
		\end{align*}
 
		Repeating the same calculation with $m$, and comparing the two expressions completes the proof.
 
	\end{proof} 	
 

	
 
Old:
 

	
 
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.
 
@@ -625,26 +743,26 @@ 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 \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\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$}\\
 
        &=\sum_{k\in\mathbb{N}\setminus I}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\mathrm{NZ}^{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\
 
        &=\sum_{k\in I_{><}}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \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}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)}) \tag{by Claim~\ref{claim:eventindependence}}\\
 
        &=\sum_{k\in I_{><}}\P^\infty_{I_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})
 
		\tag{$k<I_{\min}\Rightarrow \P^\infty_{I_{<k}}(\Z{(0)}_k)=0$}\\
 
        &=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\mathrm{NZ}^{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})	
 
        &=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot \P^\infty_{I_{>k}}(\NZ{(k)})+\mathcal{O}(p^{I_{\max}+1-|I|})	
 
		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\
 
		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot
 
        \left(\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_{<k}|<|I|$}\\
 
        \left(\P^\infty_{I'_{>k}}(\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_{<k}|<|I|$}\\
 
		&=\sum_{k\in I_{><}}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	
 
        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	
 
		\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
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\
 
        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})\\
 
		&=\sum_{k\in\mathbb{N}\setminus I'}\P^\infty_{I'_{<k}}(\Z{(0)}_k)\cdot
 
        \P^\infty_{I'_{>k}}(\mathrm{NZ}^{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\
 
        \P^\infty_{I'_{>k}}(\NZ{(k)}) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{$k=I_{\max}\Rightarrow \P^\infty_{I'_{<k}}(\Z{(0)}_k)=\mathcal{O}(p^{I_{\max}-|I'|})=\mathcal{O}(p^{I_{\max}+1-|I|})$}\\
 
		&=\P^\infty_{I'}(\Z{(0)}) +\mathcal{O}(p^{I_{\max}-|I'|})	\tag{analogously to the beginning}			
 
	\end{align*}
 
\end{proof}
0 comments (0 inline, 0 general)