AENC/resampling_chain Changeset - 280d2941c33b · Centrum Wiskunde & Informatica (CWI)

@@ -440,12 +440,17 @@ It is useful to introduce some new notation:

    \begin{align*}

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

&=

        \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) \\

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

&=

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

        \; \cdot \;

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

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

&=

        R_{b_1,\mathrm{NZ}^{(j_1,j_2)},A_1}

        \; + \;

        R_{b_2,\mathrm{NZ}^{(j_1,j_2)},A_2}

    \end{align*}

@@ -463,25 +468,26 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha

        \mathbb{P}[\xi_1]\cdot\mathbb{P}[\xi_2] \\

&=

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

    For the second equality, note that again by the same reasoning as in the proof of claim \ref{claim:expectationsum} we have

    The second equality follows directly from Bayes rule and removing $A_1,A_2$.

    For the third 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_1,j_2)},A_1,A_2) R_{b,\mathrm{NZ}^{(j_1,j_2)},A_1,A_2}

        &:= \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_1\in\paths{b_1}\\\xi_1 \in \mathrm{NZ}^{(j_1,j_2)}\cap A_1}}

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

        \mathbb{P}[\xi_1]\mathbb{P}[\xi_2] (|\xi_1| + |\xi_2|) \\

&=

        \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}\cap\mathrm{NZ}_{j_2},A_1,A_2)$ and using the first equality gives the desired result.

    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}

\begin{comment}

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

@@ -580,15 +586,15 @@ The intuition of the following lemma is that the far right can only affect the z

	Also this claim finally ``sees'' how many empty places are between slots. These properties make it possible to use this lemma to prove the sought linear bound. We show it for the infinite chain, but with a little care it should also translate to the circle.

Here, I (Tom) tried to set up the same Lemma but for the circle instead of the infinite chain.

This time, it is no longer $I_\mathrm{max}$ but any vertex $i_* \in I$, and $I' = I \setminus \{i_*\}$. Without loss of generality, we can assume that $i_* \leq n/2$ (because if not then we can relabel the vertices and count the other way around so that $i_* \to n-i_*$). The goal is now to prove:

This time, it is no longer $I_\mathrm{max}$ but any vertex $i_* \in I$, and $I' = I \setminus \{i_*\}$. Without loss of generality, we can assume that $i_* \leq n/2$ so that the distance to $0$ is simply $d(i_*,0)=i_*$ (because if not then we can relabel the vertices and count the other way around so that $i_* \to n-i_*$). The goal is now to prove:

\begin{align*}

    P_I(Z^{(0)}) = P_{I'}(Z^{(0)}) + \mathcal{O}(p^{i_* + 1 - |I|})

    P_I(Z^{(0)}) = P_{I'}(Z^{(0)}) + \mathcal{O}(p^{\mathrm{d}(i_*,0) + 1 - |I|})

\end{align*}

Note that when we refer to an interval $[a,b]$ on the circle we could be referring to two possible intervals because of the periodicity of the circle. In the following, whenever we refer to an interval $[a,b]$ we refer to the interval with vertex 0 on the \emph{inside}.

For $a,b\in[n]$, define the event ``zeroes patch'' as the event of getting zeroes inside the interval $[a,b]$ but not on the boundary, i.e.  $\mathrm{ZP}^{[a,b]} = \mathrm{NZ}^{(a)} \cap \mathrm{Z}^{(a+1)} \cap \mathrm{Z}^{(a+2)} \cap \cdots \cap \mathrm{Z}^{(b-1)} \cap \mathrm{NZ}^{(b)}$ (where we assume that $\mathrm{Z}^{(0)}$ is part of this intersection).

Furthermore, define the `inside' and `outside' of $I$ as $I_{\mathrm{in}(a,b)} = I\cap[a,b]$ and $I_{\mathrm{out}(a,b)} = I \setminus [a,b]$.

@@ -601,27 +607,27 @@ The following diagram illustrates these definitions.

    &=\sum_{\substack{l,k=1\\k+l<n}}

    P_I(\mathrm{ZP}^{[n-l,k]}) \tag{the events are a partition}\\

    &=\sum_{\substack{l,k=1\\k+l<n\\k,n-l\notin I}}

    P_I(\mathrm{ZP}^{[n-l,k]}) \tag{$\mathbb{P}(\mathrm{ZP}^{[a,b]})=0$ for $a\in I$ or $b\in I$}

\end{align*}

Note that if $[-l,k]$ does not `touch' $I$ then $P_I(\mathrm{ZP}^{[-l,k]}) = 0$.

Furthermore, we have $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{k+l-1-|I_{\mathrm{in}(n-l,k)}|})$. If $k\geq i_*$ or $l\geq i_*$ then this gives $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{i_* - 1 - |I|})$ since $|I_\mathrm{in}| \leq |I|$. Therefore we have

Furthermore, we have $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{k+l-1-|I_{\mathrm{in}(n-l,k)}|})$. If $k > \mathrm{d}(i_*,0)$ or $l > \mathrm{d}(i_*,0)$ then this gives $P_I(\mathrm{ZP}^{[n-l,k]}) = \mathcal{O}(p^{\mathrm{d}(i_*,0) + 1 - |I|})$ since $|I_\mathrm{in}| \leq |I|$. Therefore we have

\begin{align*}

    P_I(\mathrm{Z}^{(0)})

    &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}

    P_I(\mathrm{ZP}^{[n-l,k]})

    + \mathcal{O}(p^{i_* - 1 - |I|}) \\

    + \mathcal{O}(p^{i_* + 1 - |I|}) \\

    &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}

    P_{I_{\mathrm{in}(n-l,k)}}(\mathrm{ZP}^{[n-l,k]}) \cdot

    P_{I_{\mathrm{out}(n-l,k)}}(\mathrm{NZ}^{(n-l,k)})

    + \mathcal{O}(p^{i_* - 1 - |I|}) \\

    + \mathcal{O}(p^{i_* + 1 - |I|}) \\

    \tag{by Claim~\ref{claim:eventindependence} for $n-l,k\notin I$} \\

    &=\sum_{\substack{l,k=1\\k,n-l\notin I}}^{i_*-1}

    P_{I'_{\mathrm{in}(n-l,k)}}(\mathrm{ZP}^{[n-l,k]}) \cdot

    P_{I_{\mathrm{out}(n-l,k)}}(\mathrm{NZ}^{(n-l,k)})

    + \mathcal{O}(p^{i_* - 1 - |I|})

    + \mathcal{O}(p^{i_* + 1 - |I|})

\end{align*}

Now we are supposed to use the induction step, but this is where I got stuck.

\begin{definition}[Connected patches]

	Let $\mathcal{P}\subset 2^{\mathbb{Z}}$ be a finite system of finite subsets of $\mathbb{Z}$. We say that the patch set of a resample sequence is $\mathcal{P}$,