diff --git a/main.tex b/main.tex index baddb12b70fe3995a2936fa00b739de83a4b6297..af2bd5aa5e7d5df7f31a82e70ea28f3e6fe66aa6 100644 --- a/main.tex +++ b/main.tex @@ -59,6 +59,13 @@ \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{} @@ -418,12 +425,12 @@ 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} @@ -471,7 +478,7 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha \; \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} @@ -588,46 +595,102 @@ The intuition of the following lemma is that the far right can only affect the z ~ -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 \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}) + &= + 1 + - \P_{J}(\Z{-l},\NZ{r}) + - \P_{J}(\Z{r}) + \tag{partition of all events} \\ + &= + 1 + - \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}$,