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

 \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).

0 comments (0 inline, 0 general)