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

@@ -443,6 +443,11 @@ It is useful to introduce some new notation:

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

@@ -466,7 +471,8 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha

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

@@ -478,7 +484,7 @@ The lemma says that conditioned on $j_1$ and $j_2$ not being crossed, the two ha

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

@@ -583,9 +589,9 @@ The intuition of the following lemma is that the far right can only affect the z

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

@@ -604,21 +610,21 @@ The following diagram illustrates these definitions.

    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.