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

Changeset - b554f1fbc443

Parent rev.

Child rev.

[Not reviewed]

0 1 0

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

Incr.

1 file changed with 5 insertions and 3 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -53,24 +53,26 @@ @@
 \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}}
 \long\def\ignore#1{}
             \P^{[v,w]}(\start{b_1}) \right)
             \\ &\qquad \cdot
            \left( \sum_{b_2\in\{0,1\}^{[w,v]}}
             \P^{[w,v]}_{b_2}(\mathrm{NZ}^{(v,w)}\cap B)
             \P^{[w,v]}(\start{b_2}) \right) \\
         &=  \P^{[v,w]}_{b_v=b_w=1}(\mathrm{NZ}^{(v,w)}\cap A) \cdot
             \P^{[w,v]}(\mathrm{NZ}^{(v,w)}\cap B)
     \end{align*}
     The second equality follows in a similar way.
 \end{proof}
 	\begin{definition}[Connected patches]
-		Let $P\subseteq V$ be a connected component of $G$. We say that $P$ is a patch of a particular run of the process if $P$ is a maximal connected component of the vertices that have ever become $0$ before termination. We denote the set of patches of a run by $\mathcal{P}$. For a patch $P$ let $P\in \mathcal{P}$ denote the event that one of the patches is equal to $P$.
+		Let $P\subseteq V$ be a connected component of $G$. We say that $P$ is a patch of a particular run of the process if $P$ is a maximal connected component of the vertices that have ever become $0$ before termination. We denote the set of patches of a run by $\mathcal{P}$. For a patch $P$ let $\patch{P}$ denote the event that one of the patches is equal to $P$.
 		In other words
 		\begin{align*}
-		P\in\mathcal{P} := \NZ{\overline{\partial}P} \cap \Z{P}.
+		\patch{P} := \NZ{\overline{\partial}P} \cap \Z{P}.
 		\end{align*}
-		For $\mathcal{I}'\subseteq 2^{2^V}$ a set of patches we denote by $\mathcal{P}'\in \mathcal{P}$ the event that $\mathcal{P}'$ is a subset of the patches, i.e.,
+		For a set of patches $\mathcal{P}$ 	</i>
 		\begin{align*}
 			\mathcal{P}'\in \mathcal{P} := \bigcup_{P\in \mathcal{P}'}\NZ{\overline{\partial}P} \cap \Z{P}.
 		\end{align*}
 	\end{definition}
 	We are often going to use the observation that we can partition the event $\Z{v}$ using patches:
 	\begin{align*}
 	\Z{v} = \dot\bigcup_{P\text{ patch } : v\in P} (P\in\mathcal{P})
 	\end{align*}
 The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.
 \begin{lemma}\label{lemma:probIndepNewGen}

0 comments (0 inline, 0 general)