\documentclass[10pt]{article}
\usepackage{a4wide}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{axodraw}
%\usepackage{epsfig}
%\addtolength{\topmargin}{-65pt}

% Stefan's abbreveations
\def\l{\langle}
\def\r{\rangle} 
\def\g{\gamma}
\def\bq{\begin{eqnarray*}}
\def\eq{\end{eqnarray*}}
\def\bs{\begin{small}}
\def\es{\end{small}}
\newcounter{exercise}
\setcounter{exercise}{1}

\begin{document}

\begin{center}
\section*{Problem sheet 2}
\end{center}

\subsection*{1. Hyperplanes in pseudo-random numbers}
Generate a three- and a two-dimensional plot of points 
$(s_n,s_{n+1},s_{n+2})$ and $(s_n,s_{n+1})$ taken
from the multiplicative linear congruential generator $a=137$, 
$c=187$ and $m=256$. 

\subsection*{2. Out of luck in Monte Carlo}
We are interested in the integral
\bq
I & = & 2 \int\limits_0^1 dx \int\limits_0^1 dy \int\limits_0^1 dz \; \sin^2\left( 2 \pi (9x-6y+z) \right).
\eq
This integral can be solved analytically by doing the $z$-integration first and yields $1$.
Suppose we are ignorant about this possibility 
and perform a brute-force Monte Carlo integration using the
multiplicative linear congruential generator $a=65539$, $c=0$ and $m=2^{31}$.
Innocent as we are we use three consecutive random numbers from the generator to define a point
in the cube: $(x,y,z)_n = (s_{3n}/m, s_{3n+1}/m, s_{3n+2}/m)$.
What do you get ?
In order to see what went wrong show that three consecutive numbers of this generator
satisfy
\bq
\left( 9 s_n - 6 s_{n+1} + s_{n+2} \right) \; \mbox{mod} \; m & = & 0.
\eq
Instead of $m=2^{31}$ you might also take $m=2^{29}$.
To check the implementation of your generator: The first few random
numbers obtained from the seed $s_0=1$ are:
0.0001220759004, 0.0007324386388, 0.003295948729,
0.01318374462, 0.04943892919, 0.1779798735, 0.6229288783,
0.1357544083, 0.2081665453 for $m=2^{29}$.  \\
For $m=2^{31}$ the sequence starts with
0.00003051897511, 0.0001831096597, 0.0008239871822, 0.003295936156,
0.01235973230, 0.04449496837, 0.1557322196, 0.5339386021, 0.8020416363\\
0.006802399177.
                                

\subsection*{3. The Ising model}


The Hamiltonian of the Ising model
is given by
\bq
H_{Ising} & = & - J \sum\limits_{\l i,j \r} S_i S_j,
\eq
where $J>0$ is a constant, $\l i,j \r$ denotes the sum over all next-neighbours
and the spin $S_i$ at site $i$ takes the values $\pm 1$.
Observables are given
by
\bq
\l O \r & = & \frac{\sum O(\phi) e^{-H(\phi)/kT}}{\sum e^{-H(\phi)/kT}},
\eq
where the sum runs over all possible states. One observable is the magnetization $M$
or the order parameter. For the Ising model the magnetization is given by
\bq
M_{Ising} & = & \frac{1}{N} \sum S_i
\eq
Write a Monte Carlo program which simulates the
two-dimensional Ising model on a $ 16 \times 16$ lattice with periodic
boundary conditions using the Metropolis algorithm.
(Note that with a $16 \times 16$ lattice, the total number of states is $2^{256}$. 
This is far too large to evaluate the partition sum by brute force.)
You may initialize the model with all spins up (cold start) or with a random
distribution of spins (hot start).
Step through the 256 spins one at a time making an attempt to flip the current spin.
Plot the absolute value of the magnetization for various values of $K=J/kT$ between
$0$ and $1$. Is anything happening around $K=0.44$ ?




\end{document}

\subsection*{4. Flower power}
To work on this problem is facultativ. It deals with data clustering and shows
an application of the Potts model.
Given a set of data (for example as points in a $d$-dimensional vector space), 
cluster analysis tries to group this data into clusters, such that the members
in each cluster are more similar to each other than to members of different
clusters. An example is an measurement of four different quantities from 150 Iris flowers.
(In this specific example it was known that each flower belonged to exactly one subspecies
of the Iris: either Iris Setosa, Iris Versicolor or Iris Virginica.
The four quantities which were measured are the petal length, the petal width, the sepal length
and the sepal width.)
Given the data points alone, the task is to decide which flowers belong to the same subspecies.)
M. Blatt et al. suggested to use the Potts model for this problem as follows:
Given $N$ points $x_i$ in a $d$-dimensional vector space one chooses a value $q$ for the number
of different spin states and a model for the spin-spin couplings $J_{ij}=f(d_{ij})$, where
$d_{ij}$ is the distance between the points $x_i$ and $x_j$ and $f$ a function depending on the 
distance $d_{ij}$. To minimize computer time one usually
chooses $f(d_{ij})=0$ for $d_{ij}>d_{cut}$.
One then performs a Monte Carlo simulation of the corresponding Potts model. At low temperature
all spins are aligned, where as at high temperature the orientation of the spins is random.
In between there is a super-paramagnetic phase, where spins are aligned inside ``grains'', but the
orientation of different grains is random.
Using the Swendsen-Wang algorithm one first tries to find this super-paramagnetic phase by
monitoring the magnetic susceptibility (there should be a strong peak in $\chi$ at the
ferromagnetic-superparamagnetic phase transition, furthermore, at higher temperature there will
be a significant drop in the susceptibility where the alignment of the spins inside a grain
break up.)
Having found the right temperature one then calculates the probability that two neighbouring sides
are in one Swendsen-Wang cluster.
If this probability is greater than $1/2$ they are assigned to the same data cluster.
The final result should depend only mildly on the 
exact value of $q$ and the functional form of $f(d_{ij})$. This can be verified by performing the simulation
with different choices for these parameters.
Write a Monte Carlo simulation which clusters the data accoridng to the algorithm outlined above.
You can find the data for the Iris flowers on the web, for example
at http://www.math.uah.edu/stat/data/Fisher.html.