
%\section{Monte-Carlo-Simulationen des Ising-Modells}
%\subsection{Statistische Eigenschaften von Zeitreihen}
%\subsubsection{Motivation}
\section{Statistische Eigenschaften von Zeitreihen}
\subsection{Motivation}
Experimentelle Messungen und Simulationen liefern im Allgemeinen nicht ein
exaktes Ergebnis, sondern eine \hl{Zeitreihe} (d.h. eine geordnete Liste) von
Ergebnissen (Skalaren, Vektoren, etc.)
\begin{problem}
 Wie lassen sich Zeitreihen (hier: Skalare) charakterisieren und
interpretieren? Was sagen sie über das exakte Ergebnis aus?
\end{problem}
\begin{beispiel}{1}
 Eine Simulations/Messreihe liefert die Zahlen $47.5,\; 47.7,\; 47.2,\; 46.8$
- Charakterisierung?
 \begin{itemize}
  \item alle Werte ungefähr $47$
  \item \hl{Mittelwert:} $47.3$
  \item \hl{Varianz der Einzelmessung:} $0.153$
  \item	\hl{Mittelwert mit Standartabweichung:} `$47.30\pm 0.20$
  \item \hl{Trend/Transient:} negativ (spätere Werte eher kleiner)
  \item \hl{Histogramm:} nicht sinnvoll (zu wenige Werte)
  \item \hl{Autokorrelation:} nicht erfassbar
 \end{itemize}
$\;$
\end{beispiel}
\begin{frage}
 how to get reliable results from simulations?
\end{frage}
Result: estimate + error bars\\
Typical case in computer simulations:\\
simulations start with non-representative configurations and gradually approach
steady state (e.g. thermal equilibrium)\\
both mean and variance of initial measurements can differ strongly from later
ones and should be thrown away
\\
BILD
\\
Let us now assume that transient parts habe been discarded. How to compute best
estimate + error bars?\\
\\
Mathematical excursion\\
let $X$ be a random variable with \hl{probability distribution} p:
\begin{equation}
 P(x\leq X\leq x+dx)=p(x)dx\quad(p(x)
\equiv P_X\!(x))
\end{equation}
example: uniform distribution\\
\\
BILD
\\
\begin{equation}
 p(x) = \left\lbrace\begin{array}{cl}
 1 & \textrm{for} \; 0\leq x\leq1\\
 0 & \textrm{else}
\end{array}\right.
\end{equation}
probability distribution is normalized: $$\displaystyle \int
\limits_{-\infty}^{\infty}p(X)dX=1$$
\begin{tabular}{ll}
 \hl{mean ($1^{st}$ moment):} & $\displaystyle \langle X\rangle =
\int\limits_{-\infty}^{\infty}Xp(X)dX$\\
 \hl{$2^{nd}$ moment:} & $\displaystyle\langle X^2\rangle =
\int\limits^{\infty}_{-\infty}X^2p(X)dX$\\
 \hl{variance:} & $\displaystyle\sigma_X^2=\langle(X-\langle
X\rangle)^2\rangle=\langle X^2\rangle-\langle
X\rangle^2$
\end{tabular}
\\
The mean is always additive; the variance only for uncorrelated random
variables:
\begin{eqnarray}
 \langle X+Y\rangle & = & \int\limits dX\int\limits dY p(X,Y)
(X+Y)\\
& = & \int\limits dX X\int\limits dY p(X,Y)+\int\limits dY Y\int dX 
p(X,Y)\\
& = & \langle X\rangle+\langle Y\rangle\\
\sigma_{X+Y}^2 & = & \langle\lbrack(X+Y)-\langle X+Y
\rangle\rbrack^2\rangle\\
& = & \langle\lbrack(X-\langle X\rangle)+
(Y-\langle Y\rangle)\rbrack^2\rangle\\
& = & \sigma_X^2+\sigma_Y^2+\underbrace{2\langle(X-\langle X
\rangle)(Y-\langle Y\rangle)\rangle}_{
=0\; \textrm{for uncorrelated variables}}
\end{eqnarray}
Specificially for $\sigma_X=\sigma_Y\equiv \sigma$ in uncorrelated case:
\begin{equation}
 \sigma\bigg\lbrack\frac{X+Y}{2}\bigg\rbrack=\frac{\sigma}{\sqrt{2}}
\end{equation}
and in fully correlated case $X=Y$:
\begin{equation}
 \sigma\bigg\lbrack\frac{X+Y}{2}\bigg\rbrack=\sigma
\end{equation}
and for arhitmetic average of $N$ uncorrelated random numbers with equal
variance $\sigma$:
\begin{equation}
 \sigma_{\bar{X}}=\sigma\Big\lbrack\frac{1}{N}\sum_{i=1}^{N}X_i\Big\rbrack
=\frac{\sigma}{\sqrt{N}}
\end{equation}
This is one formulation of the \hl{central limit theorem}.\\
Full probability distribution of sum/average?
\begin{eqnarray}
P_{X+Y}(z) & = & \int dX P_X(X)\int dY P_Y(Y)
\delta(z-(X+Y))\\
& = & \int dX P_X(X)P_Y(z-X)
\end{eqnarray}
specifically for uniformly distributed $X,\,Y$:
\begin{equation}
 P_{X+Y}(z)=\left\lbrace\begin{array}{rcl}
 z & \textrm{for} & 0\leq z\leq1\\
 2-z & \textrm{"'} & 1\leq z\leq 2\\
 0 & else &
\end{array}\right.
\end{equation}
BILD\\
\\
Look at higher order cumulants $\rightarrow$ normal distribution
\begin{equation}
 P_{\bar{X}}(x) \stackrel{N\rightarrow\infty}{\longrightarrow}
\frac{1}{\sigma_{\bar{X}}\sqrt{2\pi}}\exp{\bigg\lbrack-\frac{1}{2}\Big(
\frac{\bar{X}-\langle X\rangle}{\sigma_{\bar{X}}}\Big)^2
\bigg\rbrack};\quad\sigma_{\bar{X}}=\frac{\sigma}{\sqrt{N}}
\end{equation}
\hl{central limit theorem} (uncorrelated case!)\\
Now: application to simulation/measurements\\
again: random variables $X_i$ with same distribution, non necessarily
uncorrelated\\
\begin{problem}
 Probability distribution, mean, variance unknown. Best unbiased estimates?
\end{problem}
easy:
\begin{equation}
 \langle X\rangle \approx \bar{X}=\frac{1}{N}\sum_{i_1}^N X_i
\end{equation}
$\bar{X}$ is (best) unbiased estimator for $\langle X\rangle$ since
\begin{equation}
 \langle\bar{X}\rangle=\frac{1}{N}\sum_{i=1}^N
\underbrace{\langle X_i\rangle}_{\langle X\rangle}
=\langle X\rangle
\end{equation}
\begin{equation}
 \left(\begin{array}{ll}
 \textrm{also unbiased:} & \tilde{X}=\sum_{i=1}^N a_iX_i\;\textrm{with}\;
\sum_{i=1}^N a_i=1\\
\textrm{also estimator:} & \tilde{\tilde{X}}=\frac{1}{N-1}\sum_{i=1}^N X_i\;
(\textrm{since}\; \langle\tilde{\tilde{X}}\rangle=\frac{N}{N-1}
\langle X\rangle\stackrel{N\rightarrow\infty}{\longrightarrow}
\langle X\rangle)
\end{array}\right)
\end{equation}
difficult: best estimator for error of $\bar{X}$?
Step (i) unbiased estimator for $\sigma_X$?
\begin{eqnarray}
 \langle\sum_{i=1}^N(X_i-\bar{X})^2\rangle & = & N
\langle(X_i-\bar{X})^2\rangle\\
&= & N\bigg\langle\Big(X_i-\frac{1}{N}\sum_{j=1}^N X_j\Big)^2\bigg\rangle\\
&=& N\bigg\langle\Big\lbrack(X_i-\langle X\rangle)-
\frac{1}{N}\sum_{j=1}^N(X_j-\langle X\rangle)
\Big\rbrack^2\bigg\rangle\\
&=&N\bigg\langle\Big\lbrack\Big(1-\frac{1}{N}\Big)(X_i-\langle X
\rangle)-\frac{1}{N}\sum_{\substack{j=1\\j\neq i}}^N(X_j-
\langle X\rangle)\Big\rbrack^2\bigg\rangle\\
&\stackrel{\textrm{no. corr.}}{=}&N\Big\lbrack\Big(1-\frac{1}{N}\Big)^2
\langle(X_i-\langle X\rangle)^2\rangle+
\frac{1}{N^2}\sum_{\substack{j=1\\j\neq i}}\big\langle(X_j-\langle
X\rangle)^2\big\rangle\Big\rbrack\\
&=&\frac{(N-1)^2}{N}\sigma^2+\frac{N-1}{N}\sigma^2\\
&=&\sigma^2\frac{\lbrack(N-1)+1\rbrack(N-1)}
{N}\\
&=&(N-1)\sigma^2
\end{eqnarray}
Thus, $\displaystyle\sigma^2_{est}=\frac{1}{N-1}\sum_{i=1}^N(X_i-\bar{X}
)^2$ is an unbiased estimator for the variance $\sigma^2$ if the data is
uncorrelated.\\
Above estimator systematically underestimates $\sigma^2$ for autocorrelated
data ($\frac{1}{N}$-effect). Better: $\displaystyle\sigma^2_{est,imp}=
\frac{\sum_i(X_i-\bar{X})^2}{N-\tau}$.\\
Step (ii) variance of mean value $\bar{X}$:
\begin{eqnarray}
 \big\langle(\bar{X}-\langle X\rangle)^2\big\rangle
&=&\bigg\langle\Big(\frac{1}{N}\sum_{i=1}^NX_i-\langle X\rangle
\Big)^2\bigg\rangle\\
&=&\bigg\langle\Big\lbrack\frac{1}{N}\sum_{i=1}^N(X_i-\langle X
\rangle)\Big\rbrack^2\bigg\rangle\\
&=&\frac{1}{N^2}\sum_{i=1}^N\sum_{j=1}^N\big\langle(X_i-\langle X
\rangle)(X_j-\langle X\rangle)\big\rangle\\
\textrm{gen. Def.:} & & C_{A,B}=\frac{\big\langle(A-\langle A
\rangle)(B-\langle B\rangle)\big\rangle}
{\sigma_A\sigma_B}\\
&=&\frac{\sigma^2}{N^2}\sum_{i=1}^N\sum_{j=1}^NC_{i,j}\\
&\stackrel{translation inv.}{\approx}&\frac{\sigma^2}{N^2}\sum_{i=1}^N
\sum_{j=1}^NC_{i-j}\\
&=&\frac{\sigma^2}{N^2}\sum_{i=1}^N\sum_{k=i-N}^{i-1}C_k\\
&\approx&\frac{\sigma^2}{N^2}\sum_{i=1}^N\sum_{k=-\infty}^\infty C_k\\
&=&\frac{\sigma^2}{N}\tau
\end{eqnarray}
\hl{autocorrelation time} $\displaystyle\tau=\sum_{k=-\infty}^\infty C_k
\stackrel{C_k=C_{-k}}{=}1+2\sum_{k=1}^\infty C_k$\\
$\displaystyle C_k\approx\frac{\frac{1}{N-k-1}\sum_{i=1}^{N-k}(X_i-\bar{X}
)(X_{i+k}-\bar{X})}{\frac{1}{N-1}\sum_{i=1}^N(X_i-\bar{X}
)^2}\quad$ autocorrelation function
\begin{beispiel}{Datenanalyse}
 Vorgegeben sind 6 Zeitreihen LINK, diese sollen analysiert werden, z.B. mit
dem Statistik-Tool stats\_v1\_4.
\end{beispiel}


%\subsection{Metropolis Monte-Carlo Methode}
\section{Metropolis Monte-Carlo Methode}
Generische Aufgabenstellung: Berechnung von Integral (oder Summe), z.B. über
Teilgebiet des $\mathbb{R}^d$.
\begin{equation}
 I=\int\limits_Vd^dr f(\vec{r});\quad V\subset\mathbb{R}^d\;\textrm{kompakt
+endlich}
\end{equation}
\begin{ansatz}{Deterministischer}
 wähle regelmäßiges Gitter, z.B. isotrop mit Schrittweite h
$$\vec{r}_{\vec{n}}=h\vec{n}\qquad(\vec{n}\in\mathbb{Z}^d)$$
und approximiere Integral durch diskrete Approximation (numerische Integration):
$$I\approx h^d\sum_{\substack{\vec{n}\\ \vec{r}_{\vec{n}}\in V}}f(
\vec{r}_{\vec{n}})$$
\end{ansatz}
\begin{problem}
 der relative Fehler ist proportional zur Schrittweite $h^s$ (z.B. $h$ oder
$h^2$), der Aufwand $t$ skaliert aber mit der Anzahl der Funktionsauswertungen:
$$t\approx\frac{V}{h^d}\propto h^{-d} \Rightarrow \Delta I\propto h^2
\propto t^{-\frac{2}{d}}$$
fällt für große $d$ nur sehr langsam ab bei Rechenzeit $t\rightarrow\infty$
\end{problem}
\begin{beispiel}{2a}
 Bei Integration 2. Ordnung und $d=200$ muss man für Halbierung des Fehlers
$2^{100}\approx10^{30}$ mal länger rechnen.\\
Alternative: \hl{stochastischer Ansatz}
\hl{(i) Monte Carlo (MC) ohne Gewichtung (simple Monte Carlo)}
\begin{equation}
 \Delta I\approx I_N=V\frac{1}{N}\sum_{i=1}^N f(\vec{r}_i)
\end{equation}
mit zufällig, gleichverteilt gezogenen Koordinaten (d.h. konstante
Wahrscheinlichkeitsdichte für mögliche Koordinaten):
\begin{equation}
 p(\vec{r}_i)=\frac{1}{V}\qquad\textrm{mittels 
Standard-Zufallszahlgenerator}
\end{equation}
Falls die Varianz $\sigma^2_f$ von f auf V existiert (und endlich ist), 
konvergiert die MC-Auswertung für lange Zeiten laut dem Gesetz der großen Zahl:
\begin{eqnarray}
 \Delta I_N & = & \frac{\sigma_f}{\sqrt{N}}\stackrel{N\rightarrow\infty}
{\longrightarrow}0\\
\Delta I_N & \approx & t^{-\frac{1}{2}}
\end{eqnarray}
Schon bei $d\geq5$ konvergiert die MC-Lösung also schneller als ein
Integrationsverfahren mit Fehler $\propto h^2$.
\end{beispiel}
\begin{beispiel}{2b}
 Für Beispiel 2a ($d=200$) lässt sich der Fehler (wie in allen Anwendungen)
durch 4 Mal höhere Rechenzeit halbieren (statt Faktor $10^{30}$).
\begin{problem}
 die Varianz $\sigma^2_f$ ist häufig groß, insbesondere in Anwendungen der
Statistischen Physik (Schwankungen des Boltzmann-Faktors $\exp{-\beta Ei}$
um viele Größenordnungen).
\end{problem}
\hl{(ii) Monte Carlo mit Gewichtung ("`importance sampling"')}\\
\begin{idee}
konzentriere Stichproben $\vec{r}_i$ auf Bereiche, die besonders stark
zum Integral beitragen.
\end{idee}
BILD\\
Man wählt also eine Verteilungsfunktion $p(x)$, die $\vert
f(x)\vert$ approximiert.\\
Formal: zerlege Integrand $f(x)$ in Wahrscheinlichkeitsanteil
$p(x)$ und Observablenanteil $o(x)$:
\begin{eqnarray}
 I&=&\int\limits_Vd^dr f(\vec{r})=\int\limits_Vd^dr p
(\vec{r})o(\vec{r})\\
&\approx&V\frac{1}{N}\sum_{i=1}^N o(\vec{r}_i);\quad\vec{r}_i\;
\textrm{zufällig mit Wahrscheinlichkeitsv.} p(\vec{r}_i)\\
&&\textrm{beachte: Normierung von}\; p(\vec{r})\;
\textrm{muss bekannt sein!}\nonumber\\
\Delta I_N&=&\frac{\sigma_o}{\sqrt{N}};\;\sigma_o\ll\sigma_f\quad
\textrm{für geeignete Wahl von} o(\vec{r})
\end{eqnarray}
\begin{problem}
 Wie realisiert man inhomogene W.-Verteilungen?
\begin{itemize}
 \item Variablen-Transformation
 \item Box-Müller für Gauß-Verteilung
 \item Von Neumann "rejection method" - ineffizient
 \item ??? (keine allg. Methode verfügbar!)
\end{itemize}
.
\end{problem}
.
\end{beispiel}
\hl{(iii) Markow-Ketten-Monte Carlo, Metropolis Algorithmus}\\
\begin{idee}
 erzeuge Kette $\vec{r}_{1},\vec{r}_{2},\ldots,\vec{r}_{n}$ von Zuständen,
wobei die Wahrscheinlichkeitsverteilung$p(\vec{r}_{n})$
asymptotisch gegen eine gewünschte Verteilung $p(\vec{r})$
konvergiert.
\end{idee}
\begin{definition}
 Ein \hl{Stochastischer Prozess} ist eine Familie von Zufallsvariablen
$(X_t)_{t\in I}$, wobei die Indexmenge geordnet ist:
$I=\lbrace t_0<t_1<\ldots\rbrace$. Für eine abzählbare Menge
$I$ (typisch $I=\mathbb{N}$) heißt der Prozess \hl{zeitdiskret}, sonst
\hl{zeitstetig} (z.B. für $I=\mathbb{R}_0^+$).
\end{definition}
\begin{bemerkung}
 Die Wertemengen der Zufallsvariablen können in den Fällen diskret oder
stetig sein.
\end{bemerkung}
\textbf{Wichtig:} Zur vollständigen Charakterisierung eines Stochastischen
Prozesses müssen neben den Wahrscheinlichkeitsverteilungen für festes $t$
(1-Punkt-Verteilungen)
\begin{equation}
 p_n(X_{t_n})\equiv p(X_n,t_n)
\end{equation}
i.A. auch alle n-Punkt-Verteilungen spezifiziert werden, z.B.
$p(x_n,t_n;x_{n-1},t_{n-1};\ldots;x_1,t_1)$
\begin{beispiel}{3a}
 Wiederholter Münzwurf; bei "`Zahl"' steigt der Kontostand des Spielers um $1$,
bei "`Wappen"' sinkt er um $1$.
\begin{eqnarray}
 p_0(x) & = & \delta_{x,0}\\
p_1(x) & = &\frac{1}{2}(\delta_{x,-1}+\delta_{x,1})\\
p_2(x) & = &\frac{1}{2}(\delta_{x,-2}+2\delta_{x,0}+
\delta_{x,2})\equiv p(x_2,2)\\
\ldots\nonumber\\
\textrm{aber:} & & p(x_n,n\vert x_{n-1},n-1)=\frac{1}{2}(
\delta_{x_n,x_{n-1}-1}+\delta_{x_n,x_{n-1}+1})\\
\end{eqnarray}
( Allgemein gilt: $p(x_n,n;x_m,m)=p(x_n,n\vert x_m,m)
p(x_m,m)$)
\end{beispiel}
\begin{beispiel}{3b}
 ein modifiziertes Spiel, in dem nach jedem Wurf das Vorzeichen des
Kontostandes invertiert wird, hat war die gleiche 1-Punkt-Verteilung
wie Bsp. 3a, aber andere n-Punkt-Verteilungen für $n\geq2$.
\end{beispiel}
\begin{definition}
 Einen stochastischen Prozess, in dem die bedingte W'-verteilung nur vom
letzten bekannten Zustannd abhängt, nennt man \hl{Markov-Prozess}:
\begin{equation}
 p(x_n,t_n\vert x_{i_1},t_{i_1};\ldots;x_{i_k},t_{i_k})=
p(x_n,t_n\vert x_{i_s},t_{i_s})
\end{equation}
für $\displaystyle t_{i_s}=\max_{1\leq j\leq k}\lbrace t_{i_j}
\rbrace$
\end{definition}
\begin{beispiel}{}
 Zufallsbewegungen (Random Walks) wie Bsp. 3a sind Markov-Prozesse; auch 3b
ist Markov-Prozess.
\end{beispiel}
Ein Markov-Prozess hat also ein minimales "`Gedächtnis"'; Prozesse ohne
Gedächtnis nennt man unkorreliert.\\
Wichtiger Spezialfall: Markov-Prozesse mit stationären (zeitlich
translationsinvarianten) Übergangswahrscheinlichkeiten:
\begin{equation}
 p(x_n,t_n\vert x_k,t_k)=p_t(x_n\vert x_k);\quad
t=t_n-t_k
\end{equation}
\textbf{\hl{Jetzt:}} zeitdiskreter Fall mit $t_n=n$ und stationären
Übergangswahrscheinlichkeiten. Betrachte speziell einzelnen Zeitschritt:
$p_1(x_{n+1}\vert x_n)\equiv W(x_{n+1}\vert x_n)$
\hl{"`Übergangsrate"'}\\
Es gilt die \hl{Master-Gleichung}:
\begin{equation}
 p_{n+1}(x)=p_n(x)+\intsum_{x'}W(x\vert x')
p_n(x')-\intsum_{x'}W(x',x)p_n(x)
\end{equation}
Die W'verteilung ist genau dann \hl{stationär}, falls sich für jedes $x$ die
Zu- und Abflüsse doe Waage halten.\\
Hinreichende Bedingung für die Stationarität einer gewünschten 
Gleichgewichtsverteilung $p_{eq}(x)$ ist die\\
\hl{Detailliertes Gleichgewicht:} $\displaystyle\frac{W(x\vert x')}
{W(x'\vert x)}=\frac{p_{eq}(x)}{p_{eq}(x')}
\quad\forall x,x'$\\
\hl{Markov-Ketten-Monte-Carlo-Algorithmen} konstruieren Markov-Ketten, für
die (i) eine vorgegebene W'verteilung stationär ist (detailliertes
Gleichgewicht wird erfüllt) und die (ii) ergodisch sind (alle Zustände
mit $p_{eq}(x)>0$ sind erreichbar).\\
\textbf{Vereinfachung:} betrachte in jedem Zeitschritt nur "`Umgebung"'
von gegebenem Zustand $x$. Teile dazu auf:
\begin{equation}
 W(x'\vert x)=W_{\textrm{Vorschlag}}(x'\vert x)
W_{\textrm{Akzeptanz}}(x'\vert x)
\end{equation}
und wähle Vorschlagsw' symmetrisch: $W_\textrm{Vorschlag}(x'\vert x)
=W_{\textrm{Vorschlag}}(x\vert x')$
\begin{beispiel}{}
 Intervall/Hyperkubus im kontinuierlichen Fall, z.B. $W_{\textrm{Vorschlag}}
(x'\vert x)=\frac{1}{a}\Theta(\frac{a}{2}-(x-x')
)$ oder Einzel-Spin-Flip im Ising Modell
\end{beispiel}
Dann reicht detaillierte Gleichgewicht für die Akzeptanzraten aus.
Möglichkeiten:
\begin{enumerate}
 \item $\displaystyle W_{\textrm{Akzeptanz}}(x'\vert x)=\min
\bigg\lbrace 1,\frac{p_{eq}(x')}{p_{eq}(x)}\bigg\rbrace$
\hl{Metropolis-Regel}
 \item $\displaystyle W_{\textrm{Akzeptanz}}(x'\vert x)=\frac{p_{eq}
(x')}{p_{eq}(x)+p_{eq}(x')}$ \hl{heat bath}
\end{enumerate}
BILD\\
Dabei hat der Metropolis-Algorithmus den Vorteil der höchstmöglichen
Akzeptanzrate, der heat bath Alhorithmus stellt dagegen instantan das lokale
Gleichgewicht her.\\
\hl{Allgemeiner Metropolis-Algorithmus} (Vorschlagsw' nicht notwendig
symmetrisch):
\begin{equation}
 W_{\textrm{Akzeptanz}}(x'\vert x)=\min\lbrace 1,r\rbrace
;\; r=\frac{p_{eq}(x')}{p_{eq}(x)}\frac{
W_{\textrm{Vorschlag}}(x\vert x')}{W_{\textrm{Vorschlag}}
(x'\vert x)}
\end{equation}
Beachte: Im Grenzfall optimaler Vorschlagsw' werden alle Vorschläge akzeptiert.\\
Typische Realisierung des Metropolis-Algorithmus in der (klassischen)
Statistischen Physik:\\
Boltzmanngewicht $p_i\propto e^{-\beta E_i}$ für Zustand $i$ mit Energie
$E_i\;(\beta=(k_BT)^{-1})$
\begin{enumerate}
 \item[0.] Initialisiere Konfiguration
 \item Wähle Teilchen (in Kontinuum oder auf Gitter) bzw. Spin $n$ aus 
$(1\leq n\leq N)$ - entweder zufällig oder bei jedem Durchgang
(sweep) alle in fester Reihenfolge.
 \item Schlage Veränderung von Teilchen $n$ vor: Umklappen oder Verdrehen
des Spins, Hüpfen oder Verschieben des Teilchens; berechne Energiedifferenz
$\Delta E$
$$r=e^{-\beta\Delta E}\frac{W_{\textrm{Vorschlag}}(x_{neu}\vert x_{alt}
)}{W_{\textrm{Vorschlag}}(x_{alt}\vert x_{neu})}$$
\item Akzeptiere Update mit W' $\min\lbrace 1,r\rbrace$, sonst
behalte alte Konfiguration.
\item Messe Observablen (z.B. Ausgabe in Datei)\\
\\
wenn \# sweeps erreicht:
\item Berechne Mittelwerte mit Standardabweichung, Verteilungen, $\ldots$
\end{enumerate}
\hl{Wichtig:} (i) Die ersten Durchgänge, bei denen die W'-verteilung noch
zu weit von der Stationaität entfernt ist, dürfen nicht für
Observablenmittelwerte verwendet werden.\\
Typische Wahl: 1\%-10\% warm-up sweeps.\\
(ii) Zustandssumme/Freie Energie nicht messbar!

\section{Statistische Physik im kanonischen Ensemble}
Zustandssumme: $\displaystyle Spur\lbrace e^{-\beta\hami}\rbrace;
\;\beta=\frac{1}{k_BT}$\\
Hamiltonoperator $\hami$, z.B. für Ising-Modell (mit Magnetfeld):
\begin{equation}
 \hami_{\textrm{Ising}}=-J\sum_{\langle ij\rangle}\sigma_i\sigma_j
-\mu_BB\sum_i\sigma_i
\end{equation}
Im klassischen Fall bzw. für diagonalisierbares $\hami$ lässt sich die
Zustandssumme vereinfachen:
\begin{equation}
 Z=\sum_{\substack{\textrm{alle}\\ \textrm{Zustände}}}e^{-\beta\hami_i}
\end{equation}
Allg. Mittel/Erwartungswerte: $\displaystyle\langle O\rangle=
\frac{1}{z}\sum_i O_ie^{-\beta\hami_i}$\\
Helmholtzsche Freie Energie: $\displaystyle F=-k_BT\ln Z$\\
Innere Energie:
\begin{eqnarray}
 E&=&\langle\hami\rangle=\frac{\sum_{i} \hami_{i} e^{-\beta\hami_{i}}}
{\sum_ie^{-\beta\hami_i}}=\frac{-\frac{\partial Z}{\partial\beta}}{Z}\\
&=&-\frac{\partial(\ln Z)}{\partial\beta}=\frac{\partial(\beta
F)}{\partial\beta}=F+\beta\frac{\partial F}{\partial\beta}\\
&\stackrel{\frac{\partial\beta}{\partial T}=-\frac{1}{k_BT}}{=}&F-T
\frac{\partial F}{\partial T}=F-TS
\end{eqnarray}
Entropie: $\displaystyle S=-\frac{\partial F}{\partial T}$\\
Spezifische Wärme: $\displaystyle C=\frac{\partial E}{\partial T}=\frac{
\partial E}{\partial\beta}\frac{\partial\beta}{\partial T}=\frac{\langle
\hami^2\rangle-\langle\hami\rangle^2}{k_BT^2}$
Sehr nützlich in MC-Kontext, erspart numerische Differentiation.\\
Magnetisierung (hier konkret für Ising-Modell):
\begin{equation}
 m=\langle\mu_B\sum_i\sigma_i\rangle=\frac{1}{\beta}\frac{
 \partial(\ln Z)}{\partial\beta};\quad M=\frac{m}{N\mu_B}
\end{equation}
\hl{Phasenübergänge:} Singularitäten thermodynamischer Größen (an
Punkten/Linien/Flächen im Phasenraum)\\
Klassifikation nach Ehrenfest ($F$ immer stetig)
\begin{tabbing}
\hl{Übergang 1. Ordnung:} \= 1. Ableitung von F unstetig\\
\hl{Übergang 2. Ordnung:} \> 1. Ableitung von F stetig, 2. Ableitung unstetig
(ggf. auch divergent)
\end{tabbing}
\hl{Beachte:} In Systemen mit einer endlichen Zahl von Zuständen können keine
Phasenübergänge auftreten:
\begin{equation}
 Z=\sum_{s=1}^{s_{max}<\infty}e^{-\beta\hami_s}\quad\textrm{ist analytisch.}
\end{equation}
Daher ist bei MC-Untersuchungen zu Phasenübergängen i.A. eine sorgfältige
Finite-Size-Analyse essentiell.\\
\hl{Kritische Exponenten} charakterisieren Systeme in der Nähe von Übergangen
2. Ordnung, sind \hl{universell}!
\begin{equation}
\left.\begin{array}{ll}
 \textrm{Magnetisierung} & m=m_0\epsilon^{\beta}\\
 \textrm{Suszeptibilität} & \chi=\chi_0\epsilon^{-\gamma}\\
 \textrm{Spez. Wärme} & C=C_0\epsilon^{-\alpha}\\
 \textrm{Korrelationslänge} & \xi=\xi_0\epsilon^{-\gamma}\\
 \textrm{Magnetisierung bei }T_c & m\propto B^{\frac{1}{\delta}}
\end{array}
\right\rbrace\epsilon=\Big\vert1-\frac{T}{T_c}\Big\vert
\end{equation}
\section{Das Ising-Modell}
Model of interacting quantum spins in a magnetic field, intduced as model for
ferromagnetism by \person{Wilhelm Lenz}{} ($\sim$ Runge-Lenz vector) and
\person{Ernst Ising}{10.5.1900-11.5.1998} in Ising's PhD thesis (Hamburg 1924).
\\
Ising later became teacher, emigrated via Luxemburg to the USA. After
Onsager's solution (1944) he became professor at Bradley university, Peoria,
Illinois, but never published another Journal article.\\
Hamiltonian of general Ising model (N lattice sites):
\begin{equation}
 \hami=-\frac{1}{2}\sum_{i,j=1}^NJ_{ij}\sigma_i\sigma_j-\mu_BB\sum_{i=1}^N
\sigma_i\quad\sigma_i\in\lbrace+1,-1\rbrace
\end{equation}
specifically for translation-invariant, isotropic nearest-neighbor
interaction:
\begin{equation}
 \hami=-J\sum_{\langle ij\rangle}\sigma_i\sigma_j-\mu_BB\sum_i
\sigma_i
\end{equation}
sum over NN pairs, each pair counted once
\begin{itemize}
 \item important special case: $B=0$
 \item trivial single-spin (noninteracting) limit: $J=0$
 \item ferromagnetic/antiferromagnetic coupling for $J<>0$
 \item properties strongly dependent on lattice (i.e. also on dimensionality)
\end{itemize}
more general spin Hamiltionian:
\begin{equation}
 \hami=-\frac{1}{2}\sum_{ij}\vec{S}_i\cdot\tensor{I}_{ij}\cdot \vec{S}_j
\end{equation}
\begin{tabbing}
 (isotropic) \= Heisenber model: \= $\tensor{I}_{ij}=I_{ij}\mathbf{1}$\\
\>Ising model:\> $(I_{ij})_{\mu\nu}=I_{ij}\delta_{\mu3}\delta_{\nu3}$\\
use scaled interactions\>\> $J_{ij}=(\half\hbar)^2I_{ij}$
\end{tabbing}
possible visualization: BILD\\
alternative visualizations: BILD\\
closely related: lattice gas model (lattice sites occupied/empty):
\begin{equation}
 \hami_{LGM}=U_{NN}\sum_{\langle ij\rangle}n_in_j-\mu\sum_in_i;\quad
n_i\in\lbrace0,1\rbrace
\end{equation}
$\mu$: chemical potentoaö (in grand canonical ensemble)

\subsection{Mean-field solution of the Ising model}
Mean-field approximation: correlations of the form $\big\langle(\sigma_i-
\langle\sigma_i\rangle)(\sigma_j-\langle\sigma_j\big\rangle)
\rangle$ are neglected.\\
For homogeneous case ($\langle\sigma_i\rangle=\langle\sigma_j\rangle\equiv
\langle\sigma\rangle=M$)
\begin{eqnarray}
 \hami&=&-J\sum_{\langle ij\rangle}\sigma_i\sigma_j-B\sum_i\sigma_i\\
&\approx&\hami_{MF}=-J\sum_i\sigma_i\sum_{\substack{j\\j\:\textrm{NN. of}\:i}}
\langle\sigma\rangle-B\sum_i\sigma_i\\
&=&-\underbrace{(B+qJ\langle\sigma\rangle)}_{B_{eff}}\sum_i\sigma_i
\end{eqnarray}
$q$: coordination number (\# of nearest neighbors)\\
effective single-spin Hamiltonian with self-consistency condition
\begin{tabbing}
 $\Rightarrow$ partition function $\displaystyle Z$ \= $\displaystyle=\bigg(
\sum_{\sigma_i=\pm1}\exp\Big(\sigma_i\frac{B+qJ\langle\sigma\rangle}{k_BT}
\Big)\bigg)^N$\\ \> $\displaystyle=\bigg(2\cosh\frac{B+qJ\langle\sigma
\rangle}{k_BT}\bigg)^N$
\end{tabbing}
$\Rightarrow$ magnetization $\displaystyle M=\langle\sigma\rangle=\tanh\frac{
B+qJ\langle\sigma\rangle}{k_BT}$
graphical solution:\\
BILD\\
\subsection{Ising model: solution in 1 dimension}
(i) simple case: open chain, no magnetic field
\begin{eqnarray}
 \hami&=&-J\sum_{i=1}^{N-1}\sigma_i\sigma_{i+1}=-J\sum_{i=2}^N\sigma_{i-1}
\sigma_i\\ Z&=&\sum_{sigma_i=\pm1}\sum_{\sigma_2=\pm1}\ldots
\sum_{\sigma_N=\pm1}e^{-\beta\hami\lbrace\sigma_e\rbrace}
\end{eqnarray}
Trick: introduce new variables $\lbrace s_i\rbrace$ with
\begin{equation}
 s_1=\sigma_1;\;s_i=\sigma_i\sigma_{i-1}\;\textrm{for}\;i\geq2\;\big(
\Rightarrow\sigma_i=\prod_{j=1}^is_i\big)
\end{equation}
\begin{eqnarray}
 \Rightarrow\hami&=&-J\sum_{i=2}^N\\
Z&=&\big(\sum_{s_1=\pm1}\big)\big(\sum_{s_2=\pm1}e^{-\beta Js_2}\big)\big(
\sum_{s_3=\pm1}e^{-\beta Js_3}\big)\ldots\big(\sum_{s_N=\pm1}e^{-\beta Js_N}
\big)\\&=&2\big(2\cosh(\beta J)\big)^{N-1}=2^N\lbrack\cosh(\beta
J)\rbrack^{N-1}\\
\Rightarrow E(\beta)&=&-\frac{\partial\ln Z}{\partial\beta}=-(
N-1)\tanh(\beta J)\\
 E(T)&=&-(N-1)J\tanh\Big(\frac{J}{k_BT}\Big)
\end{eqnarray}
$\infty$ often differentiable for all $0<T<\infty\;\rightarrow$ no finite-T
phase transition\\
(ii) more relevant case: periodic boundary conditions (+magnetic field)\\
BILD
\begin{equation}
 \hami=-J\sum_{i=1}^N\sigma_i\sigma_{i+1}-\mu_BB\sum_{i=1}^N\sigma_i
\end{equation}
Treat using bond transfer matrices ($2\times2$), see\\
LINK
\begin{eqnarray}
 \Rightarrow Z =(p^+)^N+(p^-)^N\;\textrm{where}\\
p^{\pm}=e^{\beta J}\cosh(\beta\mu_BB)\pm\sqrt{e^{2\beta J}\sinh^2
(\beta\mu_BB)+e^{-2\beta J}}
\end{eqnarray}
magnetization (in thermodynamic limit):
\begin{equation}
 M=\frac{\sinh(\beta\mu_BB)}{\sqrt{\sinh^2(\beta\mu_BB)
+e^{-4\beta J}}};\;m=N\mu_BM
\end{equation}
no finite-temperature magnetism: $m\stackrel{B\rightarrow0}{\longrightarrow}0$ 
for $T>0$\\
(but ground state fully polarized: $m=\pm N\mu_B$ for $T=0$)\\
On the basis of these results, Ising and Lenz discarded the model as irrelevant
for (finite T) magnetism.

\subsection{Ising model on the 2d square lattice}
Combination of high- and low-temperature expansions (\referenz{Kramers, Wannier,
 1941}) using duality
\begin{equation}
 \Rightarrow\frac{J}{k_BT_c}=\half\arcsinh(1)=\half\ln(\sqrt{2}
+1)\approx0.4407
\end{equation}
$$T_c\approx2.2692\frac{J}{k_B}$$
Critical exponents: $\alpha=0,\;\beta=\frac{1}{8},\;\gamma=\frac{7}{4},\;
\delta=15$\\
For details, see Thermodynamics script by \referenz{P. van Dongen} and LINK

\subsection{Ising model: simulation}
$1^{st}$ consideration: Hamiltonian for finite-size system, i.e. \hl{boundary
conditions}\\
BILD
\begin{enumerate}
 \item conventional choice: periodic boundary conditions $\Rightarrow$ all
sites equivalent
\item other extreme: open/free edge boundary conditions $\Rightarrow$ inner +
surface sites
\item screw periodic boundary conditions easy to implement on $1d$ vector
$\Rightarrow$ introduces seam
\item antiperiodic boundary conditions: flip sign of interaction along some
boundaries $\Rightarrow$ generate odd number of domain walls (e.g. 1) at
$T\rightarrow1$
\item fixed or mean-field boundary conditions: boundary sites couple to
external medium
\end{enumerate}
Possibilities can be combined/mixed $\ldots$

\subsection{Metropolis importance sampling Monte Carlo scheme}
\begin{enumerate}
 \item[0.] choose initial spin configuration
\item select site $i$
\item calculate $\Delta E=E\lbrace\sigma_{l_i}\sigma_i\rightarrow-\sigma_i
\rbrace-E\lbrace\sigma_l\rbrace$
\item Metropolis step:
\begin{itemize}
 \item if $\Delta E<0$: accept move
 \item else generate random number $r\in\lbrack0,1)$
\begin{itemize}
 \item if $\displaystyle r<\exp\lbrack-\frac{\Delta E}{k_BT}\rbrack$: flip
spin ($\sigma_i\rightarrow-\sigma_i$)
\item else: keep state
\end{itemize}
\end{itemize}
\item after warm-up: measure\\
compute internally or print out for external analysis:
\begin{eqnarray}
 n_{sum}&+=&1\\
 m_{sum}&+=&mag\lbrace\sigma_l\rbrace\\
 E_{sum}&+=&E\lbrace\sigma_l\rbrace\\
&\vdots
\end{eqnarray}
\item enough sweeps ($N=L^d$ attempted spin flips)?
\begin{itemize}
 \item yes: compute averages + error bars (if done internally)
 \item no: return to step 1.
\end{itemize}
\end{enumerate}
\textbf{note:} $\;\Delta E$ depends only on nearest neighbors of site $i$,
specifically only on number of upspins in neighborhood (and $\sigma_i$)
$\rightarrow$ look-up table possible

\subsection{Ising-Modell (NN-Wechselwirkung) - Kritische Temperaturen}
\begin{table}[h]
\begin{tabular}{c|c|c|r @{.} l|r @{.} l}
 \textbf{dim} & \textbf{lattice} & $\mathbf q$ & \multicolumn{2}{c|}{
$\mathbf{\frac{k_BT_c}{J}}$} & \multicolumn{2}{c}{$\mathbf{\frac{k_BT_c}
{Jq}}$}\\
1 & chain/ring & 2 & \multicolumn{2}{c|}{0} & \multicolumn{2}{c}{0}\\
2 & honeycomb & 3 & $\sim$1&52 & $\sim$0&5\\
& square & 4 & 2&269 & 0&57\\
& triangular & 6 & $\sim$3&64 & $\sim$0&61\\
3 & diamond & 4 & $\sim$2&704 & $\sim$0&68\\
& cubic & 6 & $\sim$4&512 & $\sim$0&75\\
& bcc & 8 & $\sim$6&35 & $\sim$0&79\\
& fcc & 12 & $\sim$9&79 & $\sim$0&82\\
4 & hypercubic & 8 & $\sim$6&68 & $\sim$0&84\\
$\infty$ & "' & $\infty$ & \multicolumn{2}{c|}{$\infty$} & 1&0
\end{tabular}
\caption{Most values taken from \referenz{Peter Meyer. PhD Thesis, University
of Derby (2000)} LINK}
\end{table}
\textbf{Note:} \begin{itemize}
 \item phase transition for all lattices in $d>1$
 \item $T_c\stackrel{q\rightarrow\infty}{\longrightarrow}\frac{Jq}{k_B}$ 
(coordination number $q$)
\end{itemize}

\subsection{Kritische Exponenten des Ising-Modells in d=3}
\begin{eqnarray}
 \alpha=0.110(1); & \beta=0.3265(3); & \gamma=1.2372
(5);\nonumber\\
\delta=4.789(2); & \nu=0.6301(4); & \eta=0.0364(5
);\;\omega=0.84(4)\nonumber
\end{eqnarray}
\referenz{Pelissetto, Vicari, Physics Reports 386, 549 (2002)} LINK\\
(zum Vergleich: \hl{mean field}, d.h. $d\geq4$: $\;\alpha=0,\beta=\half,
\gamma=1,\nu=\half$ und nochmal $d=2$: $\alpha=0,\beta=\frac{1}{8},\gamma=
\frac{7}{4},\delta=15$)

\section{Finite-size scaling}
Ziel des \hl{finite-size scaling (FSS)} ist die Extrapolation des kritischen
Verhaltens im thermodynamischen Limes aus den (nichtsingulären) Eigenschaften
endlicher Systeme.
\begin{swort}{Grundhypothese}
 für den singulären Anteil der Freien Energie ist nahe dem Phasenübergang 2.
Ordnung die \hl{relevante Längenskale durch die Korrelationslänge $\xi$
gegeben, \hl{nicht}} durch mikroskopische Längenskalen (mittlerer
Teilchenabstand, Gitterperiode etc.). Charakteristisch für die Größe eines
hyperkubischen Systems mit Volumen $V=L^d$ ist also das Verhältnis $\frac{L}
{\xi}$ von Ausdehnung zu Korrelationslänge und es gilt für die Dichte (des
singulären Anteils) der Freien Energie in führender Ordnung:
\begin{eqnarray}
 f^{(s)}(L,T)&=&\frac{1}{V}F^{(s)}(L,T
)\approx\frac{1}{V}\tilde{\Psi}\Big(\frac{L}{\xi(T)}\Big),
\quad\textrm{wobei}\\
&&\xi(T)=\xi_0\epsilon^{-\nu};\;\epsilon=\Big\vert1-\frac{T}{T_c}
\Big\vert
\end{eqnarray}
\end{swort}
\begin{tabbing}
 $\Rightarrow$ \= dimensionslose Länge \= $\displaystyle\frac{L}{\xi}=
\xi_0^{-1}\epsilon^\nu L$\\
\> Reskalierung:\>$\displaystyle\Big(\frac{L}{\xi}\frac{\xi_0}{L_0}\Big)^{
\frac{1}{\nu}}=\epsilon\Big(\frac{L}{L_0}\Big)^{\frac{1}{\nu}}$\\
\> $\displaystyle\Rightarrow f^{(s)}(L,T)\approx L^{-d}
Y(C,\epsilon L^{\frac{1}{\nu}},0)$
\end{tabbing}
Für die Kopplung an das Magnetfeld nimmt man an, dass dieses effektiv durch
eine Potenz von $\xi$ verstärkt wird, da (für das ferromagnetische Modell)
Bereiche mit Radius $\xi$ schon nahezu parallel ausgerichtet sind:
\begin{equation}
 \Rightarrow f^{(s)}(L,T,B)=L^{-d}Y\lbrack C,\epsilon L^{
\frac{1}{\nu}},C_2BL^{\frac{\beta+\gamma}{\nu}}\rbrack
\end{equation}
\referenz{V. Privman, M.E. Fisher, PRB 30, 322 (1984)} LINK\\
Dabei sind alle Exponenten und die Funktion $Y$ nur von der 
Universalitätsklasse abhängig (insbesondere von den DImensionen von Raum und
Ordnungsparameter).\\
Es lassen sich nun Skalierungsgleichungen für die Observablen ableiten, z.B.
(geschrieben für $L_0\equiv1$):
\begin{eqnarray}
 M(L,T)&=&\tilde{M}(\epsilon L^{\frac{1}{\nu}})L^{-\frac{
\beta}{\nu}}\\
\chi(L,T)&=&\tilde{\chi}(\epsilon L^{\frac{1}{\nu}})
L^{\frac{\gamma}{\nu}}\\
C(L,T)&=&\tilde{C}(\epsilon L^{\frac{1}{\nu}}) L^{\frac{
\alpha}{\nu}}
\end{eqnarray}
Hier wurden teilweise Skalenbeziehungen zwischen den Exponenten benutzt:
\begin{tabbing}
 $\alpha+2\beta+\gamma=2$ \= Rushbrooke \= $\gamma=\beta(\delta-1)$
 \= Widom\\
$d\nu=2-\alpha$\> Josephson \> $\gamma=\nu(2-\eta)$\> Fisher
\end{tabbing}
Die Funktionen $\tilde{M},\tilde{\chi},\tilde{C}$ etc. lassen sich wiederum
durch Ableitungen der universellen Funktion $Y$ und die nichtuniversellen
Koeffizienten $C_1,C_2$ ausdrücken.\\
\begin{swort}{Beachte}
 \begin{enumerate}
 \item die Skalengesetze gelten nur asymptotischfür $\epsilon\rightarrow0$ und
$B\rightarrow0$, in der Praxis können die Korrekturen (corrections to scaling)
signifikant sein.
\item Im Allgemeinen kommen noch reguläre Anteile hinzu.
\item Phasenübergänge 1. Ordnung erfordern weitergehende Analyse
\end{enumerate}
$\;$
\end{swort}
\begin{swort}{Praktische Anwendung}
 Um kritische Exponenten zu testen und nichtuniverselle Koeffizienten zu
bestimmen, müsste man laut FSS skalierte Observablen gegen skalierte Parameter
auftragen, z.B.
\begin{equation}
 \tilde{M}_L(x),\;\textrm{wobei}\;\tilde{M}_L=M_L L^{\frac{\beta}
{\nu}};\;x=\epsilon L^{\frac{1}{\nu}}
\end{equation}
Dabei sollten die Kurven asymptotisch kollabieren: $\displaystyle \tilde{M}
(x)=\lim_{L\rightarrow\infty}\tilde{M}_L(x)$ jeweils
seperat für $T<T_c$ und $T>T_c$.
\end{swort}
\\
\begin{problem}
 \begin{enumerate}
 \item die Abbildung $T\rightarrow\epsilon=\vert1-\frac{T}{T_c}
\vert$ erfordert die Kenntnis von $T_c$ (nichtuniversell)
\item Exponenten i.A. unbekannt oder nur ungenau bekannt.
\end{enumerate}$\;$
\end{problem}
\begin{swort}{Lösung}
 Bestimmt $T_c$ aus Observablen, deren Betrag nicht von $L$ renormiert wird,
die also nur im Argument von $L$ abhängen. Beipiel: aus
\begin{equation}
 \langle m^2\rangle\propto(L^dL^{-\frac{\beta}{\nu}})^2\;
\textrm{und}\; \langle m^4\rangle\propto(L^dL^{-\frac{\beta}{\nu}}
)^4
\end{equation}
konstruiere skalierungsfreien Quotienten
\begin{equation}
 \frac{\langle m^4\rangle}{\langle m^2\rangle^2}\propto(L^{d-\frac{\beta}
{\nu}})^{4-2\cdot2}=L^0
\end{equation}
bzw. die \hl{Binder-Kumulante} $U_4=1-\frac{\langle m^4\rangle}{4\langle m^2
\rangle}$ mit $U_4(L,T)=\tilde{U}_4(x)$\\
Trägt man nun Kurven $U_4(T)$ für verschiedenes $L$ gemeinsam auf,
schneiden sich diese asymptotisch für $T=T_c$ (und werden abseits mit
verschiedenen Faktoren $L$ horizontal gedehnt.
\end{swort}
\begin{beispiel}{für 2D Ising-Modell}
 BILD\\
Es gilt: $\displaystyle U_4\stackrel{L\rightarrow\infty}{\longrightarrow}
\left\lbrace\begin{array}{ccc}
 \frac{2}{3} & \textrm{für} & T<T_c\\
U^*\approx0.61 & \textrm{"'} & T=T_c\\
0 & \textrm{"'} & T>T_c
\end{array}\right.$\\
Sobald $T_c$ bekannt ist, können Exponenten z.B. aus logarithmischen
Auftragungen bestimmt werden, hier für $\beta$:\\
BILD
\end{beispiel}

\section{Cluster-MC-Algorithmen}
bisher: lokale Monte-Carlo-Schritte (single spin flips)
\begin{problem}
 Autokorrelationszeiten ind groß nahe $T_c$, divergieren (bei $T_c$) für
$L\rightarrow\infty$: \hl{critical slowing down}\\
Quantitativ: $\tau\propto\xi^z$ mit $z\approx2.125$
\end{problem}
\begin{swort}{Ursache}
BILD\\
 große Cluster gleich ausgerichteter Spins sind stabil gegen lokale spin
flips im Inneren, nur an der Oberflächesind Akzeptanzraten signifikant:\\
Kosten für spin-flip im Inneren eines 
\begin{tabbing}
 großen Clusters: $\quad$ \= $\Delta E=4DJ$\\
 Kosten am Rand: \> $\Delta E=4J$
\end{tabbing}
Bei $T\approx T_c$ ändert sich die Gesamtkonfiguration daher in erster Linie
durch Verschiebungen der Clustergrenzen, was näherungsweise dem Wandern einer
Hyperfläche ($D-1$ Dimensionen) in $D$ Dimensionen bzw. einem random walk in
einer Dimension entspricht. Für unabhängige Konfigurationen müssen sich die
Domänenwände um eine Distanz $\xi$ bewegt haben, was idealisiert $\xi^2$
Single-spin-flips erfordert ($\tau\propto\xi^z$ mit $z=2$). Genauer: $z\approx
2.125$
\end{swort}
\begin{swort}{Aber}
 der kritische Exponent ist spezifisch für die Monte-Carlo-Prozedur und kann
verbessert werden!
\end{swort}
\begin{idee}
 ganze Cluster können (fast) frei umgeklappt werden ($\Delta E\propto\ln
(N_{\textrm{Cluster}})$) $\rightarrow$ Cluster-Updates!
\end{idee}
\begin{swort}{Vorüberlegung}
 welche Cluster sollen Umklapp-Kandidaten sein? Jeweils alle zusammenhängenden
Spins gleicher Orientierung? \hl{Nein}, sonst könnten Cluster nur wachsen,
jede Simulation würde zur vollen Polarisation getrieben (Verletzung aller 
Gleichgewichtsbeziehungen)
\end{swort}
\begin{swort}{Also}
 wie Cluster auswählen, nach welchen Regeln Spins invertieren?
\end{swort}
Abbildung des Ising Modells (allgemeiner: q-state Potts model) auf ein
Perkulations-Modell:
\referenz{P.W. Kasteleyn and C.M. Fortuin, J. Phys. Soc. Jpn. Suppl. 26s, 11
(1969); C.M. Fortuin and P.W. Kasteleyn, Physica (Utrecht) 57,536 (1972)}, LINK
\begin{eqnarray}
 Z&=&\sum_{\lbrace\sigma_i\rbrace}\exp\lbrack\beta\sum_{i,j}\sigma_i\sigma_j
\rbrack\quad\quad (J=1)\\
&=&\sum_{\lbrace\sigma_i\rbrace}\prod_{\langle ij\rangle}e^{\beta\sigma_i
\sigma_j}\\
&=&\sum_{\lbrace\sigma_i\rbrace}\prod_{\langle ij\rangle}e^{\beta}\big\lbrack(
1-p)+p\delta_{\sigma_i\sigma_j}\big\rbrack;\quad p\equiv1-e^{-2\beta}
\end{eqnarray}
Um uns von der Korrektheit zu überzeugen, müssen wir nur die möglichen Werte
$\sigma_i\sigma_j$ einsetzen:
\begin{eqnarray}
 \sigma_i\sigma_j=1&\Rightarrow&e^{\beta}\big\lbrack(1-p)+p\delta_{
\sigma_i\sigma_j}\big\rbrack=e^{\beta}=e^{\beta\sigma_i\sigma_j}\\
\sigma_i\sigma_j=1&\Rightarrow&e^{\beta}\big\lbrack(1-p)+p\delta_{
\sigma_i\sigma_j}\big\rbrack=e^{\beta}(1-p)=e^{\beta}\big\lbrack 1-(
1-e^{-2\beta})\big\rbrack\\
&&=e^{-\beta}=e^{\beta\sigma_i\sigma_j}
\end{eqnarray}
Beachte: $0\leq p\leq1$ "`riecht"' nach Wahrscheinlichkeit.\\
Wir formen $Z$ weiter um; mit $\displaystyle\sum_{n=0}^1\lbrack a\delta_{n,0}+
b\delta_{n,1}\rbrack=a+b$ gilt:
\begin{equation}
 Z=\sum_{\lbrace\sigma_i\rbrace}\sum_{\lbrace n_{ij}\rbrace}\prod_{\langle ij
\rangle}e^{\beta}\big\lbrack(1-p)\delta_{n_ij,0}+p\delta_{\sigma_i
\sigma_j}\delta_{n_{ij},1}\big\rbrack
\end{equation}
Zusätzlich zu den Spin-Variablen $\sigma_i$ wurden hier Bond-Raviablen $n_{ij}$
eingeführt. Letztere können nur zwischen (Nachbar-) Spins gleicher Orientierung
"`gesetzt"' ($n_{ij}=1$) sein - mit Wahrscheinlichkeit $p$.\\
\begin{beispiel}{2 Spins}
 \begin{tabular}{ccccl}
$\sigma_1$&$\sigma_2$&$n_{12}$&Bild&Beitrag zu $Z$\\
 +1&+1&0&$\uparrow\uparrow$&$e^{\beta}(1-p)$\\
+1&+1&1&$\uparrow\hspace{-7pt}-\hspace{-7pt}\uparrow$&$e^{\beta}p$\\
+1&-1&0&$\uparrow\downarrow$&$e^{\beta}(1-p)$\\
+1&-1&1&$\uparrow\hspace{-7pt}-\hspace{-7pt}\downarrow$&0
\end{tabular}
Bei gleichen Spins: relative W' für bond ist $p$\\
Bei nicht-verbundenen Spins gleicher Beitrag: Spin-flip "`kostenlos"'\\
Letzter Fall: kein Beitrag $\rightarrow$ darf nicht auftreten
\end{beispiel}

\subsection{Swendson-Wang Cluster-Update-Algorithmus}
\begin{enumerate}
 \item[0.] Initialisierung der Spin-Konfiguration (z.B. zufällig)
\item Bond-update: für alle Nächst-Nachbar-Paare $\langle i,j\rangle$, setze
$$n_{ij}=\left\lbrace\begin{array}{cl}
 1&\;\textrm{falls}\;\sigma_i=\sigma_j\;\textrm{und}\;r<p=1-e^{-2\beta J}\\
0&\textrm{sonst}
\end{array}\right.$$
\item Spin-update: Finde alle CLuster durch Bonds verbundener Spins und weise
ihnen je zufällig neue Orientierung zu.
\item Messung von Observablen (nach Warm-up)
\item Weiter mit 1.
\end{enumerate}
\referenz{R.H. Swendsen, J.-S. Wang, Phys. Rev. Lett. 58, 86 (1987)}\\
Man kann das Spin-Update (für feste Bond-Konfiguration) mit einem modifizierten
Ising-Modell assoziieren, in dem die Paarwechselwirkung jeweils entweder
verschwindet (für $n_{ij}=0$) oder unendlich stark ferromagnetisch ist
(für $n_{ij}=1$).\\
Nichttrivialer Implementationsschritt: Finden der S-W-Cluster. Einfacher
SW-bond-update Algorithmus mit Rekursion:
\begin{enumerate}
 \item $\forall$ spins $i$: setze \texttt{visited}$\lbrack i\rbrack=0$
\item $\forall$ spins $i$:
\begin{tabbing}
 setze Variable $\sigma_{neu}$ zufällig\\
\texttt{flip\_cluster}$(i,\sigma_{neu})$\\
\\
\texttt{rou}\=\texttt{tine flip\_cluster}$(i,\sigma_{neu})$\\
\> \texttt{if }\= \texttt{visited}$\lbrack i\rbrack=0$\\
\>\>$\sigma\lbrack i\rbrack=\sigma_{neu}$\\
\>\> \texttt{visited}$\lbrack i\rbrack=1$\\
\>\>$\forall$ Na\=chbarn $j$ von $i$\\
\>\>\> \texttt{flip\_cluster}$(j,\sigma_{neu})$
\end{tabbing}
\end{enumerate}
Effizienter Algorithmus ohne Rekursion: "`cluster multiple labeling technique"'
\\ \referenz{J. Hoshen, R. Kopelman, Phys. Rev. B 14, 3438 (1976)}
\begin{swort}{Prinzip}
 führe Cluster-Label für jeden Spin ein, das angibt, zu welchem Cluster er
gehört, weise am Ende jedem Spin die richtige (Cluster-spezifische)
Orientierung zu. Arbeite systematisch: zeilen+spaltenweise. etc. Dabei
erhält jeder Spin, der mit einem scon besuchten Spin verbunden ist, dessen
Clusternummer, sonst eine neue:\\
BILD\\
\end{swort}
\begin{problem}
 häufig stellt sich nachträglich heraus, dass Spins mit verschiedenen
Clusternummern doch verbunden sind $\rightarrow$ Umbenennung + Buchhaltung
nötig.
\end{problem}
Effizienter und einfacher: \hl{Wolff Cluster-Update} wie Swendson Wang, jedoch
mit Schritt
\begin{enumerate}
 \item[3.'] Wähle zufällig einen Spin $i$ und flippe den zugehörigen Cluster.
\end{enumerate}$\;$
\begin{swort}{Vorteil}
 bevorzugte Updates großer Cluster.
\end{swort}
Beide Cluster-Algorithmen reduzieren die Autokorrelationszeiten gegenüber
Single-spin-flip dramatisch: $\tau\propto\xi^z$ mit $z=0.2-0.5$\\
Besonderheit bei Swendson-Wang: Observablen können über alle möglichen
Einstellungen der Clusterspins gemittelt werden (nicht nur die, welche für die
folgende Iteration benutzt wird), um die statistischen Fehler zu reduzieren.
\begin{beispiel}{Suszeptibilität (ohne Subtraktion von $\langle\vert M\vert
\rangle^2$}
 \begin{eqnarray}
 \chi\propto L^{2d}\langle M^2\rangle&=&\big\langle(\sum_{i=1}^N\sigma_i)^2
\big\rangle\\
&=&\big\langle(\sum_cN_c\sigma_c)^2\big\rangle\\
&&\textrm{Summe über alle Cluster }c\textrm{ mit }N_c\textrm{ Spins,
Orientierung }\sigma_c\\
&=&\Big\langle\big(\sum_cN_c\sigma_c\big)\big(\sum_{c'}N_{c'}\sigma_{c'}\big)
\Big\rangle\\
&=&\Big\langle\sum_{\lbrace\sigma_c=\pm1\rbrace}\big(\sum_cN_c\sigma_c\big)
\big(\sum_{c'}N_{c'}\sigma_{c'}\big)\Big\rangle\\
&=&\langle\sum_cN_c^2\rangle\quad\textrm{"`improved estimator"'}
 \end{eqnarray}
\end{beispiel}
\begin{beispiel}{Energie}
 \begin{equation}
 \langle\hami\rangle=\big\langle\sum_c\langle\hami_c\rangle\big\rangle=-J
\langle\sum_{\langle ij\rangle}n_{ij}\rangle
\end{equation}$\;$
\end{beispiel}
