diff --git a/main.tex b/main.tex index 69c2c4865b04f01e3b27b2e2833a3ff70771d9d6..fef9c957362806b4b9b4a5c91984cb280f79cf79 100644 --- a/main.tex +++ b/main.tex @@ -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*}