From 71d7c8f3b5ef4dee61821947b12a6fe3f118ada1 2017-05-30 16:45:55 From: Tom Bannink Date: 2017-05-30 16:45:55 Subject: [PATCH] Add claim on conditional independence --- diff --git a/main.tex b/main.tex index b826b535b105828b8fda669d5ff0bf40f744870d..6119dd84d3ca3a2ae4fca124879e10d5963820f6 100644 --- a/main.tex +++ b/main.tex @@ -402,24 +402,87 @@ where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$. ~ +It is useful to introduce some new notation: for any event $A$ (where an event is a set of paths), define +\begin{align*} + \mathbb{P}_b(A) &= \mathbb{P}(A \;|\; \text{start in }b) \\ + R_{b,A} &= \mathbb{E}( \#resamples \;|\; A\;,\; \text{start in }b) +\end{align*} +Denote by $\mathrm{Z}_j$ the event that site $j$ becomes zero at any point in time before the Markov Chain terminates. Denote the complement by $\mathrm{NZ}_j$, i.e. the event that site $j$ does \emph{not} become zero before it terminates. + The proof of claim \ref{claim:expectationsum} also proves the following claim -\begin{claim}[Probability independence] \label{claim:pathindependence} - As in \ref{claim:expectationsum}, let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes. Let $j_1$, $j_2$ be indices `inbetween' the groups (or only one index in case of the infinite line). Denote by $\mathrm{NZ}_j$ the event that site $j$ does not become zero before the Markov Chain terminates. Then we have +\begin{claim}[Conditional independence] \label{claim:eventindependence} + As in \ref{claim:expectationsum}, let $b=b_1\land b_2\in\{0,1\}^n$ be a state with two groups ($b_1\lor b_2 = 1^n$) of zeroes. Let $j_1$, $j_2$ be indices `inbetween' the groups (or only one index in case of the infinite line). Then we have \begin{align*} - \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} |\;\text{start in }b] - = - \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} \;|\;\text{start in }b_1] + \mathbb{P}_b(\mathrm{NZ}_j) + &= + \mathbb{P}_{b_1}(\mathrm{NZ}_j) \; \cdot \; - \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} \;|\;\text{start in }b_2] + \mathbb{P}_{b_2}(\mathrm{NZ}_j) \\ + R_{b,\mathrm{NZ}_j} + &= + R_{b_1,\mathrm{NZ}_j} + \; + \; + R_{b_2,\mathrm{NZ}_j} \end{align*} -up to any order in $p$. + up to any order in $p$. Furthermore the equalities also hold when $\mathrm{NZ}_j$ is replaced by any subset $A\subseteq\mathrm{NZ}_j$. \end{claim} -Since the left hand side is defined as +\begin{proof} + Note that any path $\xi\in\paths{b} \cap \mathrm{NZ}_j$ can be split into paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}_j$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}_j$ and by the same reasoning as in the proof of claim \ref{claim:expectationsum}, we obtain + \begin{align*} + \mathbb{P}_b(\mathrm{NZ}_j) + = \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi] + &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}} + \sum_{\substack{\xi_2\in\paths{b_1}\\\xi_2 \in \mathrm{NZ}_j}} + \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\ + &= + \mathbb{P}_{b_1}(\mathrm{NZ}_j) + \; \cdot \; + \mathbb{P}_{b_2}(\mathrm{NZ}_j). + \end{align*} + For the second equality, note that again by the same reasoning as in the proof of claim \ref{claim:expectationsum} we have + \begin{align*} + \mathbb{P}_b(\mathrm{NZ}_j) R_{b,\mathrm{NZ}_j} + := \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}_j}} \mathbb{P}[\xi] |\xi| + &= \sum_{\substack{\xi_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}_j}} + \sum_{\substack{\xi_2\in\paths{b_2}\\\xi_2 \in \mathrm{NZ}_j}} + \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\ + &= + \mathbb{P}_{b_2}(\mathrm{NZ}_j) \mathbb{P}_{b_1}(\mathrm{NZ}_j) R_{b_1,\mathrm{NZ}_j} + \; + \; + \mathbb{P}_{b_1}(\mathrm{NZ}_j) \mathbb{P}_{b_2}(\mathrm{NZ}_j) R_{b_2,\mathrm{NZ}_j} . + \end{align*} + Dividing by $\mathbb{P}_b(\mathrm{NZ}_j)$ and using the first equality gives the desired result. +\end{proof} + +~ + +TEST: Although a proof of claim \ref{claim:expectationsum} was already given, I'm trying to prove it in an alternate way using claim \ref{claim:eventindependence}.\\ +Assume that $b_1$ ranges up to site $0$, the gap ranges from sites $1,...,k$ and $b_2$ ranges from site $k+1$ and onwards. For $j=1,...,k$ define the partial-zero event $\mathrm{PZ}_j = \mathrm{Z}_1 \cap \mathrm{Z}_2 \cap ... \cap \mathrm{Z}_{j-1} \cap \mathrm{NZ}_j$ i.e. the first $j-1$ sites of the gap become zero and site $j$ does not become zero. Also define the all-zero event $\mathrm{AZ} = \mathrm{Z}_1 \cap ... \cap \mathrm{Z}_k$, where all sites of the gap become zero. Note that these events partition the space, so we have for all $b$ that $\sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) = 1 - \mathbb{P}_b(\mathrm{AZ}) = 1 - \mathcal{O}(p^k)$. + +Furthermore, if site $j$ becomes zero from $b_1$ it means all sites to the left of $j$ become zero as well. Similarly, from $b_2$ it implies all the sites to the right of $j$ become zero. +Because of that, we have +\begin{align*} + \mathbb{P}_{b_1}(\mathrm{PZ}_j) &= \mathbb{P}_{b_1}(\mathrm{Z}_{j-1} \cap \mathrm{NZ}_j) = \mathcal{O}(p^{j-1}) \\ + \mathbb{P}_{b_2}(\mathrm{PZ}_j) &= \mathbb{P}_{b_2}(\mathrm{NZ}_j) = 1 - \mathbb{P}_{b_2}(\mathrm{Z}_j) = 1 - \mathcal{O}(p^{k-j+1}) +\end{align*} +Now observe that \begin{align*} - \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} |\;\text{start in }b] - = \sum_{\substack{\xi\in\paths{b}\\j_1,j_2 \text{ not 0 in } \xi}} \mathbb{P}[\xi] + R_b &= \sum_{j=1}^k \mathbb{P}_b(\mathrm{PZ}_j) R_{b,\mathrm{PZ}_j} + \mathbb{P}_b(\mathrm{AZ}) R_{b,\mathrm{AZ}} \\ + &= \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{PZ}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} + + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{PZ}_j) R_{b_2,\mathrm{PZ}_j} + + \mathcal{O}(p^k) \\ + &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} + - \sum_{j=1}^k \mathbb{P}_{b_2}(\mathrm{Z}_j)\mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} + + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{PZ}_j) R_{b_2,\mathrm{PZ}_j} + + \mathcal{O}(p^k) \\ + &= \sum_{j=1}^k \mathbb{P}_{b_{1}}(\mathrm{PZ}_j) R_{b_1,\mathrm{PZ}_j} + + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{PZ}_j) R_{b_2,\mathrm{PZ}_j} + + \mathcal{O}(p^k) \\ + &= R_{b_1} + + \sum_{j=1}^k \mathbb{P}_{b_1}(\mathrm{PZ}_j)\mathbb{P}_{b_{2}}(\mathrm{PZ}_j) R_{b_2,\mathrm{PZ}_j} + + \mathcal{O}(p^k) \\ + &= R_{b_1} + R_{b_2} + \mathcal{O}(p^k) \end{align*} -we see that all such paths $\xi$ can be split into paths $\xi_1\in\paths{b_1}$ and $\xi_2\in\paths{b_2}$ and by the same reasoning as in the proof of claim \ref{claim:expectationsum}, we obtain the right hand side. \newpage \subsection{Sketch of the (false) proof of the linear bound \ref{it:const}}