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

Changeset - 0f7c68754475

Parent rev.

Child rev.

[Not reviewed]

0 1 0

Andras Gilyen - 8 years ago 2017-09-07 19:06:22
gilyen@clayoquot.swat.cwi.nl

nicer proof

1 file changed with 4 insertions and 4 deletions:

main.tex

0 comments (0 inline, 0 general)

main.tex

➞

Show inline comments

 \begin{definition}[Events conditioned on starting state] \label{def:conditionedevents}
     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$, define
     \begin{align*}
         \P^{(n)}_b(A) &= \P^{(n)}(A \;|\; \start{b}) %\\
         %R_{b,A} &= \mathbb{E}( \#resamples \;|\; A \; , \; \start{b})
     \end{align*}
-    Furthermore, for the Markov Chain on the finite chain, define
+    Furthermore, for $v\in[n]$ we define
     \begin{align*}
-        \P^{[n]}_{\partial=1}(A) &= \P^{[n]}(A \;|\; \text{boundary is initialized to }1)
+        \P^{[n]}_{b_v=1}(A) &= \P^{[n]}(A \;|\; v\text{ is initialized to }1),
     \end{align*}
-    where the boundary of $[n]$ is site $1$ and site $n$, and the boundary of $[a,b]$ are $a$ and $b$.
+    and we define similarly $\P^{[n]}_{b_v=b_w=1}(A)$ for $v,w\in[n]$.
 \end{definition}
 %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:visitingResamplings}
     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{align*}
 		\P^{(n)}(\mathrm{NZ}^{(v,w)}\cap A\cap B)
         &= \sum_{b\in\{0,1\}^n} \P^{(n)}_b(\mathrm{NZ}^{(v,w)}\cap A\cap B) \; \P^{(n)}(\start{b}) \\
         &= \sum_{b\in\{0,1\}^n}
             \P^{[v,w]}_{b|_{[v,w]}}(\mathrm{NZ}^{(v,w)}\cap A)
             \P^{[v,w]}(\start{b|_{[v+1,w-1]}})
             \\ &\qquad\qquad\quad
+            \\ &\qquad\qquad\quad\cdot
             \P^{[w,v]}_{b|_{[w,v]}}(\mathrm{NZ}^{(v,w)}\cap B)
             \P^{[w,v]}(\start{b|_{[w,v]}}) \\
         &= \left( \sum_{\substack{b_1\in\{0,1\}^{[v,w]}\\ b_v=b_w=1}}
             \P^{[v,w]}_{b_1}(\mathrm{NZ}^{(v,w)}\cap A)
             \P^{[v,w]}(\start{b_1}) \right)
             \\ &\qquad \cdot

0 comments (0 inline, 0 general)