Changeset - 25366b6ee86a
[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:
0 comments (0 inline, 0 general)
diagram_gap.pdf
Show inline comments
 
binary diff not shown
diagram_gap.tex
Show inline comments
 
@@ -19,26 +19,31 @@
 
    \draw[gray,dotted] (0,2) -- (10,2);
 
    \draw[gray] (0,2) arc (90:270:1);
 
    \draw[gray] (10,0) arc (-90:90:1);
 
    \foreach \x in {0,...,10} {
 
        \draw[fill] (\x,0) circle (0.04);
 
    }
 
    \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
 
@@ -247,25 +247,25 @@ We can further rewrite the sum over $b\in\{0,1,1'\}^n$ as a sum over all slot co
 
	R^{(n)}(p) &= \frac{1}{n} \sum_{C\subseteq[n]} \sum_{f\in\{0,1'\}^{|C|}} \rho_{C(f)} R_{C(f)} ,
 
\end{align*}
 
where $C(f)\in\{0,1,1'\}^n$ denotes a configuration with slots on the sites $C$ filled with (anti)particles described by $f$. The non-slot positions are filled with $1$s.
 

	
 
\begin{definition}[Diameter]
 
	For a slot configuration $C\subseteq[n]$, we define the diameter $\diam{C}$ to be the minimum size of an interval containing $C$ where the interval is also considered modulo $n$. In other words $\diam{C} = n - \max\{ j \vert \exists i : [i,i+j-1]\cap C = \emptyset \}$. Figure \ref{fig:diametergap} shows the diameter in a picture.
 
\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)} ,
 
    \end{align*}
 
	is $p^{\diam{C}}$ when $n$ is large enough. All lower order terms cancel out.
 
\end{claim}
 

	
 
Example: for $C_0=\{1,2,4,7,9\}$ (the configuration shown in Figure \ref{fig:diametergap}) we computed the quantity up to order $p^{20}$ in an infinite system:
 
\begin{align*}
 
@@ -519,25 +519,25 @@ Consider the chain (instead of the cycle) for simplicity with vertices identifie
 
\end{definition}
 

	
 
The intuition of the following lemma is that the far right can only affect the zero vertex if there is an interaction chain forming, which means that every vertex should get resampled to $0$ at least once.
 
\begin{lemma}\label{lemma:probIndep}
 
	Suppose we have a finite set $I\subset\mathbb{N}_+$ of vertices.
 
	Let $I_{\max}:=\max(I)$ and $I':=I\setminus\{I_{\max}\}$, and similarly let $I_{\min}:=\min(I)$.
 
	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|})
 
		\tag{$k<I_{\min}\Rightarrow P_{I_{<k}}(V^{(0)}_k)=0$}\\
 
		&=\sum_{k\in I_{><}}P_{I'_{<k}}(V^{(0)}_k)\cdot P_{I_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}+1-|I|})	
 
		\tag{$k< I_{\max}\Rightarrow I_{<k}=I'_{<k}$}\\
 
		&=\sum_{k\in I_{><}}P_{I'_{<k}}(V^{(0)}_k)\cdot
 
		\left(P_{I'_{>k}}(\overline{V^{(k)}})+\mathcal{O}(p^{I_{\max}-k+1-|I_{>k}|})\right) +\mathcal{O}(p^{I_{\max}+1-|I|})	\tag{by induction, since for $k>I_{\min}$ we have $|I_{<k}|<|I|$}\\
 
		&=\sum_{k\in I_{><}}P_{I'_{<k}}(V^{(0)}_k)\cdot
0 comments (0 inline, 0 general)