%% ================================================================
\section{An overview of the Metropolis-Hastings algorithm}
\label{sec:ising}

Here we summarize the Metropolis-Hastings algorithm for handy reference, with
no attempt to prove correctness.  More thorough discussions of the algorithm
may be found in (for example) \cite{bib:gs}, \cite{bib:huang},
\cite{bib:lawler}, and \cite{bib:mackay}.

Metropolis-Hastings is perhaps best introduced by example.

\begin{itemize}

\item One has a \bfidx{system} with multiple possible \bfidx{configurations}.
Specifically, one may think of the one-dimensional \bfidx{Ising model}.  This
is $\Omega=\{\pm 1\}^n$, i.e. $n$ particles which may be in either an up or a
down state.  A state is described by
$$
	\vecomega = (\omega_1, \ldots, \omega_n).
$$
Here, the state space $\Omega$ has $2^n$ possible configurations.

\item The system is endowed with an \bfidx{energy function}.
For the 1D Ising model, one has
$$
	E(\vecomega) = \sum_{i=1}^n \sum_{j=1}^n S_{ij} \omega_i \omega_j
		+ \sum_{i=1}^n h_i \omega_i.
$$
where the $S_ij$'s are interaction terms and the $h_i$'s are magnetization
terms.

\item One picks an \bfidx{initial configuration}.  Typically, there are three
choices: (1) Start with all spins down, i.e. $\vecomega = (-1, \ldots, -1)$.
(2) Start with all spins up, i.e. $\vecomega = (+1, \ldots, +1)$.  (3) Start
with $\vecomega$ selected from a uniform probability distribution on $\Omega$.

\item There is a system \bfidx{temperature} $\beta$.

\item One selects a \bfidx{site} $i$ and decides whether to flip $\omega_i$ to
$-\omega_i$.  This decision is made using the \bfidx{Metropolis prescription},
namely:

	\begin{itemize}
	\item One computes the change in energy $\Delta E = E(\vecomega')
		- E(\vecomega)$ which would be obtained if $\vecomega$ were
		sent to $\vecomega'$ by flipping $\omega_i$.
	\item One may compute $\Delta E$ by separately computing
		$E(\vecomega')$ and $E(\vecomega)$ and subtracting the two.
		However, since the only change is at the site $i$, one may do some
		algebra to derive an expression for $\Delta E$ which is less
		computationally expensive.
	\item One accepts the change with probability
		$$
			\min\{1, e^{-\beta \Delta E}\}.
		$$
	\end{itemize}

	This is called a \bfidx{Metropolis step}\index{step}.

\item Looping through all $n$ sites from $i=1$ to $i=n$, performing a
Metropolis step at each site $i$, is called a \bfidx{Metropolis
sweep}\index{sweep}.

\item If one realizes a random variable $X(\vecomega)$ at each of $M$ sweeps,
averaging $X$ over the $M$ sweeps, one obtains an approximation $\Xbar$ for the
expectation $E[X]$.

\item One should first run $L$ Metropolis sweeps of the system, discarding the
realizations of the random variable $X$, before running the $M$ sweeps in which
data are accumulated.  The $L$ sweeps are called the \bfidx{thermalization
phase}; the $M$ sweeps are called the \bfidx{accumulation phase}.  There is no
general method to determine whether the system has thermalized
(\cite{bib:kennedy}); the underlying concern is the convergence of the
Metropolis probability distribution to the stable distribution of its implicit
Markov chain.  Techniques for thermalization for the random-cycle model, which
is the subject of this paper, are presented in section \ref{sec:rcm_metro}.

\end{itemize}
