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

Changeset - f99db951a095

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Tom Bannink - 8 years ago 2017-09-07 17:27:27
tom.bannink@cwi.nl

Change figure position to wrapfigure

1 file changed with 13 insertions and 8 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -6,12 +6,13 @@ @@
 \usepackage{fullpage}
 \usepackage{graphics}
 \usepackage{diagbox}
 \usepackage[table]{xcolor}% http://ctan.org/pkg/xcolor
 \usepackage{graphicx}
 \usepackage{wrapfig}
 \usepackage{caption}
 \captionsetup{compatibility=false}
 \graphicspath{{./}}
 \usepackage{tikz}
     where the boundary of $[n]$ is site $1$ and site $n$, and the boundary of $[a,b]$ are $a$ and $b$.
 \end{definition}
 %Note that we have $\P^{(n)}(\start{b}) = (1-p)^{|b|}p^{n-|b|}$ by definition of our Markov Chain.
 \begin{definition}[Vertex visiting event] \label{def:visitingResamplings}
     Denote by $\mathrm{Z}^{(v)}$ the event that site $v$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(v)}$, i.e. the event that site $v$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(v,w)} := \mathrm{NZ}^{(v)} \cap \mathrm{NZ}^{(w)}$, i.e. the event that \emph{both} $v$ and $w$ do not become zero before termination.
 \end{definition}
 \begin{figure}
 	\begin{center}
     	\includegraphics{diagram_groups.pdf}
     \end{center}
     \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependence}. Here $b_1,b_2\in\{0,1\}^n$ are bitstrings such that all zeroes of $b_1$ and all zeroes of $b_2$ are separated by two indices $v,w$.}
 \end{figure}
 \begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}
 %\begin{figure}
 %	\begin{center}
 %    	\includegraphics{diagram_groups.pdf}
 %    \end{center}
 %    \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependence}. Here $b_1,b_2\in\{0,1\}^n$ are bitstrings such that all zeroes of $b_1$ and all zeroes of $b_2$ are separated by two indices $v,w$.}
 %\end{figure}
 \begin{wrapfigure}{r}{0.25\textwidth}
     \centering
     \includegraphics{diagram_groups.pdf}
     \caption{\label{fig:separatedgroups} Lemma \ref{lemma:eventindependence}.}
 \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:eventindependence} \label{claim:eventindependence}
     Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. 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
     \begin{align*}
         \P^{(n)}_b(\mathrm{NZ}^{(v,w)}, A_1, A_2)
         &=
         \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)}, A_1)
         \; \cdot \;
         %R_{b_1,\mathrm{NZ}^{(v,w)},A_1}
         %\; + \;
         %R_{b_2,\mathrm{NZ}^{(v,w)},A_2}
     \end{align*}
     %up to any order in $p$.
 \end{lemma}
 The lemma says that conditioned on $v$ and $w$ not being crossed, the two halves of the cycle are independent.
 \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
     \begin{align*}

0 comments (0 inline, 0 general)