diff --git a/main.tex b/main.tex index 6cf2e851f04da8964d15316dda774f132d7c905f..5c6414dbface5eab59263ce53252227058cd85a8 100644 --- a/main.tex +++ b/main.tex @@ -216,18 +216,23 @@ Clearly for any $\rho'$ we have that $\text{rank}(\rho' M_{(n)})\geq \text{rank}(\rho') + 1$. Another observation is, that all elements of $\rho'$ are divisible by $p^{\text{rank}(\rho')-n}$. We observe that for the initial $\rho$ we have that $\text{rank}(\rho)=n$, therefore $\text{rank}(\rho*(M_{(n)}^k))\geq n+k$, and so $\rho*(M_{(n)}^k)*\mathbbm{1}$ is obviously divisible by $p^{k}$. This implies that $a_k^{(n)}$ can be calculated by only looking at $\rho*(M_{(n)}^1)*\mathbbm{1}, \ldots, \rho*(M_{(n)}^k)*\mathbbm{1}$. +\newpage \section{Quasiprobability method} +Let us first introduce notation for paths of the Markov Chain +\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 $|\xi|$ the length of such a path, i.e. the number of resamples that happened, and by $\mathbb{P}[\xi]$ the probability associated to 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}$. +\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| \quad,\quad\text{where }|\xi|\text{ is the length of the path }\xi. + R_b(p) &= \sum_{\xi \in \paths{b}} \mathbb{P}[\xi] \cdot |\xi| \end{align*} -Here $\paths{b}$ denotes the set of all possible ways (paths) to arrive in the all-one state (denoted by $\mathbf{1}$) and we take the expected length of these paths. Note that if a path samples a $0$ then $\mathbb{P}[\xi]$ gains a factor $p$.\\ -We consider $R^{(n)}(p)$ as a power series in $p$ and show that many terms in (\ref{eq:originalsum}) cancel out if we only consider the series up to some finite order $p^k$.\\ +We consider $R^{(n)}(p)$ as a power series in $p$ and show that many terms in (\ref{eq:originalsum}) cancel out if we only consider the series up to some finite order $p^k$. Note that if a path samples a $0$ then $\mathbb{P}[\xi]$ gains a factor $p$.\\ To see this, we split the sum in (\ref{eq:originalsum}) into parts that will later cancel out. The initial probabilities $\rho_b$ contain a factor $p$ for every $0$ and a factor $(1-p)$ for every $1$. When expanding this product of $p$s and $(1-p)$s, we see that the $1$s contribute a factor $1$ and a factor $(-p)$ and the $0$s only give a factor $p$. Therefore we no longer consider bitstrings $b\in\{0,1\}^n$ but bitstrings $b\in\{0,1,1'\}^n$. We view this as follows: every site can have one of $\{0,1,1'\}$ with `probabilities' $p$, $1$ and $-p$ respectively. A configuration $b=101'1'101'$ now has probability $\rho_{b} = 1\cdot p\cdot(-p)\cdot(-p)\cdot 1\cdot p\cdot(-p) = -p^5$ in the starting state $\rho$. It should not be hard to see that we have \begin{align*} @@ -251,7 +256,7 @@ where $C(f)\in\{0,1,1'\}^n$ denotes a configuration with slots on the sites $C$ \begin{center} \includegraphics{diagram_gap.pdf} \end{center} - \caption{\label{fig:diametergap} A configuration $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 slots shown by the red dots. The dotted line at the top depicts the rest of the circle which may be much larger. The diameter of this configuration is $\diam{C}=9$ as shown and the largest gap of $C$ is $\mathrm{gap}(C)=2$. Note that we do not count the rest of the circle as a gap, we only consider gaps within the diameter of $C$.} + \caption{\label{fig:diametergap} A configuration $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 slots shown by the red dots. The dotted line at the top depicts the rest of the circle which may be much larger. The diameter of this configuration is $\diam{C}=9$ as shown and the largest gap of $C$ is $\mathrm{gap}(C)=2$. Note that we do not count the rest of the circle as a gap, we only consider gaps \emph{within} the diameter of $C$.} \end{figure} \begin{claim}[Strong cancellation claim] \label{claim:strongcancel} @@ -337,7 +342,9 @@ Here we prove claim \ref{claim:weakcancel}, the weaker version of the claim. We \begin{definition}[Path independence] \label{def:independence} We say two paths $\xi_i\in\paths{b_i}$ ($i=1,2$) of the Markov Chain are \emph{independent} if $\xi_1$ never resamples a site that was ever zero in $\xi_2$ and the other way around. It is allowed that $\xi_1$ resamples a $1$ to a $1$ that was also resampled from $1$ to $1$ by $\xi_2$ and vice versa. If the paths are not independent then we call the paths \emph{dependent}. \end{definition} -The key ingredient of the proof is the following claim: +\begin{definition}[Path independence - alternative] \label{def:independence2} + Equivalently, on the infinite line $\xi_1$ and $\xi_2$ are independent if there is a site `inbetween' them that was never zero in $\xi_1$ and never zero in $\xi_2$. On the circle $\xi_1$ and $\xi_2$ are independent if there are \emph{two} sites inbetween them that are never zero. +\end{definition} \begin{claim}[Sum of expectation values] \label{claim:expectationsum} When $b=b_1\land b_2\in\{0,1\}^n$ is a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes with $k$ $1$s inbetween the groups, then we have $R_b(p) = R_{b_1}(p) + R_{b_2}(p) + \mathcal{O}(p^{k})$ where $b_1$ and $b_2$ are the configurations where only one of the groups is present and the other group has been replaced by $1$s. To be precise, the sums agree up to and including order $p^{k-1}$. \end{claim} @@ -393,6 +400,21 @@ we can do the same with the second term and this proves the claim. \end{align*} where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$. +~ + +The proof of claim \ref{claim:expectationsum} also proves the following claim +\begin{claim}[Probability independence] \label{claim:pathindependence} + As in \ref{claim:expectationsum}, 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. Let $j_1$, $j_2$ be indices `inbetween' the groups (or only one index in case of the infinite line). Denote by $\mathrm{NZ}_j$ the event that site $j$ does not become zero before the Markov Chain terminates. Then we have + \begin{align*} + \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} |\;\text{start in }b] + = + \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} \;|\;\text{start in }b_1] + \; \cdot \; + \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} \;|\;\text{start in }b_2] + \end{align*} +up to any order in $p$. +\end{claim} + \newpage \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}} Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.