Changeset - 71d7c8f3b5ef
Parent rev.
Child rev.
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-05-30 16:45:55
tom.bannink@cwi.nl
Add claim on conditional independence
1 file changed with 74 insertions and 11 deletions:
main.tex
74
11
0 comments (0 inline, 0 general)
main.tex
➞
Show inline comments
 
@@ -381,66 +381,129 @@ where last sum only contains only terms of order $p^{k}$ or higher. Now for the
 
where the sum over independent paths could be empty for certain $\xi_1$. Now we replace this last sum by a sum over \emph{all} paths $\xi_2\in\paths{b_2}$. This will change the sum but only for terms where $\xi_1,\xi_2$ are dependent. For those terms we already know that $\mathbb{P}[\xi_1]\mathbb{P}[\xi_2]$ contains a factor $p^k$ and hence we have
 
\begin{align*}
 
    \sum_{\mathclap{\substack{\xi_{1,2}\in\paths{b_{1,2}}\\ \mathrm{independent}}}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1|
 
    &= \sum_{\xi_1\in\paths{b_1}} \sum_{\xi_2\in\paths{b_2}} \mathbb{P}[\xi_2]\mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\
 
    &= \sum_{\xi_1\in\paths{b_1}} \mathbb{P}[\xi_1]|\xi_1| + \mathcal{O}(p^k) \\
 
    &= R_{b_1} + \mathcal{O}(p^k)
 
\end{align*}
 
we can do the same with the second term and this proves the claim.
 
\end{proof}
 

			




	
	
	
		
 
~\\

			




	
	
	
		
 
\textbf{Proof of claim \ref{claim:weakcancel}}: We can assume $C$ consists of a group on the left with $l$ slots and a group on the right with $r$ slots (so $r+l=|C|$), with a gap of size $k=\mathrm{gap}(C)$ between these groups. Then on the left we have strings in $\{0,1'\}^l$ as possibilities and on the right we have strings in $\{0,1'\}^r$. The combined configuration can be described by strings $f=(a,b)\in\{0,1'\}^{l+r}$. The initial probability of such a state $C(a,b)$ is $\rho_{C(a,b)} = (-1)^{|a|+|b|} p^{r+l}$ and by claim \ref{claim:expectationsum} we know $R_{C(a,b)} = R_{C(a)} + R_{C(b)} + \mathcal{O}(p^k)$ where $C(a)$ indicates that only the left slots have been filled by $a$ and the other slots are filled with $1$s. The total contribution of these configurations is therefore

			




	
	
	
		
 
\begin{align*}

			




	
	
	
		
 
    \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}

			




	
	
	
		
 
    &= \sum_{a\in\{0,1'\}^l} \sum_{b\in\{0,1'\}^r} (-1)^{|a|+|b|}p^{r+l} \left( R_{C(a)} + R_{C(b)} + \mathcal{O}(p^k) \right) \\

			




	
	
	
		
 
    &=\;\;\; p^{r+l}\sum_{a\in\{0,1'\}^l} (-1)^{|a|} R_{C(a)} \sum_{b\in\{0,1'\}^r} (-1)^{|b|} \\

			




	
	
	
		
 
    &\quad + p^{r+l}\sum_{b\in\{0,1'\}^r} (-1)^{|b|} R_{C(b)} \sum_{a\in\{0,1'\}^l} (-1)^{|a|}

			




	
	
	
		
 
        + \mathcal{O}(p^{r+l+k})\\

			




	
	
	
		
 
    &= 0 + \mathcal{O}(p^{|C|+k})

			




	
	
	
		
 
\end{align*}

			




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

			




	
	
	
		
 
    Let us interpret $[n]$ as the vertices of a length-$n$ cycle, and interpret operations on vertices mod $n$ s.t. $n+1\equiv 1$ and $1-1\equiv n$.

			




	
	
	
		
 
    %\begin{definition}[Resample sequences]

			




	
	
	
		
 
    %	A sequence of indices $(r_\ell)=(r_1,r_2,\ldots,r_k)\in[n]^k$ is called resample sequence if our procedure performs $k$ consequtive resampling, where the first resampling of the procedure resamples around the mid point $r_1$ the second around $r_2$ and so on. Let $RS(k)$ the denote the set of length $k$ resample sequences, and let $RS=\cup_{k\in\mathbb{N}}RS(k)$.

			




	
	
	
		
 
    %\end{definition}

			




	
	
	
		
 
    %\begin{definition}[Constrained resample sequence]\label{def:constrainedRes}

			




	
	
	
		
 
    %	Let $C\subseteq[n]$ denote a slot configuration, and let $a\in\{\text{res},\neg\text{res}\}^{n-|C|}$, where the elements correspond to labels ``resampled" vs. ``not resampled" respectively. 

			




	
	
	
		
 
    %	For $j\in[n-|C|]$ let $i_j$ denote the $j$-th index in $[n]\setminus C$.

			




	
	
	
		
 
    %	We define the set $A^{(C,a)}\subseteq RS$ as the set of resample sequences $(r_\ell)$ such that for all $j$ which has $a_j=\text{res}$ we have that $i_j$ appears in $(r_\ell)$ but for $j'$-s which have $a_{j'}=\neg\text{res}$ we have that $i_{j'}$ never appears in $(r_\ell)$. 

			




	
	
	
		
 
    %\end{definition}    

			




	
	
	
		
 
    \begin{definition}[Conditional expected number of resamples]

			




	
	
	
		
 
    	For a slot configuration $C\subseteq[n]$ and $a\in\{\!\text{ever},\text{ never}\}^{n-|C|}$ we define the event $A^{(C,a)}:=\bigwedge_{j\in[n-|C|]}\{i_j\text{ has }a_j\text{ become }0\text{ before reaching }\mathbf{1}\}$,

			




	
	
	
		
 
    	where $i_j$ is the $j$-th vertex of $[n]\setminus C$.

			




	
	
	
		
 
    	Then we also define

			




	
	
	
		
 
    	$$R^{(C,a)}_b:=\mathbb{E}[\#\{\text{resamplings when started from inital state }b\}|A^{(C,a)}].$$

			




	
	
	
		
 
    \end{definition}     

			




	
	
	
		
 
    

			




	
	
	
		
 
    As in Mario's proof I use the observation that 

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
    R^{(n)}(p) &= \frac{1}{n}\sum_{b\in\{0,1,1'\}^{n}} \rho_b \; R_{\bar{b}}(p)\\

			




	
	
	
		
 
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)}(p)\\

			




	
	
	
		
 
    &= \frac{1}{n}\sum_{C\subseteq [n]}\sum_{f\in\{0,1'\}^{|C|}}\sum_{a\in\{\!\text{ever},\text{ never}\}^{n-|C|}} \rho_{C(f)} R^{{(C,a)}}_{C(f)}(p)P_{C(f)}(A^{(C,a)})\\

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: kalli-3626972
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support