1
$\begingroup$

Section 2.2.3 of this book:

http://itf.fys.kuleuven.be/~fpspXIII/material/Barkema_FPSPXIII.pdf

discusses the detailed balance condition in the context of Markov chain Monte Carlo algorithms.

First it gives a necessary condition required for a system to tend to some stationary distribution $\mathbf{p}$ (Eq. 2.6) as $$\sum_{\nu}p_{\mu}P(\mu\rightarrow\nu) = \sum_{\nu}p_{\nu}P(\nu\rightarrow\mu)$$

It then argues that this is not a sufficient condition, since as well as the desired long time behaviour of the master equation (Eq. 2.10)$$\mathbf{w}(\infty)=\mathbf{P}\cdot\mathbf{w}(\infty)$$ we can also have limit cycles of length $n$ governed by (Eq. 2.11) $$\mathbf{w}(\infty)=\mathbf{P}^{n}\cdot\mathbf{w}(\infty)$$

The conclusion is that in order to exclude such limit cycles, we further impose the detailed balance condition (Eq. 2.12) $$p_{\mu}P(\mu\rightarrow\nu) = p_{\nu}P(\nu\rightarrow\mu)$$ which clearly still satisfies Eq. 2.6.

My question is about the accuracy of this statement, which I question in two ways:

  1. A counter-example. Suppose we would like a stationary distribution $p = (\frac{1}{2}, \frac{1}{2})$. Then we may write down a Markov matrix $\mathbf{P} = \begin{bmatrix}0&1\\1&0\end{bmatrix}$ which satisfies the detailed balance condition. Clearly this has limit cycles $(1,0) = \mathbf{P}^{2}\cdot (1,0)$ and $(0,1) = \mathbf{P}^{2}\cdot (0,1)$ in conflict with the above.
  2. The discussion in the paragraph following Eq. 2.12 discusses how the detailed balance condition ensures the probability flowing between the states $\mu$ and $\nu$ cancels in both directions, ensuring there may be no limit cycles. However, surely this argument holds only when the system has probability distribution $\mathbf{p}$, and not before the system has reached this stationary distribution.

In summary, I don't really follow the logic of this argument. NB: my understanding of this stuff is more from a physics perspective, so if possible it would be good to avoid too much rigor.

$\endgroup$
  • $\begingroup$ The more I've thought about this, and tried to read around, the more I think you are right, and the book is wrong. Detailed balance does not guarantee aperiodicity (which is the key condition under discussion here) and I don't think that I have seen this claimed anywhere else. See also this more recent question on phys.SE which seems relevant, and at least indicates some interest. It would be good to get a definitive answer from someone! $\endgroup$ – user575517 Jul 27 '18 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.