From ec61b8b5528045dd7a1fe82939d1911c11e74526 2017-09-08 14:32:50
From: Tom Bannink <tom.bannink@cwi.nl>
Date: 2017-09-08 14:32:50
Subject: [PATCH] Add event defs

---

diff --git a/main.tex b/main.tex
index 229303ac5f091f14e934a338256902a48279a050..45372e8fec3b5870badfa21c2e09674719d91a34 100644
--- a/main.tex
+++ b/main.tex
@@ -61,6 +61,7 @@
 \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}}
@@ -593,14 +594,13 @@ 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}