AENC/resampling_chain Changeset - b0265ec2951b · Centrum Wiskunde & Informatica (CWI)

Changeset - b0265ec2951b

Parent rev.

Child rev.

[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

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

  		&=\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}
         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}}\\
 		&= \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}, Corollary~\ref{cor:probIndepNew}}\\
 		&= \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.

0 comments (0 inline, 0 general)