Changeset - b09c769c096e
Parent rev.
Child rev.
[Not reviewed]
0 1 2
Tom Bannink - 8 years ago 2017-09-06 14:16:20
tom.bannink@cwi.nl
Add better explanation of independence claim
3 files changed with 145 insertions and 45 deletions:
diagram_paths2.pdf
bin+new file
diagram_paths2.tex
107
main.tex
38
45
0 comments (0 inline, 0 general)
diagram_paths2.pdf
➞
Show inline comments
 
new file 100644
 
binary diff not shown
diagram_paths2.tex
➞
Show inline comments
 
new file 100644
 
\documentclass{standalone}
 
\usepackage[T1]{fontenc}
 
\usepackage{amsmath}
 
\usepackage{amsfonts}
 
\usepackage{parskip}
 
\usepackage{marvosym} %Lightning symbol
 
\usepackage[usenames,dvipsnames]{color}
 
\usepackage[hidelinks]{hyperref}
 
\renewcommand*{\familydefault}{\sfdefault}
 

			




	
	
	
		
 
\usepackage{bbm} %For \mathbbm{1}

			




	
	
	
		
 
%\usepackage{bbold}

			




	
	
	
		
 
\usepackage{tikz}

			




	
	
	
		
 

			




	
	
	
		
 
\begin{document}

			




	
	
	
		
 

			




	
	
	
		
 
\begin{tikzpicture}

			




	
	
	
		
 
    \def\height{4};

			




	
	
	
		
 
    \draw[step=1cm,gray,dotted] (-0.9,-0.9) grid (8.9,\height+0.9);

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % Red line through grid

			




	
	
	
		
 
    %

			




	
	
	
		
 
    \draw [line width=3.0,red] (0,0) -- (0,1) -- (1,1) -- (2,1) -- (2,2);

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % Arrows of the grid

			




	
	
	
		
 
    %

			




	
	
	
		
 
    \foreach \x in {0,...,7} {

			




	
	
	
		
 
        \foreach \y in {1,...,\height} {

			




	
	
	
		
 
            \draw[->] (\x,\y-1) -- (\x+0.9,\y-1);

			




	
	
	
		
 
            \draw[->] (\x,\y-1) -- (\x,\y-1+0.9);

			




	
	
	
		
 
        }

			




	
	
	
		
 
        \draw [->] (\x,\height) -- (\x+0.9,\height);

			




	
	
	
		
 
    }

			




	
	
	
		
 
    \foreach \y in {1,...,\height} %somehow the loop cant go to '\height-1'

			




	
	
	
		
 
        \draw [->] (8,\y-1) -- (8,\y-1+0.9); % so we fix it like this with '\y-1'

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % Move labels

			




	
	
	
		
 
    %

			




	
	
	
		
 
    \foreach \y in {1,...,\height} {

			




	
	
	
		
 
        \draw (-1, \y - 0.5) node {$(z_\y',s_\y',r_\y')$};

			




	
	
	
		
 
    }

			




	
	
	
		
 
    \foreach \x in {1,...,8} {

			




	
	
	
		
 
        \draw (\x-0.6, -1.4) node[rotate=70] {$(z_\x,s_\x,r_\x)$};

			




	
	
	
		
 
    }

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % bitstring labels

			




	
	
	
		
 
    %

			




	
	
	
		
 

			




	
	
	
		
 
    \draw(-0.1,-0.4) node {$b_1\land b_2$};

			




	
	
	
		
 
    \draw(8.2,-0.4) node {$\mathbf{1} \land b_2$};

			




	
	
	
		
 
    \draw (-0.2,\height+0.3) node {$b_1\land\mathbf{1}$};

			




	
	
	
		
 
    \draw (8.2,\height+0.3) node {$\mathbf{1}$};

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % -> steps of xi

			




	
	
	
		
 
    %

			




	
	
	
		
 

			




	
	
	
		
 
    \draw (4,-2.5) node {$\to$ steps of $\xi_1$};

			




	
	
	
		
 
    \node[rotate=90,anchor=south,xshift=2cm,yshift=1.9cm] {$\to$ steps of $\xi_2$};

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % (Red) circles

			




	
	
	
		
 
    %

			




	
	
	
		
 

			




	
	
	
		
 
    \draw[fill,red] (0,0) circle (0.08);

			




	
	
	
		
 
    \draw[fill    ] (8,0) circle (0.05);

			




	
	
	
		
 
    \draw[fill    ] (0,\height) circle (0.05);

			




	
	
	
		
 
    \draw[fill,red] (8,\height) circle (0.08);

			




	
	
	
		
 

			




	
	
	
		
 
    %

			




	
	
	
		
 
    % Probability labels

			




	
	
	
		
 
    %

			




	
	
	
		
 

			




	
	
	
		
 
    \def\x{6};

			




	
	
	
		
 
    \def\y{3};

			




	
	
	
		
 
    \draw[fill,black] (\x,\y) circle (0.07);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x+0.23,\y-0.26) rectangle +(0.5,0.5);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x-0.55,\y+0.26) rectangle +(1.1,0.5);

			




	
	
	
		
 
    \draw (\x+0.5,\y) node {$p_{ij}$};

			




	
	
	
		
 
    \draw (\x,\y+0.5) node {$1-p_{ij}$};

			




	
	
	
		
 

			




	
	
	
		
 
    \def\x{2};

			




	
	
	
		
 
    \def\y{1};

			




	
	
	
		
 
    \draw[fill,black] (\x,\y) circle (0.07);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x+0.12,\y-0.26) rectangle +(0.7,0.5);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x-0.75,\y+0.26) rectangle +(1.5,0.5);

			




	
	
	
		
 
    \draw (\x+0.5,\y) node {$p_{3,2}$};

			




	
	
	
		
 
    \draw (\x,\y+0.5) node {$1-p_{3,2}$};

			




	
	
	
		
 

			




	
	
	
		
 
    \def\x{8};

			




	
	
	
		
 
    \def\y{1};

			




	
	
	
		
 
    \draw[fill,black] (\x,\y) circle (0.07);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x-0.25,\y+0.26) rectangle +(0.5,0.5);

			




	
	
	
		
 
    \draw (\x,\y+0.5) node {$1$};

			




	
	
	
		
 

			




	
	
	
		
 
    \def\x{3};

			




	
	
	
		
 
    \def\y{\height};

			




	
	
	
		
 
    \draw[fill,black] (\x,\y) circle (0.07);

			




	
	
	
		
 
    \draw[fill=white,draw=black] (\x+0.25,\y-0.25) rectangle +(0.5,0.5);

			




	
	
	
		
 
    \draw (\x+0.5,\y) node {$1$};

			




	
	
	
		
 
\end{tikzpicture}

			




	
	
	
		
 
\end{document}

			




        

    


    
    

    

        

                

                    main.tex
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -474,64 +474,57 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha

			




	
	
	
		
 
                &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi|}} \P(r_{|\xi|}) .

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    To construct $\xi_1$ and $\xi_2$, start with empty sequences $\xi_1,\xi_2$ and for each step $(z_i,s_i,r_i)$ in $\xi$ do the following: if $s_i$ is ``on the $b_1$ side of $j_1,j_2$'' then add $(z^{(1)}_i,s_i,r_i)$ to $\xi_1$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add $(z^{(2)}_i,s_i,r_i)$ to $\xi_2$. Here $z^{(1)}_i$ is the number of zeroes that were on the $b_1$ side and $z^{(2)}_i$ is the number of zeroes on the $b_2$ side so we have $z_i = z^{(1)}_i + z^{(2)}_i$.

			




	
	
	
		
 
    Let the resulting paths be

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\

			




	
	
	
		
 
        \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right)

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    %Let the resulting paths be

			




	
	
	
		
 
    %\begin{align*}

			




	
	
	
		
 
    %    \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\

			




	
	
	
		
 
    %    \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right)

			




	
	
	
		
 
    %\end{align*}

			




	
	
	
		
 
    Now $\xi_1$ is a valid (terminating) path from $b_1$ to $\mathbf{1}$, because in the original path $\xi$, all zeroes ``on the $b_1$ side'' have been resampled by resamplings ``on the $b_1$ side''. Since the sites $j_1,j_2$ inbetween never become zero, there can not be any zero ``on the $b_1$ side'' that was resampled by a resampling ``on the $b_2$ side''.

			




	
	
	
		
 
    The probability of $\xi_1$, started from $b_1$, is given by

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P_{b_1}[\xi_1] &= \P(\text{choose }s_{a_1}) \P(r_{a_1}) \P(\text{choose }s_{a_2}) \P(r_{a_2}) \cdots \P(\text{choose }s_{a_{|\xi|}}) \P(r_{a_{|\xi|}}) \\

			




	
	
	
		
 
                &= \frac{1}{z^{(1)}_{a_1}} \P(r_{a_1}) \frac{1}{z^{(1)}_{a_2}} \P(r_{a_2}) \cdots \frac{1}{z^{(1)}_{a_{|\xi|}}} \P(r_{a_{|\xi|}})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    and similar for $\xi_2$.

			




	
	
	
		
 
    Vice versa, all paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$. The following diagram illustrates all possible interleavings:

			




	
	
	
		
 
    \begin{center}

			




	
	
	
		
 
        \includegraphics{diagram_paths.pdf}

			




	
	
	
		
 
    \end{center}

			




	
	
	
		
 
    A particular interleaving is a path through the above grid. So for a fixed $\xi_1,\xi_2$ there are $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ possible interleavings $\xi$, and vice versa there are $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ that decompose into the same $\xi_1$ and $\xi_2$. For a fixed $\xi_1,\xi_2$ we now show the following:

			




	
	
	
		
 
    Vice versa, any two paths $\xi_1\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_2\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ also induce a path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$.

			




	
	
	
		
 
    For a fixed $\xi_1,\xi_2$ we will now show the following:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \sum_{\substack{\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P_b[\xi] &=

			




	
	
	
		
 
        \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2] \\

			




	
	
	
		
 
        &= \P_{b_1}[\xi_1] \cdot \P_{b_2}[\xi_2]

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    This is best explained by an example. We have, for an example interleaving:

			




	
	
	
		
 
    where both sums are over $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ terms.

			




	
	
	
		
 
    This is best explained by an example. Lets consider the following fixed $\xi_1,\xi_2$ and an example interleaving where we choose steps from $\xi_2,\xi_1,\xi_1,\xi_2,\cdots$:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \xi_1 &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots  \right) \\

			




	
	
	
		
 
        \xi_2 &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots  \right) \\

			




	
	
	
		
 
        \xi   &= \left( (z_1 + z_1', s_1', r_1'), (z_1+z_2', s_1, r_1), (z_2+z_2', s_2, r_2), (z_3+z_2', s_2', r_2'), \cdots \right)

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    The probability of $\xi_1$, started from $b_1$, is given by

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \xi   &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4), \cdots \right) \\

			




	
	
	
		
 
        \xi_1 &= \left( (z^{(1)}_1, s_1, r_1), \phantom{(z^{(2)}_2, s_2, r_2), (z^{(1)}_3, s_3, r_3),} (z^{(1)}_4, s_4, r_4),\cdots  \right) \\

			




	
	
	
		
 
        \xi_2 &= \left( \phantom{(z^{(1)}_1, s_1, r_1),} (z^{(2)}_2, s_2, r_2), (z^{(2)}_3, s_3, r_3),\phantom{(z^{(2)}_4, s_4, r_4), } \cdots \right)

			




	
	
	
		
 
        \P_{b_1}[\xi_1] &= \P(\text{choose }s_1) \P(r_{a_1}) \P(\text{choose }s_2) \P(r_{a_2}) \cdots \P(\text{choose }s_{|\xi_1|}) \P(r_{|\xi_1|}) \\

			




	
	
	
		
 
                &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi_1|}} \P(r_{|\xi_1|}) .

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Remember $z^{(1)}_i + z^{(2)}_i = z_i$.

			




	
	
	
		
 
    The probability associated to this interleaving is

			




	
	
	
		
 
    and similar for $\xi_2$ but with primes.

			




	
	
	
		
 
    The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $\xi$ in the example above.

			




	
	
	
		
 
    \begin{center}

			




	
	
	
		
 
        \includegraphics{diagram_paths2.pdf}

			




	
	
	
		
 
    \end{center}

			




	
	
	
		
 
    For the labels shown within the grid, define $p_{ij} = \frac{z_i}{z_i + z_j'}$.

			




	
	
	
		
 
    The probability of $\xi$ is given by

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P_b[\xi] &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \frac{1}{z_3} \P(r_3) \frac{1}{z_4} \P(r_4) \cdots \\

			




	
	
	
		
 
        \P_b[\xi] &= \frac{1}{z_1+z_1'} \P(r_1') \frac{1}{z_1+z_2'} \P(r_1) \frac{1}{z_2+z_2'} \P(r_2) \frac{1}{z_3+z_2'} \P(r_2') \cdots \tag{by definition}\\

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \frac{z^{(1)}_1}{z_1} \frac{1}{z^{(1)}_1} \P(r_1) \;

			




	
	
	
		
 
        \frac{z^{(2)}_2}{z_2} \frac{1}{z^{(2)}_2} \P(r_2) \;

			




	
	
	
		
 
        \frac{z^{(2)}_3}{z_3} \frac{1}{z^{(2)}_3} \P(r_3) \;

			




	
	
	
		
 
        \frac{z^{(1)}_4}{z_4} \frac{1}{z^{(1)}_4} \P(r_4)

			




	
	
	
		
 
        \cdots \\

			




	
	
	
		
 
        \frac{z_1'}{z_1+z_1'} \frac{1}{z_1'} \P(r_1') \;

			




	
	
	
		
 
        \frac{z_1 }{z_1+z_2'} \frac{1}{z_1 } \P(r_1 ) \;

			




	
	
	
		
 
        \frac{z_2 }{z_2+z_2'} \frac{1}{z_2 } \P(r_2 ) \;

			




	
	
	
		
 
        \frac{z_2'}{z_3+z_2'} \frac{1}{z_2'} \P(r_2')

			




	
	
	
		
 
        \cdots \tag{rewrite fractions}\\

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \frac{z^{(1)}_1}{z_1}

			




	
	
	
		
 
        \frac{z^{(2)}_2}{z_2}

			




	
	
	
		
 
        \frac{z^{(2)}_3}{z_3}

			




	
	
	
		
 
        \frac{z^{(1)}_4}{z_4}

			




	
	
	
		
 
        \frac{z_1'}{z_1+z_1'} \;

			




	
	
	
		
 
        \frac{z_1 }{z_1+z_2'} \;

			




	
	
	
		
 
        \frac{z_2 }{z_2+z_2'} \;

			




	
	
	
		
 
        \frac{z_2'}{z_3+z_2'}

			




	
	
	
		
 
        \cdots

			




	
	
	
		
 
        \P_{b_1}[\xi_1] \P_{b_2}[\xi_2]

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    \todo{write more}

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P(\text{interleaving}) = \P(\text{choose step of }\xi_1) \P(\text{choose step of }\xi_2) \P(\text{choose step of }\xi_2) \P(\text{choose step of }\xi_1) \cdots

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    These choices depend on the number of zeroes present in the state:

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P(\text{choose step of }\xi_1) &=

			




	
	
	
		
 
        \frac{z^{(1)}_1}{z^{(1)}_1 + z^{(2)}_1} \\

			




	
	
	
		
 
        \P(\text{choose step of }\xi_2) &=

			




	
	
	
		
 
        \frac{z^{(2)}_1}{z^{(1)}_1 + z^{(2)}_1}

			




	
	
	
		
 
        \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $\P_{b_i}[\xi_i]$} \\

			




	
	
	
		
 
        &= (1-p_{1,1}) \; p_{1,2} \; p_{2,2} \; (1-p_{3,2}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2] \tag{definition of $p_{i,j}$} \\

			




	
	
	
		
 
        &= \P(\text{path in grid}) \; \P_{b_1}[\xi_1] \; \P_{b_2}[\xi_2]

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    These are the $p_i$ and $1-p_i$ shown in the grid diagram. In $\P_{b_1}[\xi_1]$ we have a factor $\frac{1}{z^{(1)}_1}$, so together with the probability above this gives $\frac{z^{(1)}_1}{z^{(1)}_1 + z^{(2)}_1} \frac{1}{z^{(1)}_1} = \frac{1}{z_1}$, as in the original expression for $\P_b[\xi]$. In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This means the sum of all $\P(\text{interleaving})$ is equal to 1.

			




	
	
	
		
 
    In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This proves the required equality.

			




	
	
	
		
 

			




	
	
	
		
 
    We obtain

			




	
	
	
		
 
    \begin{align*}

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








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