From 964f0906252a2dbf83b5df0703dc01a7ccfa941d 2017-09-09 20:25:59 From: Tom Bannink Date: 2017-09-09 20:25:59 Subject: [PATCH] Add boundary definition --- diff --git a/main.tex b/main.tex index 5c66397e30fc5e62d186c5943c89b5bddfaac80c..5b9c7eef507453c9bc3fe2144022f9edaca27806 100644 --- a/main.tex +++ b/main.tex @@ -594,7 +594,7 @@ 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. -\begin{definition}[Events] \label{def:events} +\begin{definition}[Events and notation] \label{def:events} 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. @@ -603,43 +603,33 @@ Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. We define a Marko \begin{align*} \P^{G}_S(A) &= \P^{G}(A \mid \text{All vertices in $S$ get initialized to }1) \end{align*} - \item Boundary $\partial$ \todo{} - \item $d$-Neighbourhood $B(S;d)$ \todo{} + 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 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} -\begin{wrapfigure}[7]{r}{0.25\textwidth} % The first [] argument is number of lines that are narrowed - \centering - \includegraphics{diagram_groups.pdf} - \caption{\label{fig:separatedgroupsGen} Lemma \ref{lemma:eventindependenceGen}.} -\end{wrapfigure} -The following lemma considers two vertices $v,w$ that are never ``crossed'' so that two halves of the cycle become independent. -\begin{lemma}[Conditional independence] \label{lemma:eventindependenceGen} - Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two separated groups of zeroes as in Figure \ref{fig:separatedgroupsGen}. Let $v$, $w$ be any indices inbetween the groups, such that $b_1$ lies on one side of them and $b_2$ on the other, as shown in the figure. Furthermore, let $A_1$ be any event that depends only on the sites ``on the $b_1$ side of $v,w$'', and similar for $A_2$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have +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^{(n)}_b(\mathrm{NZ}^{(v,w)}, A_1, A_2) + \P^{G}_S(\NZ{S} \cap A^X \cap A^Y) &= - \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)}, A_1) - \; \cdot \; - \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)}, A_2) \\ - \P^{(n)}_b(A_1, A_2 \mid \mathrm{NZ}^{(v,w)}) - &= - \P^{(n)}_{b_1}(A_1 \mid \mathrm{NZ}^{(v,w)}) + \P^{G\setminus Y}_S(\NZ{S} \cap A^X) \; \cdot \; - \P^{(n)}_{b_2}(A_2 \mid \mathrm{NZ}^{(v,w)}) .%\\ - %R_{b,\mathrm{NZ}^{(v,w)},A_1,A_2} - %&= - %R_{b_1,\mathrm{NZ}^{(v,w)},A_1} - %\; + \; - %R_{b_2,\mathrm{NZ}^{(v,w)},A_2} + \P^{G\setminus X}_S(\NZ{S} \cap A^Y) \end{align*} - %up to any order in $p$. \end{lemma} +%\newcommand{\initone}[1]{\textsc{InitOne}_#1} \begin{proof} - From any path $\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)}$ we can construct paths $\xi_1\in\start{b_1}\cap \mathrm{NZ}^{(v,w)}$ and $\xi_2\in\start{b_2}\cap\mathrm{NZ}^{(v,w)}$ as follows. Let us write the path $\xi$ as - $$\xi=\left( (\text{initialize }b), (z_1, s_1, r_1), (z_2, s_2, r_2), ..., (z_{|\xi|}, s_{|\xi|}, r_{|\xi|}) \right)$$ - where $z_i\in[n]$ denotes the number of zeroes in the state before the $i$th step, $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. We have + 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|}) . @@ -738,7 +728,7 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t \P^{(n)}_{b} (\NZ{v,w} \cap A) = \P^{[v,w]}_b (\NZ{v,w}\cap A) . \end{align*} If vertex $v$ and $w$ never become zero, then the zeroes never get outside of the interval $[v,w]$ and we can ignore the entire circle and only focus on the process within $[v,w]$. - We can apply this to the result of Lemma \ref{lemma:eventindependenceGen}, to get + We can apply this to the result of Lemma \ref{lemma:splitting}, to get \begin{align*} \P^{(n)}_b(\mathrm{NZ}^{(v,w)} \cap A \cap B) &=