Hi Alekk,

There is a paper from several years ago by Bhatnagar and Randall on torpid mixing of simulated tempering on the Potts model. In it, they mention that they also have a proof of rapid mixing for a related tempering approach on the same model (I don't remember if this is actually in the paper; they haven't yet published everything that they know on the subject).

I've talked to a few people who were experts on this sort of thing in the intervening time, and they have mostly claimed that there has been very little progress on proving efficiency for anything that isn't a mean-field model. Of course, the people who I've been talking to tend towards proving 'good' (i.e. small-order polynomial in size of the lattice) for discrete models, and in L^{1} distance; its possible that other areas of the literature have analyses in other metrics or for other models.

Also, I don't know the etiquette here, but I've been thinking about a few simple related models for a little while now. I'd certainly be interested in talking & sharing results/simulations/etc if you are in fact working in the area (my guess from your blog is that you're a graduate student as well?). My (slightly embarrassing and very old) email is cauchie.p@gmail.com.

Cheers,