Changeset - b0265ec2951b
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-09-07 12:05:29
tom.bannink@cwi.nl
Add small proof fixes
1 file changed with 19 insertions and 5 deletions:
main.tex
19
5
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -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}}\\   			
0 comments (0 inline, 0 general)