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

Changeset - be633a788363

Parent rev.

Child rev.

[Not reviewed]

0 1 0

András Gilyén - 8 years ago 2017-09-14 00:25:36
gilyen@cwi.nl

General distance-degree lemma

1 file changed with 2 insertions and 2 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

 The intuition of the following lemma is that if two sites have distance $d$ in the graph, then the only way they can affect each other is that an interaction chain is forming between them, meaning that every vertex should get resampled to $0$ at least once in between them.
 \begin{lemma}\label{lemma:distancePower}
 	Suppose $G=(V,E)$ is a graph, $X,Y\subseteq V$ and $A^X$ is a local event on $X$. Then
 	$$\P^{G}(A^X)-\P^{G\setminus Y}(A^X)=\bigO{p^{d(X,Y)}}.$$
 	(Should be true with $+1$ in the degree!)
+	(Should be true with $+1$ in the degree, when $d(X,Y)>0$!)
 \end{lemma}
 \begin{proof}
 	We can assume without loss of generality, that $X\neq \emptyset\neq Y$, otherwise the statement is trivial.
+	We can assume without loss of generality, that $X\neq \emptyset\neq Y$, otherwise the statement is trivial. Also we can assume without loss of generality that $d(X,Y)\leq \infty$, i.e., $X,Y$ are in the same connected component of $G$, otherwise we can use Lemma~\ref{lemma:splitting} with $S=\emptyset$.
 	The proof goes by induction on $d(X,Y)$. The statement is trivial for $d(X,Y)=0$, and is easy to check for $d(X,Y)=1$, by looking at resample sequences that reach the all $1$ state in at most $0$ step (which is simply the case when everything is sampled to $1$ initially).
 	Now we show the inductive step, assuming we know the statement for $d$, and that $d(X,Y)=d+1$.
 	First we assume, that $\NZ{X}\subseteq\overline{A^X}$, i.e., $A^X\subseteq \Z{X}$.

0 comments (0 inline, 0 general)