7
$\begingroup$

I am new to methods for simulating Markov chains in order to sample from the target, unknown distribution. After a couple days of reading, I found out that even though people have realized that non-reversible (or, irreversible) Markov chains usually converge faster to their invariant distributions. There are not many papers on irreversible Markov chains for the purpose of generating the unknown distribution; instead, reversible Markov chains dominate the literature.

Could you please please explain why the irreversible Markov chains are so less frequently used to induce the unknown distribution one wants to sample from? Thanks in advance.

Regards,

Chee

$\endgroup$
  • $\begingroup$ I think the idea of sampling from an "unknown distribution" is inaccurate. You must know enough about the distribution to construct a MC with that distribution as its invariant distribution. Often there are natural ways to construct a reversible chain with a "difficult to analyze directly" invariant distribution. For more general chains getting the right invariant distribution is problematic. $\endgroup$ – guest Aug 26 '14 at 8:44
8
$\begingroup$

I will take a stab at this, even though I no longer have the full eloquence of a working mathematician. First of all reversible Markov chains are really self-adjoint operators in disguise, whose spectral properties are therefore well-understood at least in theory. But even in this nice setting, many seemingly simple questions cannot be answered. For instance, take a card shuffling example, where you swap a randomly chosen pair of adjacent cards in a deck with 1/2 probability, and ask about the rate of convergence in say the most natural total variation distance. Some of its eigenvalues that correspond to irreducible characters of the symmetric group are rational, but the majority of them are irrational. Of course this does not prevent us from getting good rates of convergence in theory. The current best record of upper and lower bounds have a factor of two in between, and nobody has any clue how to close the gap. Another more serious example is the random walk on proper coloring, for which the right order of magnitude is not known in many cases of number of colors and maximum graph degree. It was conjectured the a uniform lower bound of $n log n$ should hold for all bounded degree graph, which is reasonable in light of coupon collector's phenomenon, but it is still open. A similar assertion for Glauber dynamics on Ising model has been resolved a few years ago; you can see how hard it can be to prove such a simple statement.

Even if we know all the eigenvalues of the chain, we are still not guaranteed an easy path to its rate of convergence. One such example is the Glauber dynamics on Ising lattice, which has only recently been resolved in the high temperature case, and still open for the critical and low temperature regime. I can't think of other good examples at the moment, but there should be plenty in this book and this.

Finally there are definitely some non-reversible chains that have been extensively and successfully studied, such as the riffle shuffle and Thorpe shuffle. The fact that one can get exact answer for the first one and the right order of magnitude (only recently) for the second one is nothing short of miracles. But from a mathematical point of view, it is more natural to exhaust the study of "easier" reversible cases before tackling the wild west.

$\endgroup$
  • $\begingroup$ Hi John, thank you for providing part of a whole picture of the area and for the inspirations you cited in your reply. I really appreciate it! $\endgroup$ – Chee Aug 26 '14 at 15:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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