Changeset - adb803662770
Parent rev.
Child rev.
[Not reviewed]
Merge
0 1 0
András Gilyén - 8 years ago 2017-09-07 01:31:35
gilyen@cwi.nl
Merge branch 'master' of https://git.overleaf.com/9473097rgxjnfdkjdhb
1 file changed with 114 insertions and 2 deletions:
main.tex
114
2
0 comments (0 inline, 0 general)
main.tex
➞
Show inline comments
 
@@ -471,7 +471,7 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha
 
    $$\xi=\left( (z_1, s_1, r_1), (z_2, s_2, r_2), ..., (z_{|\xi|}, s_{|\xi|}, r_{|\xi|}) \right)$$
 
    where $z_i\in[n]$ denotes the number of zeroes in the state before the $i$th step, $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. We have
 
    \begin{align*}
 
        \P_b[\xi] &= \P(\text{choose }s_1) \P(r_1) \P(\text{choose }s_2) \P(r_2) \cdots \P(\text{choose }s_{|\xi|}) \P(r_{|\xi|}) \\
 
        \P_b[\xi] &= \P(\text{pick }s_1) \P(r_1) \P(\text{pick }s_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi|}) \P(r_{|\xi|}) \\
 
                &= \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$.
 
@@ -497,7 +497,7 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha
 
    \end{align*}
 
    The probability of $\xi_1$, started from $b_1$, is given by
 
    \begin{align*}
 
        \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|}) \\
 
        \P_{b_1}[\xi_1] &= \P(\text{pick }s_1) \P(r_1) \P(\text{pick }s_2) \P(r_2) \cdots \P(\text{pick }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*}
 
    and similar for $\xi_2$ but with primes.
 
@@ -1313,6 +1313,118 @@ Here, I (Tom) tried to set do the same Lemma but for the cycle instead of the in
 
    To actually go below $2k$ one needs to be careful, because there are periodic configurations that are invariant under some rotations causing double counting issues. This can be probably resolved by showing that when a pattern becomes periodic for some $n$ it actually produces periodicity times more expectation due to symmetry. But this is all just speculation.
 
\end{comment}
 

			




	
	
	
		
 
\newpage

			




	
	
	
		
 
\textbf{test:} Rewrite of lemma and proof

			




	
	
	
		
 
\begin{lemma}[Conditional independence] \label{lemma:eventindependence} \label{claim:eventindependence}

			




	
	
	
		
 
    Let $b=b_L\land b_R\in\{0,1\}^n$ be a state with two groups ($b_L\lor b_R = 1^n$) of zeroes that are separated by at least one site inbetween, as in Figure \ref{fig:separatedgroups}. Let $j_1$, $j_2$ be any indices inbetween the groups, such that $b_L$ lies on one side of them (left) and $b_R$ on the other (right), as shown in the figure. Furthermore, let $A_L$ be any event that depends only on the sites ``on the $b_L$ side of $j_1,j_2$'', and similar for $A_R$ (for example $\mathrm{Z}^{(i)}$ for an $i$ on the correct side). Then we have

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)}, A_L, A_R)

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \mathbb{P}_{b_L}(\mathrm{NZ}^{(j_1,j_2)}, A_L)

			




	
	
	
		
 
        \; \cdot \;

			




	
	
	
		
 
        \mathbb{P}_{b_R}(\mathrm{NZ}^{(j_1,j_2)}, A_R) \\

			




	
	
	
		
 
        \mathbb{P}_b(A_L, A_R \mid \mathrm{NZ}^{(j_1,j_2)})

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \mathbb{P}_{b_L}(A_L \mid \mathrm{NZ}^{(j_1,j_2)})

			




	
	
	
		
 
        \; \cdot \;

			




	
	
	
		
 
        \mathbb{P}_{b_R}(A_R \mid \mathrm{NZ}^{(j_1,j_2)}) \\

			




	
	
	
		
 
        R_{b,\mathrm{NZ}^{(j_1,j_2)},A_L,A_R}

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        R_{b_L,\mathrm{NZ}^{(j_1,j_2)},A_L}

			




	
	
	
		
 
        \; + \;

			




	
	
	
		
 
        R_{b_R,\mathrm{NZ}^{(j_1,j_2)},A_R}

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    up to any order in $p$.

			




	
	
	
		
 
\end{lemma}

			




	
	
	
		
 
The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two halves of the cycle are independent. 

			




	
	
	
		
 

			




	
	
	
		
 
\begin{proof}

			




	
	
	
		
 
    From any path $\xi\in\paths{b} \cap \mathrm{NZ}^{(j_1,j_2)}$ we can construct paths $\xi_L\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_R\in\paths{b_2}\cap\mathrm{NZ}^{(j_1,j_2)}$ as follows. Let us write the path $\xi$ as

			




	
	
	
		
 
    $$\xi=\left( (s_1, r_1), (s_2, r_2), ..., (s_{|\xi|}, r_{|\xi|}) \right)$$

			




	
	
	
		
 
    where $s_i\in [n]$ denotes the site that was resampled and $r_i\in \{0,1\}^3$ is the result of the three resampled bits. Denote by $\textsc{state}_i \in \{0,1\}^n$ the state of the system at the start of step $i$. We have

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P_b[\xi] &= \P(\text{pick }s_1 | \textsc{state}_1 ) \P(r_1) \P(\text{pick }s_2 | \textsc{state}_2 ) \P(r_2) \cdots \P(\text{pick }s_{|\xi|} | \textsc{state}_{|\xi|} ) \P(r_{|\xi|})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    To construct $\xi_L$ and $\xi_R$, start with empty sequences $\xi_L,\xi_R$ and for each step $(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 $(s_i,r_i)$ to $\xi_L$ and if its ``on the $b_2$ side of $j_1,j_2$'' then add $(s_i,r_i)$ to $\xi_R$.

			




	
	
	
		
 
    %Let the resulting paths be

			




	
	
	
		
 
    %\begin{align*}

			




	
	
	
		
 
    %    \xi_L &= \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_L|}}, s_{a_{|\xi_L|}}, r_{a_{|\xi_L|}}) \right) \\

			




	
	
	
		
 
    %    \xi_R &= \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_L|}}, s_{b_{|\xi_L|}}, r_{b_{|\xi_L|}}) \right)

			




	
	
	
		
 
    %\end{align*}

			




	
	
	
		
 
    Now $\xi_L$ 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''.

			




	
	
	
		
 
    Vice versa, any two paths $\xi_L\in\paths{b_1}\cap \mathrm{NZ}^{(j_1,j_2)}$ and $\xi_R\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_L,\xi_R$ actually induce $\binom{|\xi_L|+|\xi_R|}{|\xi_L|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_L$ and $\xi_R$.

			




	
	
	
		
 
    For a fixed $\xi_L,\xi_R$ 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_L,\xi_R }} \P_b[\xi] &=

			




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

			




	
	
	
		
 
        &= \P_{b_1}[\xi_L] \cdot \P_{b_2}[\xi_R]

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    where both sums are over $\binom{|\xi_L|+|\xi_R|}{|\xi_L|}$ terms.

			




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

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \xi_L &= \left( (s_1, r_1), (s_2, r_2), (s_3, r_3), (s_4, r_4),\cdots  \right) \\

			




	
	
	
		
 
        \xi_R &= \left( (s_1', r_1'), (s_2', r_2'), (s_3', r_3'), (s_4', r_4'),\cdots  \right) \\

			




	
	
	
		
 
        \xi   &= \left( (s_1', r_1'), (s_1, r_1), (s_2, r_2), (s_2', r_2'), \cdots \right)

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Denote by $\textsc{state}^{L}_i\in\{0,1\}^n$ the state of the system at the start of step $i$ of $\xi_L$ and similar for $\xi_R$. Denote by $\textsc{state}^{L+R}_i$ the state at the start of step $i$ for this particular interleaving $\xi$.

			




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

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \P_{b_L}[\xi_L] &= \P(\text{pick }s_1 | \textsc{state}^{L}_1 ) \P(r_1) \P(\text{pick }s_2 | \textsc{state}^{L}_2 ) \P(r_2) \cdots \P(\text{pick }s_{|\xi_L|} | \textsc{state}^{L}_{|\xi_L|} ) \P(r_{|\xi_L|})

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    and similar for $\xi_R$.

			




	
	
	
		
 
    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]

			




	
	
	
		
 
        &= 

			




	
	
	
		
 
        \P(\text{pick }s_1' | \textsc{state}^{L+R}_1 ) \P(r_1')

			




	
	
	
		
 
        \P(\text{pick }s_1  | \textsc{state}^{L+R}_2 ) \P(r_1 ) \\

			




	
	
	
		
 
 &\qquad\P(\text{pick }s_2  | \textsc{state}^{L+R}_3 ) \P(r_2 )

			




	
	
	
		
 
        \P(\text{pick }s_2' | \textsc{state}^{L+R}_4 ) \P(r_2') \\

			




	
	
	
		
 
        &= 

			




	
	
	
		
 
        \P(\text{pick right}) \P(\text{pick }s_1' | \textsc{state}^{R}_1 ) \P(r_1')

			




	
	
	
		
 
        \P(\text{pick left} ) \P(\text{pick }s_1  | \textsc{state}^{L}_1 ) \P(r_1 ) \\

			




	
	
	
		
 
 &\qquad\P(\text{pick left} ) \P(\text{pick }s_2  | \textsc{state}^{L}_2 ) \P(r_2 )

			




	
	
	
		
 
        \P(\text{pick right}) \P(\text{pick }s_2' | \textsc{state}^{R}_2 ) \P(r_2') \\

			




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

			




	
	
	
		
 
    \end{align*}

			




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

			




	
	
	
		
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2)

			




	
	
	
		
 
        &= \sum_{\substack{\xi\in\paths{b} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] \\

			




	
	
	
		
 
        &= \sum_{\substack{\xi_L\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_1}} \;\;

			




	
	
	
		
 
          \sum_{\substack{\xi_R\in\paths{b_1} \cap \\ \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}

			




	
	
	
		
 
        \mathbb{P}[\xi_L]\cdot\mathbb{P}[\xi_R] \\

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1)

			




	
	
	
		
 
        \; \cdot \;

			




	
	
	
		
 
        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2).

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event.

			




	
	
	
		
 
    For the third equality, by the same reasoning we can decompose the paths

			




	
	
	
		
 
    \begin{align*}

			




	
	
	
		
 
        \mathbb{P}_b(\mathrm{NZ}^{(j_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}

			




	
	
	
		
 
        &\equiv \sum_{\substack{\xi\in\paths{b}\\\xi \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1\cap A_2}} \mathbb{P}[\xi] |\xi| \\

			




	
	
	
		
 
        &= \sum_{\substack{\xi_L\in\paths{b_1}\\\xi_L \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}

			




	
	
	
		
 
          \sum_{\substack{\xi_R\in\paths{b_2}\\\xi_R \in \mathrm{NZ}^{(j_1,j_2)}\cap A_2}}

			




	
	
	
		
 
        \mathbb{P}[\xi_L]\mathbb{P}[\xi_R] (|\xi_L| + |\xi_R|) \\

			




	
	
	
		
 
        &=

			




	
	
	
		
 
        \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1} \\

			




	
	
	
		
 
        &\quad +

			




	
	
	
		
 
        \mathbb{P}_{b_1}(\mathrm{NZ}^{(j_1,j_2)},A_1) \mathbb{P}_{b_2}(\mathrm{NZ}^{(j_1,j_2)},A_2) R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2} .

			




	
	
	
		
 
    \end{align*}

			




	
	
	
		
 
    Dividing by $\mathbb{P}_b(\mathrm{NZ}_{(j_1,j_2)},A_1,A_2)$ and using the first equality gives the desired result.

			




	
	
	
		
 
\end{proof}

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
	\bibliographystyle{alpha}

			




	
	
	
		
 
	\bibliography{Resample.bib}

			




	
	
	
		
 
	

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








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