8
$\begingroup$

The Ising model on $\mathbb{Z} / 2d\mathbb{Z}$ gives to the configuration $x=(x_0, \ldots, x_{2d-1}) \in \{-1,+1\}^{2d}$ a probability proportional to $\exp\\big(\beta \sum_i x_ix_{i+1} \\big)$. The Gibbs sampler with block updates is a Markov chain $X_k$ that evolves on the set of such configurations and updates the odd (resp. even) indices conditionally on the even (resp. odd) indices with probability a half.

It seems like a relatively straightforward application of the path coupling [1] approach (two configurations are neighbours if they agree on all odd or all even coordinates; distance between two neighbours is $1+H(x,y)/d$ where $H$ is the Hamming distance) shows that the mixing time of the Gibbs sampler stays bounded as the size $d$ of the system goes to infinity, which looks rather surprising. Any intuition behind that? If this is already written somewhere, any reference concerning this (or similar) result?

  • [1] Chapter 14 of Markov Chains and Mixing Times by D. Levin, Y. Peres and E. Wilmer
$\endgroup$
2
  • 1
    $\begingroup$ I guess you mean $\mathbb{Z}/2d\mathbb{Z}$ and $(x_0,\dots, x_{2d-1})\in \{-1, +1\}^{2d}$? Also $d$ is probably more naturally "size" than "dimension" here, since everything is really 1-dimensional. Anyway, are you sure you are asking the question you mean? Maybe I misunderstand, but for most sensible definitions the mixing time for, say $d=1$ (a system with only 2 sites) will not be the same as that for $d=1000$. Often in these kind of problems the mixing time is considered in an asymptotic regime as some parameter gets large - but that seems to be absent here. $\endgroup$ Oct 19, 2012 at 14:58
  • $\begingroup$ Thank you for the comment, I have updated the notations. As you said, I really meant "size" instead of "dimension". And I should not have written that the mixing time does not depend on d; what I really meant is that the mixing time $\tau(d)$ seems to stay bounded as $d$ goes to infinity. $\endgroup$
    – Alekk
    Oct 19, 2012 at 15:26

1 Answer 1

7
$\begingroup$

This is not so surprising, and is related to the lack of phase transition in the one dimensional Ising model.

Consider first why the mixing time might be large. If $\beta$ is very high, and we start with a configuration where half the circle is + and half -, it will take a fairly long time for the chain to converge to one of the extreme states. (Roughly $d^2$, as the interface will perform a random walk.)

However, if $\beta$ is fixed and $d$ is large, then at every step the process will create islands of the opposite sign, at distance of order $e^{4\beta}$, regardless of $d$. Notethat the stationary distribution also has a finite correlation length.

Finally, another way to see the bounded mixing time is by a coupling argument. The simplest local coupling, will create agreement with some density, and segments of agreement will grow at positive rate, so after roughly at most $e^{4\beta}$ steps any two starting configurations will couple. This bound can be improved.

$\endgroup$
1
  • $\begingroup$ Thank, that's a great answer. I was trying the other day to see how long it would take to couple an all +1 configuration with an all -1 configuration, and one can see that the coupling time stays bounded wrt $d$. $\endgroup$
    – Alekk
    Oct 21, 2012 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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