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

Changeset - 589559c13da7

Parent rev.

Child rev.

[Not reviewed]

0 1 2

Tom Bannink - 8 years ago 2017-09-10 03:07:35
tombannink@gmail.com

Add tikz diagram for splitting lemma

3 files changed with 75 insertions and 23 deletions:

diagram_splittinglemma.pdf

bin+new file

diagram_splittinglemma.tex

main.tex

0 comments (0 inline, 0 general)

diagram_splittinglemma.pdf

➞

Show inline comments

		new file 100644
		binary diff not shown

diagram_splittinglemma.tex

➞

Show inline comments

@@ new file 100644 @@
 \documentclass{standalone}
 \usepackage[T1]{fontenc}
 \usepackage{amsmath}
 \usepackage{amsfonts}
 \usepackage{parskip}
 \usepackage{marvosym} %Lightning symbol
 \usepackage[usenames,dvipsnames]{color}
 \usepackage[hidelinks]{hyperref}
 \renewcommand*{\familydefault}{\sfdefault}
 \usepackage{bbm} %For \mathbbm{1}
 %\usepackage{bbold}
 \usepackage{tikz}
 \begin{document}
 \begin{tikzpicture}[scale=0.8]
     \def\width{6};
     \def\height{4};
     %\draw[step=1cm] (0,0) grid (\width,\height);
     % Vertices and edges
     \foreach \x in {0,...,\width} {
         \foreach \y in {0,...,\height} {
             \draw (\x,\y) circle (0.10);
             \ifnum\x<\width
                 \draw (\x,\y)+(0.1,0) -- (\x+0.9,\y);
             \fi
             \ifnum\y<\height
                 \draw (\x,\y)+(0,0.1) -- (\x,\y+0.9);
             \fi
+        }
+    }
+    %
     % The set S : red circles
+    %
     \draw[fill,red] (3,0) circle (0.08);
     \draw[fill,red] (2,1) circle (0.08);
     \draw[fill,red] (3,2) circle (0.08);
     \draw[fill,red] (3,3) circle (0.08);
     \draw[fill,red] (4,4) circle (0.08);
     \draw (3,-0.5) node {$S$};
     % The set X
     \draw[xshift=-0.2cm,dashed] (-0.5,-1.0) -- (2.5,-1.0) -- (2.5,0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.5,1.5) -- (2.5,3.5) -- (3.5,3.5) -- (3.5,4.5) -- (-0.5,4.5) -- cycle;
     \draw (1,-0.5) node {$X$};
     % The set Y
     \draw[xshift=+0.2cm,dashed] (6.5,-1.0) -- (3.5,-1.0) -- (3.5,0.5) -- (2.5,0.5) -- (2.5,1.5) -- (3.5,1.5) -- (3.5,3.5) -- (4.5,3.5) -- (4.5,4.5) -- (6.5,4.5) -- cycle;
     \draw (5,-0.5) node {$Y$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

         \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{center}
     \includegraphics[scale=0.8]{diagram_splittinglemma.pdf}
 \end{center}
 \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}$.
+    We are considering three different Markov Chains, and the events $\NZ{S}$ in the different parts of the equation are events on different probability spaces. We will keep using the same notation for these events because it should be clear from the context which Markov Chain is being considered. We will consider paths (i.e. resampling sequences) and 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:
     \begin{align*}
         \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*}
     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
         \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.
+    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 either $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:
     Now $\xi^{G\setminus Y}$ is a valid path of the Markov Chain associated to the graph $G\setminus Y$ (i.e. with vertices $X\cup S$), because in the original path $\xi^G$, all zeroes in $X$ have been resampled by resamplings in $X$. There can not be a vertex $v\in Y$ such that the resampling of $v$ changed a vertex in $X$, since $X$ and $Y$ are only connected through $S$ and we know $\xi^G\in\NZ{S}$.
     Vice versa, any two paths $\xi^{G\setminus Y}\in\NZ{S}$ and $\xi^{G\setminus X}\in\NZ{S}$ also induce a path $\xi^G\in\NZ{S}$ by simply interleaving the resampling positions. Note that $\xi^{G\setminus Y},\xi^{G\setminus X}$ actually induce $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ paths $\xi^G$ because of the possible orderings of interleaving the resamplings in $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$.
     For a fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ 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]
         \sum_{\substack{\xi^G\in\NZ{S} \text{ s.t.}\\ \xi^G \text{ decomposes into } \xi^{G\setminus Y},\xi^{G\setminus X} }} \P^{G}_S(\xi^G) &=
         \sum_{\text{interleavings of }\xi^{G\setminus Y},\xi^{G\setminus X}} \P(\text{interleaving}) \cdot \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) \\
         &= \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X})
     \end{align*}
     where both sums are over $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ terms.
     This is best explained by an example. Lets consider the following fixed $\xi_1,\xi_2$ and an example interleaving where we choose steps from $\xi_2,\xi_1,\xi_1,\xi_2,\cdots$:
     where both sums are over $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ terms.
     This is best explained by an example. Lets consider the following fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ and an example interleaving where we choose steps from $\xi^{G\setminus X},\xi^{G\setminus Y},\xi^{G\setminus Y},\xi^{G\setminus X},\cdots$:
     \todo{from here}
     \begin{align*}
         \xi_1 &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots  \right) \\
         \xi_2 &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots  \right) \\
         \xi^{G\setminus Y} &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots  \right) \\
         \xi^{G\setminus X} &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots  \right) \\
         \xi   &= \left( (z_1 + z_1', s_1', r_1'), (z_1+z_2', s_1, r_1), (z_2+z_2', s_2, r_2), (z_3+z_2', s_2', r_2'), \cdots \right)
     \end{align*}
-    The probability of $\xi_1$, started from $b_1$, is given by
+    The probability of $\xi^{G\setminus Y}$, started from $b_1$, is given by
     \begin{align*}
         \P^{(n)}_{b_1}[\xi_1] &= \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_1|}|z_{|\xi_1|}) \P(r_{|\xi_1|}) \\
                 &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi_1|}} \P(r_{|\xi_1|}) .
     \end{align*}
-    and similar for $\xi_2$ but with primes.
+    and similar for $\xi^{G\setminus X}$ but with primes.
     The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $\xi$ in the example above.
     \begin{center}
         \includegraphics{diagram_paths2.pdf}
     \end{center}
     For the labels shown within the grid, define $p_{ij} = \frac{z_i}{z_i + z_j'}$.
     The probability of $\xi$ is given by
         \cdots
         \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2] \tag{definition of $\P^{(n)}_{b_i}[\xi_i]$} \\
         &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2] \tag{definition of $p_{i,j}$} \\
         &= \P(\text{path in grid}) \; \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2]
     \end{align*}
     In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This proves the required equality.
     We obtain
     \begin{align*}
         \P^{(n)}_b(\mathrm{NZ}^{(v,w)},A_1,A_2)
         &= \sum_{\substack{\xi\in\start{b} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_1\cap A_2}} \P^{(n)}_b(\xi) \\
         &= \sum_{\substack{\xi_1\in\start{b_1} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_1}} \;\;
           \sum_{\substack{\xi_2\in\start{b_1} \cap \\ \mathrm{NZ}^{(v,w)}\cap A_2}}
         \P^{(n)}_{b_1}(\xi_1)\cdot\P^{(n)}_{b_2}(\xi_2) \\
         &=
         \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1)
         \; \cdot \;
         \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2).
     \end{align*}
     The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.
 \end{proof}
 \begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNewGen}
 	Let $v,w \in [n]$, and let $A$ be any event that depends only on the sites $[v,w]$ (meaning the initialization and resamples) and similarly $B$ an event that depends only on the sites $[w,v]$. (For example $\mathrm{Z}^{(s)}$ or ``$s$ has been resampled at least $k$ times'' for an $s$ on the correct interval). Then we have
 	\begin{align*}
 		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)

0 comments (0 inline, 0 general)