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

Changeset - e62754c9120c

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Tom Bannink - 8 years ago 2017-09-14 15:45:53
tom.bannink@cwi.nl

Add definition of local event

1 file changed with 11 insertions and 5 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -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}}
 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)
 	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}

0 comments (0 inline, 0 general)