Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
share|improve this question
1  
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. –  James Martin Oct 19 '12 at 14:58
    
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. –  Alekk Oct 19 '12 at 15:26
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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$. –  Alekk Oct 21 '12 at 10:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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