From b0265ec2951b4f4f193685404276946f1850e726 2017-09-07 12:05:29
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-09-07 12:05:29
Subject: [PATCH] Add small proof fixes

---

diff --git a/main.tex b/main.tex
index 23e4e6342b921b79bae49f773187e43289ab488e..c2bb29cc162f53da2c1a65f46e2d5927464c234a 100644
--- a/main.tex
+++ b/main.tex
@@ -706,13 +706,27 @@ The intuition of the following lemma is that the far right can only affect the z
 		$R^{(n)}-R^{(m)}=\mathcal{O}(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
+        \begin{align*}
+            P\in\mathcal{P} \equiv \NZ{a-1} \cap \Z{a} \cap \Z{a+1} \cap \cdots \cap \Z{b-1} \cap \Z{b} \cap \NZ{b+1} .
+        \end{align*}
+        Note that we have the following partition of the event $\Z{v}$ for any vertex $v\in[n]$:
+        \begin{align*}
+            \Z{v} = \dot\bigcup_{P : v\in P} (P\in\mathcal{P})
+        \end{align*}
 		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}\\   		
+            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}}\\