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

Changeset - 2d71071d9d58

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Tom Bannink - 8 years ago 2017-09-09 21:03:51
tombannink@gmail.com

Add small update to splitting lemma proof

1 file changed with 21 insertions and 9 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -583,67 +583,79 @@ Questions: @@
 	\item Can we generalise the proof to other translationally invariant spaces, like the torus?
 	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?
 	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?
 \end{itemize}
 	%I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.
 \newpage
 \section{General graphs proof}
 We consider the following generalization of the Markov Chain.
-Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain and $\E^G$ to denote expectation values.
+Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain and $\E^G$ to denote expectation values.
 \begin{definition}[Events and notation] \label{def:events}
     Let $S\subseteq V$ be any subset of vertices.
+    Let $G=(V,E)$ be a graph. Let $S\subseteq V$ be any subset of vertices.
     \begin{itemize}
         \item Define $\Z{S}$ as the event that \emph{all} vertices in $S$ become zero at any point in time before the Markov Chain terminates.
         \item Define $\NZ{S}$ as the event that \emph{none} of the vertices in $S$ become zero at any point in time before the Markov Chain terminates.
         \item Define for any event $A$:
             \begin{align*}
                 \P^{G}_S(A) &= \P^{G}(A \mid \text{All vertices in $S$ get initialized to }1)
             \end{align*}
             The condition does not apply to subsequent resamplings of vertices in $S$, it only specifies the initial assignment.
         \item Define the $d$-neighbourhood $B(S;d)$ of $S$ as the set of vertices reachable from $S$ within $d$ steps.
         \item Define $G\setminus S$ as the graph obtained by removing from $G$ all vertices in $S$ and edges adjacent to $S$.
         \item Define the $d$-neighbourhood $B^G(S;d)$ of $S$ as the set of vertices reachable from $S$ within $d$ steps.
         \item Define the boundary $\partial S$ of $S$ as the set of vertices adjacent to $S$, excluding $S$ itself. In other words $\partial S = B(S;1) \setminus S$.
     \end{itemize}
 \end{definition}
 The following Lemma says that if a set $S$ splits the graph in two, then those two parts become independent if the vertices in $S$ never become zero.
 \begin{lemma}[Splitting lemma] \label{lemma:splitting}
     \todo{Picture of $S,X,Y$.}
     Let $G=(V,E)$ be a graph. Let $S,X,Y\subseteq V$ be a partition of the vertices, such that $X$ and $Y$ are disconnected in the graph $G\setminus S$. Furthermore, let $A^X$ and $A^Y$ be any events that depends only on the sites in $X$ and $Y$ respectively. Then we have
     \begin{align*}
         \P^{G}_S(\NZ{S} \cap A^X \cap A^Y)
         &=
         \P^{G\setminus Y}_S(\NZ{S} \cap A^X)
         \; \cdot \;
         \P^{G\setminus X}_S(\NZ{S} \cap A^Y)
     \end{align*}
 \end{lemma}
 %\newcommand{\initone}[1]{\textsc{InitOne}_#1}
 \begin{proof}
     We are considering three different Markov Chains and we will consider paths (i.e. resampling sequences) of them. We will use a superscript to denote to which Markov Chain a path belongs. Let $\xi^G \in \NZ{S}$ be a path of the Markov Chain associated to the resample process on the graph $G$, that satisfies the event $\NZ{S}$.
     From $\xi^G$ we will now construct paths $\xi^{G\setminus Y} \in \NZ{S}$ and $\xi^{G \setminus X} \in \NZ{S}$ of the other Markov Chains satisfying the corresponding events on those Markov Chains.
     Let us write the path $\xi^G$ as an initialization and a sequence of resamplings:
     $$\xi^G=\left( (\text{initialize to }b), (z_1, v_1, r_1), (z_2, v_2, r_2), ..., (z_{|\xi^G|}, v_{|\xi^G|}, r_{|\xi^G|}) \right)$$
     where $1 \leq z_i \leq |V|$ denotes the number of zeroes in the state before the $i$th step, $v_i\in V$ denotes the site that was resampled and $r_i\in \{0,1\}^{d(v_i)+1}$ is the result of the resampled bits. Here $d(v_i)$ is the degree of vertex $v_i$. We have
     \todo{from here}
     \begin{align*}
         \P^{(n)}_b[\xi] &= \P(\text{pick }s_1 | z_1) \P(r_1) \P(\text{pick }s_2 | z_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi|} | z_{|\xi|}) \P(r_{|\xi|}) \\
                 &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi|}} \P(r_{|\xi|}) .
         \xi^G=\left( (\text{initialize to }b), (z_1, v_1, r_1), (z_2, v_2, r_2), ..., (z_{|\xi^G|}, v_{|\xi^G|}, r_{|\xi^G|}) \right)
     \end{align*}
     To construct $\xi_1$ and $\xi_2$, start with $\xi_1 = \left( (\text{initialize }b_1) \right)$ and $\xi_2 = \left( (\text{initialize }b_2) \right)$. For each step $(z_i,s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $v,w$'' then append $(z^{(1)}_i,s_i,r_i)$ to $\xi_1$ and if its ``on the $b_2$ side of $v,w$'' then append $(z^{(2)}_i,s_i,r_i)$ to $\xi_2$. Here $z^{(1)}_i$ is the number of zeroes that were on the $b_1$ side and $z^{(2)}_i$ is the number of zeroes on the $b_2$ side so we have $z_i = z^{(1)}_i + z^{(2)}_i$.
     where $b\in\{0,1\}^V$ is the initial state, $1 \leq z_i \leq |V|$ denotes the number of zeroes in the state before the $i$th step, $v_i\in V$ denotes the site that was resampled and $r_i\in \{0,1\}^{d(v_i)+1}$ is the result of the resampled bits. Here $d(v_i)$ is the degree of vertex $v_i$. By definition of the resample process, we have
     \begin{align*}
         \P^{G}_S(\xi^G) &=
         \P(\text{initialize }b \mid \text{initialize $S$ to }1)
         \P(\text{pick }s_1 \mid z_1) \P(r_1)
         \P(\text{pick }s_2 \mid z_2) \P(r_2) \cdots \\
         &= \frac{(1-p)^{|b|} p^{|V|-|b|}}{(1-p)^{|S|}} \cdot
         \frac{1}{z_1} \P(r_1) \cdot
         \frac{1}{z_2} \P(r_2) \cdots
         \frac{1}{z_{|\xi^G|}} \P(r_{|\xi^G|}) .
     \end{align*}
     Let $b|_{G\setminus X}$ be the restriction of $b$ to $G\setminus X$ and similar for $b|_{G\setminus Y}$.
     To construct $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$, start with $\xi^{G\setminus Y} = \left( (\text{initialize }b|_{G\setminus Y}) \right)$ and $\xi^{G\setminus X} = \left( (\text{initialize }b|_{G\setminus X}) \right)$. For each step $(z_i,v_i,r_i)$ in $\xi^G$ do the following: if $v_i \in X$ then append $(z^{X}_i,v_i,r_i)$ to $\xi^{G\setminus Y}$ and if $v_i \in Y$ then append $(z^{Y}_i,v_i,r_i)$ to $\xi^{G\setminus X}$.
     Here $z^{X}_i$ is the number of zeroes that were in $X$ and $z^{Y}_i$ is the number of zeroes in $Y$. We have $z_i = z^{X}_i + z^{Y}_i$ because $\xi^G\in\NZ{S}$ so there can not be any zero in $S$; they all have to be in $X$ or $Y$. Furthermore, this also makes sure that we always have $v_i\in X$ or $v_i\in Y$ since only vertices that are zero can be chosen to resample.
     \todo{from here}
     %Let the resulting paths be
     %\begin{align*}
     %    \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\
     %    \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right)
     %\end{align*}
     Now $\xi_1$ is a valid (terminating) path from $b_1$ to $\mathbf{1}$, because in the original path $\xi$, all zeroes ``on the $b_1$ side'' have been resampled by resamplings ``on the $b_1$ side''. Since the sites $v,w$ inbetween never become zero, there can not be any zero ``on the $b_1$ side'' that was resampled by a resampling ``on the $b_2$ side''.
     Vice versa, any two paths $\xi_1\in\start{b_1}\cap \mathrm{NZ}^{(v,w)}$ and $\xi_2\in\start{b_2}\cap\mathrm{NZ}^{(v,w)}$ also induce a path $\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$.
     For a fixed $\xi_1,\xi_2$ we will now show the following:
     \begin{align*}
         \sum_{\substack{\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P^{(n)}_b[\xi] &=
         \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2] \\
         &= \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2]

0 comments (0 inline, 0 general)