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

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

0 comments (0 inline, 0 general)