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

@@ -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)

&=