Changeset - a14984cd2c08
[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
11
31
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -61,7 +61,6 @@
 
\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)}
 
@@ -593,41 +592,22 @@ Questions:
 

	
 
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}
0 comments (0 inline, 0 general)