AENC/resampling_chain Changeset - 25366b6ee86a · Centrum Wiskunde & Informatica (CWI)

Changeset - 25366b6ee86a

Parent rev.

Child rev.

[Not reviewed]

0 3 0

Tom Bannink - 8 years ago 2017-05-31 16:44:52
tom.bannink@cwi.nl

Update diameter diagram

3 files changed with 9 insertions and 4 deletions:

diagram_gap.pdf

bin+mod

diagram_gap.tex

main.tex

0 comments (0 inline, 0 general)

diagram_gap.pdf

➞

Show inline comments

binary diff not shown

diagram_gap.tex

➞

Show inline comments

@@ @@ -25,20 +25,25 @@ @@
     \draw[fill] (11,1) circle (0.04);
     \draw[fill] (-1,1) circle (0.04);
     \foreach \x in {1,2,4,7,9} {
         \draw[fill,red] (\x,0) circle (0.08);
+    }
     \foreach \x in {3,5,6,8} {
         \draw[fill,blue] (\x-0.06,0-0.06) rectangle +(0.12,0.12);
+    }
     \draw[<->] (1,-0.5) -- (9,-0.5);
     \draw (5,-0.9) node {$\mathcal{D}(C)$};
     \draw[<->] (4.9,0.3) -- (6.1,0.3);
     \draw (5.5,0.7) node {$\mathrm{gap}(C)$};
     \draw[fill,red] (1,-2) circle (0.08);
     \draw (2,-2) node {slots $C$};
     \draw[fill] (5,-2) circle (0.04);
     \draw (6.5,-2) node {non-slots $[n]\setminus C$};
     %\draw[fill] (3,-2) circle (0.04);
     %\draw (4.5,-2) node {non-slots $[n]\setminus C$};
     \draw[fill,blue] (7.4-0.06,-2-0.06) rectangle +(0.12,0.12);
     \draw (8,-2) node {$C_{><}$};
 \end{tikzpicture}
 \end{document}

main.tex

➞

Show inline comments

 \end{definition}
 \begin{figure}
 	\begin{center}
     	\includegraphics{diagram_gap.pdf}
     \end{center}
-    \caption{\label{fig:diametergap} A configuration $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 slots shown by the red dots. The dotted line at the top depicts the rest of the circle which may be much larger. The diameter of this configuration is $\diam{C}=9$ as shown and the largest gap of $C$ is $\mathrm{gap}(C)=2$. Note that we do not count the rest of the circle as a gap, we only consider gaps \emph{within} the diameter of $C$.}
+    \caption{\label{fig:diametergap} A configuration $C=\{1,2,4,7,9\}\subseteq[n]$ consisting of 5 slots shown by the red dots. The blue squares denote the set $C_{><}$ which is all elements of $[n]\setminus C$ that lie within the interval spanned by $C$. The dotted line at the top depicts the rest of the circle which may be much larger. The diameter of this configuration is $\diam{C} = |C| + |C_{><}| =9$ as shown. The largest gap of $C$ is $\mathrm{gap}(C)=2$ which is the largest connected component of $C_{><}$. Note that we do not count the rest of the circle as a gap, we only consider gaps \emph{within} the diameter of $C$.}
 \end{figure}
 \begin{claim}[Strong cancellation claim] \label{claim:strongcancel}
 	The lowest order term in
     \begin{align*}
         \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,
 	Then $P_{I}(V^{(0)})=P_{I'}(V^{(0)}) + O(p^{I_{\max}+1-|I|})$.
 \end{lemma}
 \begin{proof}
 	The proof uses induction on $|I|$. For $|I|=1$ the statement is easy, since every resample sequence that resamples the $0$ vertex must produce at least $I_{\max}$ number of $0$-s during the resamplings.
 	Induction step: For an event $A$ and $k>0$ let us denote by $A_k=A\cap$``Each vertex in $0,1,2,\ldots, k-1$ gets $0$ before termination (either by resampling or initialisation), but not $k$''. Observe that $V^{(0)}=\dot{\bigcup}_{k=1}^{\infty}V^{(0)}_k$.
-	Let $I_{<k}:=I\cap[k-1]$ and similarly $I_{>k}:=I\setminus[k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$. Suppose we proved the claim up to $|I|-1$, then the induction step can be shown by
+    Let $I_{<k}:=I\cap[k-1]$ and similarly $I_{>k}:=I\setminus[k]$, finally let $I_{><}:=\{I_{\min}+1,I_{\max}-1]\}\setminus I$ as shown in Figure \ref{fig:diametergap}. Suppose we proved the claim up to $|I|-1$, then the induction step can be shown by
 	\begin{align*}
 		P_{I}(V^{(0)})
 		&=\sum_{k=1}^{\infty}P(V^{(0)}_k)
 		=\sum_{k\in \mathbb{N}\setminus I}P(V^{(0)}_k)\\
 		&=\sum_{k\in\mathbb{N}\setminus I}P_{I_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}}) \tag{by Claim~\ref{claim:eventindependence}}\\
 		&=\sum_{k\in I_{><}}P_{I_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}+1-|I|})

0 comments (0 inline, 0 general)