Changeset - fcbfed677dc9
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-06-10 16:26:20
tombannink@gmail.com
Shorten notation of conditional independence lemma
1 file changed with 21 insertions and 23 deletions:
main.tex
21
23
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -416,7 +416,7 @@ It is useful to introduce some new notation:
 
    \end{align*}
 
\end{definition}
 
\begin{definition}[Vertex visiting event] \label{def:visitingResamplings}
 
    Denote by $\mathrm{Z}^{(j)}$ the event that site $j$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(j)}$, i.e. the event that site $j$ does \emph{not} become zero before it terminates.
 
    Denote by $\mathrm{Z}^{(j)}$ the event that site $j$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(j)}$, i.e. the event that site $j$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(j_1,j_2)} := \mathrm{NZ}^{(j_1)} \cap \mathrm{NZ}^{(j_2)}$, i.e. the event that \emph{both} $j_1$ and $j_2$ do not become zero before termination.
 
\end{definition}
 
\begin{figure}
 
	\begin{center}
 
@@ -427,49 +427,47 @@ It is useful to introduce some new notation:
 
\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 ($b_1\lor b_2 = 1^n$) of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. Let $j_1$, $j_2$ 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 $j_1,j_2$'', and similar for $A_2$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have
 
    \begin{align*}
 
        \mathbb{P}_b(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_1, A_2)
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)}, A_1, A_2)
 
        &=
 
        \mathbb{P}_{b_1}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_1)
 
        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)}, A_1)
 
        \; \cdot \;
 
        \mathbb{P}_{b_2}(\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2}, A_2) \\
 
        R_{b,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_1,A_2}
 
        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)}, A_2) \\
 
        R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}
 
        &=
 
        R_{b_1,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_1}
 
        R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1}
 
        \; + \;
 
        R_{b_2,\mathrm{NZ}_{j_1},\mathrm{NZ}_{j_2},A_2}
 
        R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2}
 
    \end{align*}
 
    up to any order in $p$.
 
\end{lemma}
 
The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two halves of the circle are independent. 
 

	
 
\begin{proof}
 
    For clarity we do the proof for the infinite line, when there is only one index. Simply replace $\mathrm{NZ}_j$ by $\mathrm{NZ}_{j_1}\cap\mathrm{NZ}_{j_2}$ for the case of the circle.
 

	
 
    Note that any path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ can be split into paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$. This can be done by taking all resampling positions $r_i$ in $\xi$ and if $r_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add it to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add it to $\xi_2$. Note that now $\xi_1$ is a 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 $j_1,j_2$ 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, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ by simply concatenating the resampling positions. By the same reasoning as in the proof of claim \ref{claim:expectationsum}, we obtain
 
    Note that any path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ can be split into paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$. This can be done by taking all resampling positions $r_i$ in $\xi$ and if $r_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add it to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add it to $\xi_2$. Note that now $\xi_1$ is a 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 $j_1,j_2$ 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, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply concatenating 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 concatenating the resamplings in $\xi_1$ and $\xi_2$. However, all these paths have smaller weight, and by the same reasoning as in the proof of claim \ref{claim:expectationsum} these weights sum to exactly $1$, so we obtain
 
    \begin{align*}
 
        \mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2)
 
        = \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j\cap A_1\cap A_2}} \mathbb{P}[\xi]
 
        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j\cap A_1}}
 
          \sum_{\substack{\xi_2\in\paths{b_1}\\\xi_2 \in \mathrm{NZ}_j\cap A_2}}
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2)
 
        &= \sum_{\substack{\xi\in\paths{b} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] \\
 
        &= \sum_{\substack{\xi_1\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1}} \;\;
 
          \sum_{\substack{\xi_2\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
 
        \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\
 
        &=
 
        \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1)
 
        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)
 
        \; \cdot \;
 
        \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2).
 
        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).
 
    \end{align*}
 
    For the second equality, note that again by the same reasoning as in the proof of claim \ref{claim:expectationsum} we have
 
    \begin{align*}
 
        \mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2) R_{b,\mathrm{NZ}_j,A_1,A_2}
 
        &:= \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\
 
        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j\cap A_1}}
 
          \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}_j\cap A_2}}
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}
 
        &:= \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\
 
        &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}
 
          \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}
 
        \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\
 
        &=
 
        \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2) \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1) R_{b_1,\mathrm{NZ}_j,A_1} \\
 
        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1} \\
 
        &\quad +
 
        \mathbb{P}_{b_1}(\mathrm{NZ}_j,A_1) \mathbb{P}_{b_2}(\mathrm{NZ}_j,A_2) R_{b_2,\mathrm{NZ}_j,A_2} .
 
        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2} .
 
    \end{align*}
 
    Dividing by $\mathbb{P}_b(\mathrm{NZ}_j,A_1,A_2)$ and using the first equality gives the desired result.
 
    Dividing by $\mathbb{P}_b(\mathrm{NZ}_{j_1}\cap\mathrm{NZ}_{j_2},A_1,A_2)$ and using the first equality gives the desired result.
 
\end{proof}
 

	
 
\begin{comment}
0 comments (0 inline, 0 general)