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

Changeset - c2fa910c4916

Parent rev.

Child rev.

[Not reviewed]

0 3 0

Tom Bannink - 8 years ago 2017-07-06 17:33:23
tom.bannink@cwi.nl

Add circle version of lemma

3 files changed with 115 insertions and 49 deletions:

diagram_circle_lemma.pdf

bin+mod

diagram_circle_lemma.tex

main.tex

105

0 comments (0 inline, 0 general)

diagram_circle_lemma.pdf

➞

Show inline comments

binary diff not shown

diagram_circle_lemma.tex

➞

Show inline comments

@@ @@ -34,41 +34,44 @@ @@
     % Green triangles
     \foreach \a in {6,8,9,10,11,14,15,17} {
         \draw[fill,green] ({\a*\step}:{\r-0.3}) +(-0.15,-0.1) -- +(0.15,-0.1) -- +(0,0.15);
+    }
     % Legend
-    \draw (-1,0)+(-0.5,-1) rectangle +(2.2,1);
+    \draw (-1,0)+(-0.5,-1) rectangle +(2.6,1);
     \draw[fill,red]   (-1.1,0.5)  circle (0.09);
     \draw[fill,blue]  (-1.1,0)    +(-0.1,-0.1) rectangle +(0.1,0.1);
     \draw[fill,green] (-1.1,-0.5) +(-0.15,-0.1) -- +(0.15,-0.1) -- +(0,0.15);
     \draw[anchor=west] (-1,0.5)  node {$I$};
     \draw[anchor=west] (-1,0)    node {$I_{\mathrm{in}(n-l,k)}$};
     \draw[anchor=west] (-1,-0.5) node {$I_{\mathrm{out}(n-l,k)}$};
     \draw[anchor=west] (-1,0)    node {$I\cap [{\color{gray}n}{-l},r]_0$};
     \draw[anchor=west] (-1,-0.5) node {$I\setminus[{\color{gray}n}{-l},r]_0$};
     % Bigger circle
     \foreach \a in {-5,...,3} {
         \draw[-,dashed] ({\a*\step}:\r+1) -- ({(\a+1)*\step}:\r+1);
         %\draw ({\a*\step}:\r+1) circle (0.05);
+    }
     \draw ({-5*\step}:\r+1) +(0.2,-0.2) node {$n-l$};
     \draw ({4*\step}:\r+1) +(0.2,0.2) node {$k$};
     \draw ({-5*\step}:\r+1) +(0.2,-0.2) node {${\color{gray}n}{-l}$};
     \draw ({4*\step}:\r+1) +(0.2,0.2) node {$r$};
+    %
     % Arrows with labels
+    %
     % 0
     \draw ({0*\step}:\r-0.3) node {$0$};
     % 1
     \draw ({1*\step}:\r-0.3) node {$1$};
     % n/2
     \draw ({12*\step}:\r-0.3) node {$\frac{n}{2}$};
     % n-1
     \draw ({-1*\step}:\r-0.3) +(-0.4,0) node {${\color{gray}n}{-1}$};
     % i_*
     \draw[->] ({10*\step}:\r-1) -- ({10*\step}:\r-0.2);
     \draw ({10*\step}:\r-1) +(0.3,0) node {$i_*$};
     % n-1
     \draw ({-1*\step}:\r-0.3) +(-0.4,0) node {$n-1$};
     % j
     \draw[->] ({0*\step}:\r-1.3) -- ({0*\step}:\r-0.8);
     \draw ({0*\step}:\r-1) +(-0.4,0) node {$j$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

@@ @@ -56,12 +56,19 @@ @@
 \newcommand{\SharpP}{\textsf{\# P}}
 \newcommand{\diam}[1]{\mathcal{D}\left(#1\right)}
 \newcommand{\paths}[1]{\mathcal{P}\left(#1\to\mathbf{1}\right)}
 \newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}
 \newcommand{\gaps}[1]{#1_{\mathrm{gaps}}}
 \renewcommand{\P}{\mathbb{P}}
 \newcommand{\NZ}[1]{\mathrm{NZ}^{(#1)}}
 \newcommand{\Z}[1]{\mathrm{Z}^{(#1)}}
 %\newcommand{\dist}[1]{d_{\!\!\not\,#1}}
 \newcommand{\dist}[1]{d_{\neg #1}}
 \newcommand{\todo}[1]{{\color{red}\textbf{TODO:} #1}}
 \long\def\ignore#1{}
 \newtheorem{theorem}{Theorem}
 \newtheorem{corollary}[theorem]{Corollary}%[theorem]
 \newtheorem{lemma}[theorem]{Lemma}
     &= 0 + \mathcal{O}(p^{|C|+k})
 \end{align*}
 where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$.
 \newpage
 \subsection{Proving the strong cancellation claim}
-It is useful to introduce some new notation:
+It is useful to introduce some new notation. 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$ and any event $A$ (where an event is a subset of all possible paths of the Markov Chain), define
+    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
     \begin{align*}
         \mathbb{P}_b(A) &= \mathbb{P}(A \;|\; \text{start in }b) \\
         R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; \& \; \text{start in }b)
         \mathbb{P}_b(A) &= \mathbb{P}(A \;|\; \textsc{start}(b)) \\
         R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \textsc{start}(b))
     \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. 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}
         \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\
         &=
         \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)
         \; \cdot \;
         \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).
     \end{align*}
-    The second equality follows directly from Bayes rule and removing $A_1,A_2$.
+    The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.
     For the third 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_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}}
 	The main insight that Lemma~\ref{lemma:probIndep} gives is that if we separate the slots to two halves, in order to see the cancellation of the contribution of the expected resamples on the right, we can simply pair up the left configurations by the particle filling the leftmost slot. And similarly for cancelling the left expectations we pair up right configurations based on the rightmost filling.
 	Also this claim finally ``sees'' how many empty places are between slots. These properties make it possible to use this lemma to prove the sought linear bound. We show it for the infinite chain, but with a little care it should also translate to the circle.
+~
 Here, I (Tom) tried to set up the same Lemma but for the circle instead of the infinite chain.
 This time, it is no longer $I_\mathrm{max}$ but any vertex $i_* \in I$, and $I' = I \setminus \{i_*\}$. Without loss of generality, we can assume that $i_* \leq n/2$ so that the distance to $0$ is simply $d(i_*,0)=i_*$ (because if not then we can relabel the vertices and count the other way around so that $i_* \to n-i_*$). The goal is now to prove:
 \begin{align*}
     P_I(Z^{(0)}) = P_{I'}(Z^{(0)}) + \mathcal{O}(p^{\mathrm{d}(i_*,0) + 1 - |I|})
 \end{align*}
 Note that when we refer to an interval $[a,b]$ on the circle we could be referring to two possible intervals because of the periodicity of the circle. In the following, whenever we refer to an interval $[a,b]$ we refer to the interval with vertex 0 on the \emph{inside}.
 Here, I (Tom) tried to set do the same Lemma but for the circle instead of the infinite chain.
 \begin{lemma}[Startingstate dependence] \label{lemma:probIndepCircle}
     Let $d(a,b)$ be the distance between $a,b\in[n]$ on the circle, so $d(a,b)=\min(|a-b| , n-|a-b|)$. Let $\dist{s}(a,b)$ be the distance between $a,b$ when taking the path that does \emph{not} cross $s$. Let $I\subseteq [n]$ be a non-empty set of vertices. Let $i_* \in I$ and define $I' = I \setminus \{i_*\}$. Let $j,s\notin I$, with $j\neq s$ be any vertices not in $I$.
     Then
     \begin{align*}
         \P_{I}(\Z{j})        &= \P_{I'}(\Z{j})        + \mathcal{O}(p^{d(i_*,j) + 1 - |I|}) \\
         \P_{I}(\Z{j},\NZ{s}) &= \P_{I'}(\Z{j},\NZ{s}) + \mathcal{O}(p^{\dist{s}(i_*,j) + 1 - |I|}) .
     \end{align*}
 \end{lemma}
 \begin{proof}
     We will prove both statements inductively on $|I|$. For $|I|=1$ we have $I=\{i_*\}$ and $I'=\emptyset$, so $\P_{I'}(\Z{j})=0$ and
     \begin{align*}
         \P_{I}(\Z{j})       &= \mathcal{O}(p^{d(i_*,j)}) \\
         \P_{I}(\Z{j},\NZ{s}) &= \mathcal{O}(p^{\dist{s}(i_*,j)})
     \end{align*}
     simply because a chain of zeroes has to be formed between $i_*$ and $j$, and in the second case this chain can not go through $s$. Now assume both statements hold up to $|I|-1$, then we prove them both for sets of size $|I|$.
 For $a,b\in[n]$, define the event ``zeroes patch'' as the event of getting zeroes inside the interval $[a,b]$ but not on the boundary, i.e.  $\mathrm{ZP}^{[a,b]} = \mathrm{NZ}^{(a)} \cap \mathrm{Z}^{(a+1)} \cap \mathrm{Z}^{(a+2)} \cap \cdots \cap \mathrm{Z}^{(b-1)} \cap \mathrm{NZ}^{(b)}$ (where we assume that $\mathrm{Z}^{(0)}$ is part of this intersection).
     When we refer to an interval $[a,b]$ on the circle we could be referring to two possible intervals because of the periodicity of the circle. Define $[a,b]_j$ as the interval with vertex $j$ on the \emph{inside}. Furthermore by $-a$ we mean the vertex $n-a$, as one would expect modulo $n$.
     %If we refer to only $[a,b]$ then we mean $\{a,a+1,...,b\}$ where numbers are considered modulo $n$. So $[a,b]$ and $[b,a]$ are different intervals that cover the circle together.
 Furthermore, define the `inside' and `outside' of $I$ as $I_{\mathrm{in}(a,b)} = I\cap[a,b]$ and $I_{\mathrm{out}(a,b)} = I \setminus [a,b]$.
 The following diagram illustrates these definitions.
 \begin{center}
     \includegraphics{diagram_circle_lemma.pdf}
 \end{center}
 \begin{align*}
     P_{I}(\mathrm{Z}^{(0)})
     &=\sum_{\substack{l,k=1\\k+l<n}}
     P_I(\mathrm{ZP}^{[n-l,k]}) \tag{the events are a partition}\\
     &=\sum_{\substack{l,k=1\\k+l<n\\k,n-l\notin I}}
     P_I(\mathrm{ZP}^{[n-l,k]}) \tag{$\mathbb{P}(\mathrm{ZP}^{[a,b]})=0$ for $a\in I$ or $b\in I$}
 \end{align*}
 Note that if $[-l,k]$ does not `touch' $I$ then $P_I(\mathrm{ZP}^{[-l,k]}) = 0$.
 Furthermore, we have $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{k+l-1-|I_{\mathrm{in}(n-l,k)}|})$. If $k > \mathrm{d}(i_*,0)$ or $l > \mathrm{d}(i_*,0)$ then this gives $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{\mathrm{d}(i_*,0) + 1 - |I|})$ since $|I_\mathrm{in}| \leq |I|$. Therefore we have
 \begin{align*}
     P_I(\mathrm{Z}^{(0)})
     &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}
     P_I(\mathrm{ZP}^{[n-l,k]})
     + \mathcal{O}(p^{i_* + 1 - |I|}) \\
     &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}
     P_{I_{\mathrm{in}(n-l,k)}}(\mathrm{ZP}^{[n-l,k]}) \cdot
     P_{I_{\mathrm{out}(n-l,k)}}(\mathrm{NZ}^{(n-l,k)})
     + \mathcal{O}(p^{i_* + 1 - |I|}) \\
     \tag{by Claim~\ref{claim:eventindependence} for $n-l,k\notin I$} \\
     &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}
     P_{I'_{\mathrm{in}(n-l,k)}}(\mathrm{ZP}^{[n-l,k]}) \cdot
     P_{I_{\mathrm{out}(n-l,k)}}(\mathrm{NZ}^{(n-l,k)})
     + \mathcal{O}(p^{i_* + 1 - |I|})
 \end{align*}
 Now we are supposed to use the induction step, but this is where I got stuck.
     Without loss of generality, we can assume that $0=j < i_* < s < n$. We will now consider intervals around vertex 0.
     For $l,r\geq 1$ and $l+r\leq n$, define the event ``zeroes patch'' $\mathrm{ZP}^{[-l,r]_0}$ as the event of getting zeroes inside the interval $[-l,r]_0$ but not on the boundary, i.e.
     $$\mathrm{ZP}^{[-l,r]_0} = \NZ{-l} \cap \Z{-l+1} \cap \cdots \cap \Z{0} \cap \cdots \cap \Z{r-1} \cap \NZ{r}$$
     Note that there are $r+l-1$ `zeroes' in this event, so $\P_{J}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{r+l-1-|J|})$ for $J\subseteq[-l,r]_0$.
     Claim:
     \begin{align*}
         \P_{I}(\mathrm{ZP}^{[-l,r]_0}) &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
         + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})
     \end{align*}
     \todo{These special cases.}
     If $r\geq i_*$ or $l\geq n-i_*$ then $\P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{d(i_*,0) + 1 - |I|})$.
     If $-l\in I$ or $r\in I$ then the left hand side is zero so the claim holds.
     If $[-l,r]_0$ has no overlap with $I$ then both sides of the above expression are zero so it also holds. We are left with the case where, $-l,r,\notin I$ and $[-l,r]_0 \cap I \neq \emptyset$ and $i_*\notin[-l,r]_0$.
     The following diagram illustrates the situation
     \begin{center}
         \includegraphics{diagram_circle_lemma.pdf}
     \end{center}
     Note that by Claim~\ref{claim:eventindependence} we have
     \begin{align*}
         \P_{I}(\mathrm{ZP}^{[-l,r]_0}) = \P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I\setminus [-l,r]_0}(\NZ{a},\NZ{b})
     \end{align*}
     We have $i_*\in I \setminus[-l,r]_0$, and $I\cap[-l,r]_0 = I' \cap [-l,r]_0$. Define $J=I\setminus[-l,r]_0$ and $J'=I'\setminus[-l,r]_0$. We have $|J|<|I|$ so we can apply the induction hypothesis to $J$:
     \begin{align*}
         \P_{J}(\NZ{-l},\NZ{r})
         &=
         - \P_{J}(\Z{-l},\NZ{r})
         - \P_{J}(\Z{r})
         \tag{partition of all events} \\
         &=
         - \P_{J'}(\Z{-l},\NZ{r})
         - \P_{J'}(\Z{r}) \\
         &\quad + \mathcal{O}(p^{\dist{r}(i_*,-l)+1-|J|})
         + \mathcal{O}(p^{d(i_*,r)+1-|J|}) \\
         &=
         \P_{J'}(\NZ{-l},\NZ{b})
         + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|})
     \end{align*}
     Note that the event $\mathrm{ZP}^{[-l,r]_0}$ contains $l+r-1$ zeroes, so $\P_{I \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) = \mathcal{O}(p^{l+r-1-|I\cap[-l,r]_0|})$. This means
     \begin{align*}
         \P_{I}(\mathrm{ZP}^{[-l,r]_0})
         &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0})
         \left( \P_{I' \setminus [-l,r]_0}(\NZ{a},\NZ{b}) + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J|}) \right) \\
         &= \P_{I' \cap [-l,r]_0}(\mathrm{ZP}^{[-l,r]_0}) \;\cdot\; \P_{I'\setminus [-l,r]_0}(\NZ{a},\NZ{b}) \\
         &\qquad + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+1-|J| + l+r-1-|I\cap[-l,r]_0|}) \\
         &= \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
         + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|})
     \end{align*}
     Case separation shows that $\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right) \geq d(i_*,0) + 1$ \todo{prove.}
     Now we can prove the required equalities:
     \begin{align*}
         \P_{I}(\Z{0})
         &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
         \P_I(\mathrm{ZP}^{[-l,r]_0})
         \tag{the events are a partition of $\Z{0}$}\\
         &=\sum_{\substack{l,r\geq 1\\l+r\leq n}}
         \P_{I'}(\mathrm{ZP}^{[-l,r]_0})
         + \mathcal{O}(p^{\min\left( \dist{r}(i_*,-l) , d(i_*,r)\right)+l+r-|I|}) \\
         &= \P_{I'}(\Z{0}) + \mathcal{O}(p^{d(i_*,0)+1-|I|})
     \end{align*}
     Similarly, we have
     \begin{align*}
         \P_{I}(\Z{0} , \NZ{s})
         &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
         \P_{I}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
         \tag{partition of $\Z{0}$}\\
         &=\sum_{l=1}^{n-s}\sum_{r=1}^{s}
         \P_{I'}(\mathrm{ZP}^{[-l,r]_0},\NZ{s})
         + \mathcal{O}(p^{something}) \\
         &= \P_{I'}(\Z{0} , \NZ{s})
         + \sum_{l=1}^{n-s}\sum_{r=1}^{s} + \mathcal{O}(p^{something})
     \end{align*}
     \todo{finish details}
 \end{proof}
 \begin{definition}[Connected patches]
 	Let $\mathcal{P}\subset 2^{\mathbb{Z}}$ be a finite system of finite subsets of $\mathbb{Z}$. We say that the patch set of a resample sequence is $\mathcal{P}$,
 	if the connected components of the vertices that have ever become $0$ are exactly the elements of $\mathcal{P}$. We denote by $A^{(\mathcal{P})}$ the event that the set of patches is $\mathcal{P}$. For a patch $P$ let $A^{(P)}=\bigcup_{\mathcal{P}:P\in \mathcal{P}}A^{(\mathcal{P})}$.
 \end{definition}
 Note by Tom: So $A^{(\mathcal{P})}$ is the event that the set of all patches is \emph{exactly} $\mathcal{P}$ whereas $A^{(P)}$ is the event that one of the patches is equal to $P$ but there can be other patches as well.

0 comments (0 inline, 0 general)