Changeset - b43c29412d5d
[Not reviewed]
0 1 0
Tom Bannink - 8 years ago 2017-05-29 08:51:35
tombannink@gmail.com
Add note on probability independence claim
1 file changed with 6 insertions and 0 deletions:
0 comments (0 inline, 0 general)
main.tex
Show inline comments
 
@@ -405,24 +405,30 @@ where we used the identity $\sum_{a\in\{0,1\}^l} (-1)^{|a|} = 0$.
 
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{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]
 
        \; \cdot \;
 
        \mathbb{P}[\mathrm{NZ}_{j_1} , \mathrm{NZ}_{j_2} \;|\;\text{start in }b_2]
 
    \end{align*}
 
up to any order in $p$.
 
\end{claim}
 
Since the left hand side is defined as
 
\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]
 
\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}    
0 comments (0 inline, 0 general)