From e62754c9120c2b111fdad5bdd77173503343c940 2017-09-14 15:45:53
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-09-14 15:45:53
Subject: [PATCH] Add definition of local event

---

diff --git a/main.tex b/main.tex
index c5a999c027c22f6a88457f807704a9da737f00b0..c4a748c6f3e5784d0a4ce9a8092c864313d207da 100644
--- a/main.tex
+++ b/main.tex
@@ -51,7 +51,7 @@
 \def\im{\mathrm{im}}
 \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{\Res}[1]{\#\textsc{Res}\left(#1\right)}
 
 \newcommand{\QMAo}{\textsf{QMA$_1$}}
 \newcommand{\BQP}{\textsf{BQP}}
@@ -257,10 +257,16 @@ We consider the following generalization of the Markov Chain.
 Let $G=(V,E)$ be an undirected 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 and notation] \label{def:events}
-    Let $G=(V,E)$ be a graph. Let $S\subseteq V$ be any subset of vertices.
+    Let $G=(V,E)$ be a graph. Let $S\subseteq V$ be any subset of vertices, and let $v\in V$ be any vertex.
     \begin{itemize}
         \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 $\Z{S}$ as the complement of $\NZ{S}$, i.e. the event that \emph{there exists} a vertex in $S$ that becomes zero at some point in time before the Markov Chain terminates.
+        \item Let $\Res{v}$ be the number of times that $v$ was picked as a center of resampling.
+        \item We say an event $A$ is \emph{local} on the vertex set $S$ if it is in the sigma algebra generated by the events
+            \begin{align*}
+                \NZ{v} \; , \; \Z{v}\cap(\Res{v}=0) \; , \; (\Res{v} = k)
+            \end{align*}
+            for all $v\in S$ and $1\leq k \leq \infty$.
         \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)
@@ -422,9 +428,9 @@ The intuition of the following lemma is that if two sites have distance $d$ in t
 	Now we use the Splitting lemma~\ref{lemma:splitting} to show that for all $i\in[d]$
 	\begin{align}
 		\P^G(A_{i}^X)
-		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)}) \tag{by Lemma~\ref{lemma:splitting}}\\
-		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \left(\P^{G\setminus Y\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1-i}}\right) \tag{by induction}\\
-		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus Y\setminus B(X,i-1)}(X,i)(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1}} \tag{by equation \eqref{eq:AXorder}}\\
+		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus B(X,i-1)}(\NZ{\overline{\partial}(X,i)}) \tag{by Lemma~\ref{lemma:splitting}}\\
+		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \left(\P^{G\setminus Y\setminus B(X,i-1)}(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1-i}}\right) \tag{by induction}\\
+		&=\P^{G\cap B(X,i)}_{\overline{\partial}(X,i)}(A_{i}^X)\cdot \P^{G\setminus Y\setminus B(X,i-1)}(\NZ{\overline{\partial}(X,i)})+\bigO{p^{d+1}} \tag{by equation \eqref{eq:AXorder}}\\
 		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d+1}} \tag{by Lemma~\ref{lemma:splitting}}\\
 		&=\P^{G\setminus Y}(A_{i}^X)+\bigO{p^{d(Y,Y)}}. \label{eq:indStep}
 	\end{align}