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

Changeset - 9b0f04598ca9

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Andras Gilyen - 8 years ago 2017-09-07 16:40:09
gilyen@clayoquot.swat.cwi.nl

nicer proof

1 file changed with 11 insertions and 11 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

         \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)}
 			&= \E^{(n)}(\Res{1}) \tag{by translation invariance}\\
 			&= \sum_{k=1}^{\infty}\P^{(n)}(\Res{1}\geq 1) \\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{(n)}(\Res{1}\geq 1\& 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}) +\bigO{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+\bigO{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+\bigO{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+\bigO{p^{n}} \tag{by Corollary~\ref{cor:probIndepNew}}\\
 			&= \sum_{s=1}^{n-1}\E^{[-N,N]}(\# \text{ resamples in }[s]|[s]\in \mathcal{P})+\bigO{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})+\bigO{p^{n}}.
 			%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r-1}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq 1\,\&\, [\ell+1,r-1]\in\mathcal{P}) \tag{partition}\\
 			%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq 1\,\&\, [\ell+1,r-1]\in\mathcal{P})  +\bigO{p^{n}} \\
 			%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r}{\ell,r\in[n]}}\P^{[l,r]}_{b_{\ell}=b_{r}=1}(\Res{1}\geq 1\,\&\, [\ell+1,r-1]\in\mathcal{P}) \P^{[r,\ell]}(\NZ{\ell,r}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{(n)}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) \tag{partition}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{(n)}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) +\bigO{p^{n}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) \P^{[\overline{P}]}(\NZ{\partial P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) \left(\left(\P^{[|\overline{P}|]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:independenetSidesNew}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[P\cup \partial P]}_{b_{\partial P}=1}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) \left(\left(\P^{[N]}(\NZ{1})\right)^2+\bigO{p^{|\overline{P}|}}\right) +\bigO{p^{n}} \tag{by Corollary~\ref{cor:probIndepNew}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{[-N,N]}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}\P^{[-N,N]}(\Res{1}\geq 1\,\&\, P\in\mathcal{P}) +\bigO{p^{n}} \tag{by Lemma~\ref{lemma:eventindependenceNew}}\\
 			&= \E^{[-N,N]}(\Res{1})+\bigO{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.
     Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$. These definitions are illustraded in Figure \ref{fig:lemmaillustration}.
 	Then $\P^\infty_{I}(\Z{0})-\P^\infty_{I'}(\Z{0}) = O(p^{I_{\max}-|I'|})$.

0 comments (0 inline, 0 general)