4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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:

  1. $(x_1,x_3,\ldots,x_{19})|(x_2,x_4,\ldots,x_{20})$
  2. $(x_2,x_4,\ldots,x_{20})|(x_1,x_3,\ldots,x_{19})$
  3. $(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.

$\endgroup$
  • $\begingroup$ In you step when you went from $\pi(x_i | x_{-i})$ to $\pi(x_i=0 | x_{-i})$ why did you get rid of the sum? Shouldn't the value of a particular $x_i$ depend on all of the rest of the values in the sample vector, not just the adjacent ones? $\endgroup$ – ketchup Nov 5 '17 at 21:27
  • $\begingroup$ I sort of took a whack at it and tried to implement an algorithm. For $\beta = .01$ I got 1. 0.478 2. 0.5 3. 0.486 4. 0.503 5. 0.511 6. 0.486 7. 0.495 8. 0.474 9. 0.505 10. 0.498 11. 0.471 12. 0.474 13. 0.531 14. 0.507 15. 0.481 16. 0.509 17. 0.471 18. 0.482 19. 0.505 20. 0.497 $\endgroup$ – ketchup Nov 8 '17 at 3:28
  • $\begingroup$ Percent of $x_i$ equal to one after throwing out the first half samples $\endgroup$ – ketchup Nov 8 '17 at 14:14
  • $\begingroup$ They seem to all go to .5. I start with an initial vector with random 1s and 0s $\endgroup$ – ketchup Nov 8 '17 at 19:51
  • 1
    $\begingroup$ Note that for the 1d example described in the question, it is possible to directly generate exact iid samples via forward-backward sampling $\endgroup$ – Darren Wilkinson Nov 11 '17 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.