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

Changeset - ec61b8b55280

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Tom Bannink - 8 years ago 2017-09-08 14:32:50
tom.bannink@cwi.nl

Add event defs

1 file changed with 6 insertions and 6 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

@@ @@ -52,24 +52,25 @@ @@
 \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{\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{}
@@ @@ -584,32 +585,31 @@ Questions: @@
 \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.
 \begin{definition}[Events] \label{def:events}
     For any subset $S\subseteq V$ of vertices.
     For any state $b\in\{0,1\}^n$, define $\start{b}$ as the event that the starting state of the chain is the state $b$. For any event $A$ and any $v\in[n]$, define
     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^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) \\
         \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1) \\
         \P^{[n]}_{b_v=b_w=1}(A) &= \P^{[n]}(A \;|\; v\text{ and }w\text{ are initialized to }1) ,
         \P^{G}_S(A) &= \P^{G}(A \;\mid\; \initone{S})
     \end{align*}
     The last two probabilities are not conditioned on any other bits of the starting state.
 \end{definition}
 $\NZ{S}$
 $\Z{S}$
 patch
 $B(S;d)$

0 comments (0 inline, 0 general)