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

@@ @@ -28,6 +28,9 @@ @@
     \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)$};
@@ @@ -37,8 +40,10 @@ @@
     \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

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

0 comments (0 inline, 0 general)