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

Changeset - 62d60a9017a9

Parent rev.

Child rev.

[Not reviewed]

Merge

0 1 0

Tom Bannink - 8 years ago 2017-09-07 17:14:59
tom.bannink@cwi.nl

Merge branch 'master' of https://git.overleaf.com/9473097rgxjnfdkjdhb

1 file changed with 16 insertions and 12 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

 	$\P^{[n]}(\Z{1})-\P^{[m]}(\Z{1}) = \bigO{p^{\min(n,m)}}$. (Should be true with $\bigO{p^{\min(n,m)+1}}$ too.)
 \end{corollary}
 	The intuition of the following lemma is simmilar to the previous. The events on the two sides should be independent unless an interaction chain is forming, implying that every vertex gets resampled to $0$ at least once.
  	\begin{lemma}\label{lemma:independenetSidesNew}
  		$$\P^{[k]}(\Z{1}\cap \Z{k})=\P^{[k]}(\Z{1})\P^{[k]}(\Z{k})+\bigO{p^{k}}=\left(\P^{[k]}(\Z{1})\right)^2+\bigO{p^{k}}.$$
  	\end{lemma}
  		+\bigO{p^{k}}.
  		\end{align*}
  	\end{proof}
 	Again the intuition of the final theorem is simmilar to the previous lemmas. A site can only realise the length of the cycle after an interaction chain was formed around the cycle, implying that every vertex was resampled to $0$ at least once.
 	\begin{theorem}
 		$R^{(n)}-R^{(m)}=\bigO{p^{\min(n,m)}}$.
 		\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}\P^{(n)}(\Res{1}\geq k) \\
 			%&= \sum_{k=1}^{\infty}\sum_{\underset{\ell\geq r-1}{\ell,r\in[n]}}\P^{(n)}(\Res{1}\geq k\,\&\, [\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 k\,\&\, [\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 k\,\&\, [\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 k\,\&\, P\in\mathcal{P}) \tag{partition}\\
 			&= \sum_{k=1}^{\infty}\sum_{P\text{ patch}:1\in P}^{|P|<n}\P^{(n)}(\Res{1}\geq k\,\&\, 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 k\,\&\, 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 k\,\&\, 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 k\,\&\, 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 k\,\&\, 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 k\,\&\, 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.

0 comments (0 inline, 0 general)