Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
Gibbs sampling is a Markov Chain Monte Carlo sampling technique that iteratively samples variables from their conditional distributions. There are two common scan orders for the variables: random scan and systematic scan. Due to the benefits of locality in hardware, systematic scan is commonly used, even though most statistical guarantees are only for random scan. While it has been conjectured that the mixing times of random scan and systematic scan do not differ by more than a logarithmic factor, we show by counterexample that this is not the case, and we prove that that the mixing times do not differ by more than a polynomial factor under mild conditions. To prove these relative bounds, we introduce a method of augmenting the state space to study systematic scan using conductance.
This paper is interested in comparing the mixing rates of Gibbs sampling using either systematic scan or random updates. The basic contributions are two: First, in Section 2, a set of cases where 1) systematic scan is polynomially faster than random updates. Together with a previously known case where it can be slower this contradicts a conjecture that the speeds of systematic and random updates are similar. Secondly, (In Theorem 1) a set of mild conditions under which the mixing times of systematic scan and random updates are not "too" different (roughly within squares of each other). 
I think this paper addresses an important issue and makes valuable contributions, and thus should be published. I have a few concerns, hence my lower rating for the last question above (which I think could be addressed relatively easily, however).       - The proofs are sketched out in quite an informal manner. I think this is fundamentally *OK* and even perhaps a positive thing. However, I think a bit more discussion needs to be given to how the arguments might be made more formal. For example, in Section 2.1, I think the proof is intended to hold only in the limit of M going to infinity. Please give a stament of what should hold in what limit-- this wasn't clear to me. Another example is the assumption that the bridge state has low mass in Section 2.2. This seems like a dubious assumption. Again this seems to be intended to hold only in the limit of a large model but exactly how this should work is not sketched out. (Also, if you are going to make this assumption, why not include it in Eq. 3?) Finally, the assumption that each of the islands mix rapidly within themselves again seems to weaken the strength of Section 2.2 All these assumptions are probably fine-- and improve the readability of the paper-- but I think more guidance needs to be given how one would make things more formal if desired.       - I don't understand the experiments. Specifically, how are the mixing times calculated? This isn't discussed at all. I do not understand what was done to only consider states next to the bridge.       - The argument at the end of Section 2.2 seems sufficient to compare f(n) to n*f(n) but it isn't clear why f(n) should itself be n.       - What is |x| in P(x) on p. 4? Is this simply the length of x?       - All the results seem to have the nature of adding/removing a factor of n, or squaring the mixing times. Is there anything fundamental about this? The abstract seems to lose something in only referring to this as "polynomial".