From f66b48a711a76812a6669a1cbd6eb49212ad9c39 2017-09-08 10:56:57 From: Tom Bannink Date: 2017-09-08 10:56:57 Subject: [PATCH] Remove unused definition --- diff --git a/main.tex b/main.tex index d1cad055bc49ef6190a224e51eb23566459ed372..19638717389c40395a568df2656edaafd3689e84 100644 --- a/main.tex +++ b/main.tex @@ -245,42 +245,26 @@ \newpage \section{Proving that $a_k^{(k+1)}=a_k^{(n)}$ for all $n>k$} -It is useful to introduce some new notation. We will consider variations of the Markov Chains: +We consider $R^{(n)}(p)$ as a power series in $p$ and our main aim in this section is to show that $R^{(n)}(p)$ and $R^{(n+k)}(p)$ are the same up to order $n-1$. + +The proof will consider variations of the Markov Chain: \begin{itemize} \item $\P^{(n)}$ refers to the original process on the length-$n$ cycle. \item $\P^{[a,b]}$ or $\P^{[n]}$ refers to a similar Markov Chain but on a finite chain ($[a,b]$ or $[1,n]$). \end{itemize} -The process on the finite chain has the following modification at the boundary: if a boundary site is resampled, it can only resample its single neighbour so it draws only two new bits. +The process on the finite chain has the following modification at the boundary: if a boundary site is resampled, it can only resample itself and its single neighbour so it draws only two new bits. We use the notation $\E^{(n)}$,$\E^{[a,b]}$ and $\E^{[n]}$ similarly for denoting expectations. -\begin{definition}[Paths] - We define a \emph{path} of the Markov Chain as a sequence of states and resampling choices $\xi=((b_0,r_0),(b_1,r_1),...,(b_k,r_k)) \in (\{0,1\}^n\times[n])^k$ indicating that at time $t$ Markov Chain was in state $b_t\in\{0,1\}^n$ and then resampled site $r_t$. We denote by $\mathbb{P}[\xi]$ the probability that the process followed this path. - We denote by $\paths{b}$ the set of all valid paths $\xi$ that start in state $b$ and end in state $\mathbf{1} := 1^n$. -\end{definition} -We can write the expected number of resamplings per site $R^{(n)}(p)$ as -\begin{align} -R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1\}^{n}} \rho_b \; R_b(p) \label{eq:originalsum} , -\end{align} -where $R_b(p)$ is the expected number of resamplings when starting from configuration $b$ -\begin{align*} -R_b(p) &= \sum_{\xi \in \paths{b}} \mathbb{P}[\xi] \cdot |\xi| . -\end{align*} - -We consider $R^{(n)}(p)$ as a power series in $p$ and our main aim in this section is to show that $R^{(n)}(p)$ and $R^{(n+k)}(p)$ are the same up to order $n-1$. - %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 $\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 \;|\; \start{b}) %\\ - %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \start{b}) - \end{align*} - Furthermore, for $v\in[n]$ we 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$ and any $v\in[n]$, define \begin{align*} - \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1), + \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) \\ + \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1) \\ + \P^{[n]}_{b_v=b_w=1}(A) &= \P^{[n]}(A \;|\; v\text{ and }w\text{ are initialized to }1) , \end{align*} - and we define similarly $\P^{[n]}_{b_v=b_w=1}(A)$ for $v,w\in[n]$. + The last two probabilities are not conditioned on any other bits of the starting state. \end{definition} %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} @@ -292,13 +276,13 @@ We consider $R^{(n)}(p)$ as a power series in $p$ and our main aim in this secti % \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} +\begin{wrapfigure}[7]{r}{0.25\textwidth} % The first [] argument is number of lines that are narrowed \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 + Let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two separated groups of zeroes 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) &= @@ -393,19 +377,6 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2). \end{align*} 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, by the same reasoning we can decompose the paths - %\begin{align*} - % \P^{(n)}_b(\mathrm{NZ}^{(v,w)},A_1,A_2) R_{b,\mathrm{NZ}^{(v,w)},A_1,A_2} - % &\equiv \sum_{\substack{\xi\in\start{b}\\\xi \in \mathrm{NZ}^{(v,w)}\cap A_1\cap A_2}} \P^{(n)}[\xi] |\xi| \\ - % &= \sum_{\substack{\xi_1\in\start{b_1}\\\xi_1 \in \mathrm{NZ}^{(v,w)}\cap A_1}} - % \sum_{\substack{\xi_2\in\start{b_2}\\\xi_2 \in \mathrm{NZ}^{(v,w)}\cap A_2}} - % \P^{(n)}[\xi_1]\P^{(n)}[\xi_2] (|\xi_1| + |\xi_2|) \\ - % &= - % \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2) \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1) R_{b_1,\mathrm{NZ}^{(v,w)},A_1} \\ - % &\quad + - % \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)},A_1) \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2) R_{b_2,\mathrm{NZ}^{(v,w)},A_2} . - %\end{align*} - %Dividing by $\P^{(n)}_b(\mathrm{NZ}_{(v,w)},A_1,A_2)$ and using the first equality gives the desired result. \end{proof} \begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNew} @@ -440,7 +411,7 @@ The following lemma considers two vertices $v,w$ that are never ``crossed'' so t &= \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) + \P^{[w,v]}_{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