Changeset - 75a17e59e436
[Not reviewed]
Merge
0 1 0
Andras Gilyen - 8 years ago 2017-09-07 18:50:52
gilyen@clayoquot.swat.cwi.nl
1 file changed with 61 insertions and 13 deletions:
main.tex
61
13
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -9,6 +9,7 @@
 
\usepackage{diagbox}
 
\usepackage[table]{xcolor}% http://ctan.org/pkg/xcolor
 
\usepackage{graphicx}
 
\usepackage{wrapfig}
 
\usepackage{caption}
 
\captionsetup{compatibility=false}
 
\graphicspath{{./}}
 
@@ -438,10 +439,10 @@ The process on the finite chain has the following modification at the boundary:
 

	
 
%Note that an \emph{event} is a subset of all possible paths of the Markov Chain.
 
\begin{definition}[Events conditioned on starting state] \label{def:conditionedevents}
 
    For any state $b\in\{0,1\}^n$, define $\textsc{start}(b)$ as the event that the starting state of the chain is the state $b$. For any event $A$, define
 
    For any state $b\in\{0,1\}^n$, define $\start{b}$ as the event that the starting state of the chain is the state $b$. For any event $A$, define
 
    \begin{align*}
 
        \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \textsc{start}(b)) %\\
 
        %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b))
 
        \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) %\\
 
        %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \start{b})
 
    \end{align*}
 
    Furthermore, for the Markov Chain on the finite chain, define
 
    \begin{align*}
 
@@ -449,17 +450,22 @@ The process on the finite chain has the following modification at the boundary:
 
    \end{align*}
 
    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)}(\textsc{start}(b)) = (1-p)^{|b|}p^{n-|b|}$ by definition of our Markov Chain.
 
%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)
 
@@ -480,7 +486,6 @@ The process on the finite chain has the following modification at the boundary:
 
    \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
 
@@ -576,7 +581,7 @@ The lemma says that conditioned on $v$ and $w$ not being crossed, the two halves
 
    Let $b_I$ be the state where everything is $1$, apart from the vertices corresponding to $I$, which are set $0$. Define $\P^{(n)}_I(A)=\P^{(n)}_{b_I}(A)$ which is defined in Definition \ref{def:conditionedevents}.
 
\end{definition}
 

	
 
\begin{lemma}[Conditional independence] \label{lemma:eventindependenceNew}
 
\begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNew}
 
	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)
 
@@ -595,6 +600,49 @@ The lemma says that conditioned on $v$ and $w$ not being crossed, the two halves
 
	\end{align*}
 
	where there is no longer a condition on the starting state.
 
\end{lemma}
 
\begin{proof}
 
    We start by relating the different Markov Chains.
 
    If $b$ is a starting state where all the zeroes are inside an interval $[v,w]$ (not on the boundary) then we can switch between the cycle and the finite chain:
 
    \begin{align*}
 
        \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:eventindependence}, to get
 
    \begin{align*}
 
        \P^{(n)}_b(\mathrm{NZ}^{(v,w)} \cap A \cap B)
 
        &=
 
        \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)} \cap A)
 
        \; \cdot \;
 
        \P^{[v,w]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)} \cap B)
 
    \end{align*}
 
    Note that this also holds if $b$ has zeroes on the boundary (i.e. $b_v=0$ or $b_w=0$), because then both sides of the equations are zero.
 
    For the starting state we have the expression $\P^{(n)}(\start{b}) = (1-p)^{|b|} p^{n-|b|}$ so it splits into a product
 
    \begin{align*}
 
        \P^{(n)}(\start{b}) = \P^{[v,w]}(\start{b|_{[v+1,w-1]}}) \;\; \P^{[w,v]}(\start{b|_{[w,v]}})
 
    \end{align*}
 
    where we have to be careful to count the boudary only once.
 
    We now have
 
    \begin{align*}
 
		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)
 
        &= \sum_{b\in\{0,1\}^n} \P^{(n)}_b(\mathrm{NZ}^{(v,w)}\cap A\cap B) \; \P^{(n)}(\start{b}) \\
 
        &= \sum_{b\in\{0,1\}^n}
 
            \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)}\cap A)
 
            \P^{[v,w]}(\start{b|_{[v+1,w-1]}})
 
            \\ &\qquad\qquad\quad
 
            \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)}\cap B)
 
            \P^{[w,v]}(\start{b|_{[w,v]}}) \\
 
        &= \left( \sum_{\substack{b_1\in\{0,1\}^{[v,w]}\\ b_v=b_w=1}}
 
            \P^{[v,w]}_{b_1}(\mathrm{NZ}^{(v,w)}\cap A)
 
            \P^{[v,w]}(\start{b_1}) \right)
 
            \\ &\qquad \cdot
 
           \left( \sum_{b_2\in\{0,1\}^{[w,v]}}
 
            \P^{[w,v]}_{b_2}(\mathrm{NZ}^{(v,w)}\cap B)
 
            \P^{[w,v]}(\start{b_2}) \right) \\
 
        &=  \P^{[v,w]}_{b_v=b_w=1}(\mathrm{NZ}^{(v,w)}\cap A) \cdot
 
            \P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B)
 
    \end{align*}
 
    The second equality follows in a similar way.
 
\end{proof}
 

	
 
    Some notation: let $P$ be an interval $[a,b]$. We say $P$ is a \emph{patch} when the $\Z{i}$ event holds for all $i \in [a,b]$ and $\NZ{a-1}$ and $\NZ{b+1}$ holds. We denote this event by $P\in\mathcal{P}$, so
 
	\begin{align*}
0 comments (0 inline, 0 general)