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

Changeset - a14984cd2c08

Parent rev.

Child rev.

[Not reviewed]

Merge

0 1 0

Andras Gilyen - 8 years ago 2017-09-08 17:10:16
gilyen@clayoquot.swat.cwi.nl

Incr.

1 file changed with 11 insertions and 31 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -52,25 +52,24 @@ @@
 \newcommand{\bOt}[1]{\widetilde{\mathcal O}\left(#1\right)}
 \newcommand{\bigO}[1]{\mathcal O\left(#1\right)}
 \newcommand{\Res}[1]{\#\mathrm{Res}\left(#1\right)}
 \newcommand{\QMAo}{\textsf{QMA$_1$}}
 \newcommand{\BQP}{\textsf{BQP}}
 \newcommand{\NP}{\textsf{NP}}
 \newcommand{\SharpP}{\textsf{\# P}}
 \newcommand{\diam}[1]{\mathcal{D}\left(#1\right)}
 \newcommand{\paths}[1]{\mathcal{P}\left(#1\to\mathbf{1}\right)}
 \newcommand{\start}[1]{\textsc{start}\left(#1\right)}
 \newcommand{\initone}[1]{\textsc{InitOne}\left(#1\right)}
 \newcommand{\patch}[1]{\textsc{Patch}\left(#1\right)}
 \newcommand{\patches}[1]{\textsc{Patches}\left(#1\right)}
 \newcommand{\maxgap}[1]{\mathrm{maxgap}\left(#1\right)}
 \newcommand{\gaps}[1]{#1_{\mathrm{gaps}}}
 \renewcommand{\P}{\mathbb{P}}
 \newcommand{\E}{\mathbb{E}}
 \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}}
@@ @@ -584,59 +583,40 @@ Questions: @@
 	\item Can we generalise the proof to other translationally invariant spaces, like the torus?
 	\item In view of this proof, can we better characterise $a_k^{(k+1)}$?
 	\item Why did Mario's and Tom's simulation show that for fixed $C$ the contribution coefficients have constant sign? Is it relevant for proving \ref{it:pos}-\ref{it:geq}?
 \end{itemize}
 	%I think the same arguments would translate to the torus and other translationally invariant spaces, so we could go higher dimensional as Mario suggested. Then I think one would need to replace $|S_{><}|$ by the minimal number $k$ such that there is a $C$ set for which $S\cup C$ is connected. I am not entirely sure how to generalise Lemma~\ref{lemma:probIndep} though, which has key importance in the present proof.
 \newpage
 \section{General graphs proof}
 We consider the following generalization of the Markov Chain.
 Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain.
+Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. We define a Markov Chain $\mathcal{M}_G$ as the following process: initialize every vertex of $G$ independently to 0 with probability $p$ and 1 with probability $1-p$. Then at each step, select a uniformly random vertex that has value $0$ and resample it and its neighbourhood, all of them independently with the same probability $p$. The Markov Chain terminates when all vertices have value $1$. We use $\P^{G}$ to denote probabilities associated to this Markov Chain and $\E^G$ to denote expectation values.
 \begin{definition}[Events] \label{def:events}
     Let $S\subseteq V$ be any subset of vertices.
     Define $\Z{S}$ as the event that \emph{all} vertices in $S$ become zero at any point in time before the Markov Chain terminates.
     Define $\NZ{S}$ as the event that \emph{none} of the vertices in $S$ become zero at any point in time before the Markov Chain terminates.
     Define $\initone{S}$ as the event that all vertices in $S$ \emph{initially} get assigned the value 1, and define for any event $A$:
     \begin{align*}
         \P^{G}_S(A) &= \P^{G}(A \;\mid\; \initone{S})
     \end{align*}
     \begin{itemize}
         \item Define $\Z{S}$ as the event that \emph{all} vertices in $S$ become zero at any point in time before the Markov Chain terminates.
         \item Define $\NZ{S}$ as the event that \emph{none} of the vertices in $S$ become zero at any point in time before the Markov Chain terminates.
         \item Define for any event $A$:
             \begin{align*}
                 \P^{G}_S(A) &= \P^{G}(A \mid \text{All vertices in $S$ get initialized to }1)
             \end{align*}
         \item Boundary $\partial$ \todo{}
         \item $d$-Neighbourhood $B(S;d)$ \todo{}
     \end{itemize}
 \end{definition}
 $\NZ{S}$
 $\Z{S}$
 patch
 $B(S;d)$
 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 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:visitingResamplingsGen}
     Denote by $\mathrm{Z}^{(v)}$ the event that site $v$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}^{(v)}$, i.e. the event that site $v$ does \emph{not} become zero before it terminates. Furthermore define $\mathrm{NZ}^{(v,w)} := \mathrm{NZ}^{(v)} \cap \mathrm{NZ}^{(w)}$, i.e. the event that \emph{both} $v$ and $w$ do not become zero before termination.
 \end{definition}
 %\begin{figure}
 %	\begin{center}
 %    	\includegraphics{diagram_groups.pdf}
 %    \end{center}
 %    \caption{\label{fig:separatedgroups} Illustration of setup of Lemma \ref{lemma:eventindependenceGen}. 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}[7]{r}{0.25\textwidth} % The first [] argument is number of lines that are narrowed
     \centering
     \includegraphics{diagram_groups.pdf}
     \caption{\label{fig:separatedgroupsGen} Lemma \ref{lemma:eventindependenceGen}.}
 \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:eventindependenceGen}
     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:separatedgroupsGen}. 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)
         &=
         \P^{(n)}_{b_1}(\mathrm{NZ}^{(v,w)}, A_1)

0 comments (0 inline, 0 general)