Gibbs sampling an Ising model with 0s and 1s One of my problems in one of my courses ask to sample a 20 dimensional vector of 0s and 1s, $\{0,1\}^{20},$ when they are distributed as
$$
\pi(x) = \exp\left\{-\beta \sum_{i=1}^{19} |x_{i+1}-x_i| \right\}
$$
I came across this question:
Gibbs sampling for Ising model
But I am still having trouble finding the conditional distribution for my case. Is my probability distribution even a distribution? Since the state space is discrete, shouldn't $\pi(x)$ be a pmf, and consider the vector $\vec{0}$. Then $\pi(\vec{0}) = e^0 = 1 = \pi(\vec{1})$ so the probabilities are greater than one?
 A: The Ising model is one of the simplest examples of distributions with intractable normalising constant: the exact definition of the pmf is
$$\pi(x) \propto \exp\left\{-\beta \sum_{i=1}^{19} |x_{i+1}-x_i| \right\}\qquad x\in\{0,1\}^{20}$$meaning that $\pi(x)$ is equal to
$$\dfrac{\exp\left\{-\beta \sum_{i=1}^{19} |x_{i+1}-x_i| \right\}}{\sum_{y\in \{0,1\}^{20}} \exp\left\{-\beta \sum_{i=1}^{19} |y_{i+1}-y_i| \right\}}$$
a sum that cannot be computed in closed form because of the $2^{20}$ terms inside.
A Gibbs sampling simulation from this distribution is nonetheless feasible as, if one considers a single element $x_i$ $(1\le i\le 20)$ of the vector $x=(x_1,\ldots,x_{20})$, then its conditional distribution satisfies
\begin{align*}\pi(x_i|x_{-i})&\propto \pi(x)\propto \exp\left\{-\beta \sum_{j=1}^{19} |x_{j+1}-x_j| \right\}\\
&=\overbrace{\exp\left\{-\beta \sum_{j=1}^{i-1} |x_{j+1}-x_j| \right\}}^ {\text{does not depend on }x_i}\\
&\qquad \times\exp\left\{-\beta |x_{i+1}-x_i| \right\}\times\exp\left\{-\beta |x_{i+1}-x_i| \right\}\\
&\qquad\qquad \times\underbrace{\exp\left\{-\beta \sum_{j=i+1}^{19} |x_{j+1}-x_j| \right\}}_{\text{does not depend on }x_i}\end{align*}
The same proportionality symbol occurs in this representation but is no longer an issue: since $x_i\in \{0,1\}$ the pmf can easily be normalised into a probability distribution:
\begin{align*}\pi(x_i=0|x_{-i})&\propto \exp\left\{-\beta |x_{i-1}| -\beta |x_{i+1}|\right\}\\
\pi(x_i=1|x_{-i})&\propto \exp\left\{-\beta |x_{i-1}-1| -\beta |x_{i+1}-1|\right\}\end{align*}
with obvious adjustments when $i=1,20$. Therefore,
$$\pi(x_i=0|x_{-i})=\dfrac{\exp\left\{-\beta |x_{i-1}| -\beta |x_{i+1}|\right\}}{\exp\left\{-\beta |x_{i-1}| -\beta |x_{i+1}|\right\}+\exp\left\{-\beta |x_{i-1}-1| -\beta |x_{i+1}-1|\right\}}$$
which can be simulated directly. 
Actually, this Gibbs sampler can be sped up by simulating:


*

*$(x_1,x_3,\ldots,x_{19})|(x_2,x_4,\ldots,x_{20})$

*$(x_2,x_4,\ldots,x_{20})|(x_1,x_3,\ldots,x_{19})$

*$(x_1,x_3,\ldots,x_{19})|(x_2,x_4,\ldots,x_{20})$


because the components with odd (resp. even) indices are independent conditional on the components with even (resp. odd) indices. And, while the Gibbs sampler gets less and less energy to converge to its stationary when $\beta$ gets larger, an alternative (slice) sampler called the Wang-Landau algorithm can speed up the Gibbs sampler considerably.
There also exist "perfect" sampling algorithms for simulating exact realisations from the Ising model, rather than Markov chains converging to this model, but the description is a bit too advanced for the forum. See this book by Mark Huber for details. Or my blog comments about it.
