The Cycle Criterion for Reversibility

From Detailed Balance to a Cycle Test

Detailed balance assigns a weight to every state so that the rate of weighted flow from $i$ to $j$ matches the weighted flow back. The cycle criterion replaces the unknown state weights with a test involving only the transition rates around closed paths. It is useful when rates are given but a candidate stationary distribution is not. A necessary preliminary check is that every positive rate has a positive reverse rate: cycle products alone cannot detect a one-way edge if there are no cycles containing it.

Let $(X_t)_{t\ge0}$ be a continuous-time Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal F,\mathbb P)$, with a conservative, nonexplosive generator $Q=(q_{ij})$. For distinct states $i,j$, $q_{ij}\ge0$ is the transition rate from $i$ to $j$, and conservativity means $q_{ii}=-\sum_{j\ne i}q_{ij}$, with finite exit rate from each state. A positive weight function is a collection $w=(w_i)_{i\in S}$ with $0<w_i<\infty$ for every $i$. It satisfies detailed balance if $w_iq_{ij}=w_jq_{ji}$ for every pair of distinct states. If the weights have finite sum, they can be normalized to a probability distribution; if not, they still describe positive detailed-balance weights, but not a stationary probability distribution.

Definition: The rate support is symmetric if, for all distinct $i,j$, $q_{ij}>0$ holds exactly when $q_{ji}>0$. Under symmetric support, draw an undirected edge between $i$ and $j$ whenever $q_{ij}>0$. A finite cycle is a sequence $i_0,i_1,\ldots,i_m=i_0$, $m\ge2$, whose consecutive states are joined by edges. The cycle condition is $$ \prod_{r=0}^{m-1}q_{i_r i_{r+1}} = \prod_{r=0}^{m-1}q_{i_{r+1}i_r} $$ for every such cycle.

For a nonexplosive CTMC, detailed balance of a positive measure is the rate form of reversibility: starting from a normalized reversible measure, the stationary process has the same law when time is reversed. The earlier material on detailed balance establishes this characterization. Here the issue is how to decide whether the rate equations can hold without already knowing the weights.

Theorem (Cycle criterion): A countable-state generator has strictly positive detailed-balance weights if and only if its rate support is symmetric and the cycle condition holds. When these conditions hold, weights can be constructed separately on each connected component of the undirected rate graph. Within each component, the weights are unique up to multiplication by one positive constant.

Proof. First suppose positive weights satisfy detailed balance. If $q_{ij}>0$, then $w_iq_{ij}=w_jq_{ji}$, and since both weights are positive, $q_{ji}>0$. Reversing $i,j$ proves symmetric support. For any cycle $i_0,\ldots,i_m=i_0$, multiply the detailed-balance equations $w_{i_r}q_{i_r i_{r+1}}=w_{i_{r+1}}q_{i_{r+1}i_r}$ over $r=0,\ldots,m-1$. The product of weights on the left is $\prod_{r=0}^{m-1}w_{i_r}$, and on the right it is $\prod_{r=0}^{m-1}w_{i_{r+1}}$; these are equal because the cycle visits the same states in cyclic order. Cancelling this positive product gives the cycle condition.

Conversely, suppose support is symmetric and every cycle satisfies the condition. Work in one connected component and choose a root $o$, assigning it any weight $w_o>0$. For a finite path $\gamma=(o=i_0,\ldots,i_m=j)$, define $$ R(\gamma)=\prod_{r=0}^{m-1}\frac{q_{i_r i_{r+1}}}{q_{i_{r+1}i_r}}. $$ Every factor is positive because support is symmetric. The cycle condition says that $R(\gamma)=1$ for a closed cycle. It also holds for every finite closed walk: if a closed walk repeats an internal vertex, split it at that vertex into two shorter closed walks; repeating this reduces to cycles, while a two-step backtrack has ratio $q_{ij}q_{ji}/(q_{ji}q_{ij})=1$. Thus each closed walk has ratio $1$.

If $\alpha$ and $\beta$ are two paths from $o$ to $j$, follow $\alpha$ and then traverse $\beta$ backwards. This forms a closed walk. Its ratio is $R(\alpha)/R(\beta)=1$, so $R(\alpha)=R(\beta)$. Therefore the assignment $w_j=w_oR(\gamma)$ does not depend on the chosen path. For an edge $i\leftrightarrow j$, take a path to $i$ and append that edge. Path independence gives $w_j=w_iq_{ij}/q_{ji}$, hence $w_iq_{ij}=w_jq_{ji}$. An isolated state is a component by itself and can be assigned any positive weight; there are no off-diagonal balance equations to check there. Finally, if $\widetilde w$ is another positive solution in the component, detailed balance on every edge gives $\widetilde w_j/w_j=\widetilde w_i/w_i$. Connectivity makes this ratio constant throughout the component. Different components have no edges between them, so their positive scaling constants are unrestricted. $\square$

For a countable graph, the construction needs only finite paths: every state in a connected component is connected to the root by a finite path. Equivalently, one may choose a shortest-path tree from the root and compute each weight along its unique tree path. The cycle condition ensures that non-tree edges give the same weights as well. Checking only simple cycles is sufficient, since the closed-walk splitting argument in the proof reduces any closed walk to simple cycles and backtracks.

Applying the Criterion

Worked Example: A Reversible Three-State Cycle

Consider $S=\{0,1,2\}$, with rates $q_{01}=2,\ q_{10}=1,\ q_{12}=2,\ q_{21}=\tfrac43,\ q_{20}=1,\ q_{02}=3$. The diagonal entries are $q_{00}=-5,\ q_{11}=-3,\ q_{22}=-\tfrac73$. Each generator row sums to zero: $-5+2+3=0$, $-3+1+2=0$, and $-\tfrac73+\tfrac43+1=0$. Every off-diagonal rate is positive, so support is symmetric.

There is one three-edge cycle to check, up to reversing its orientation. For $0\to1\to2\to0$, the forward product is $2\cdot2\cdot1=4$. The reverse product is $3\cdot\tfrac43\cdot1=4$, so the cycle condition holds. Construct weights by setting $w_0=1$. The edge $0\leftrightarrow1$ gives $w_1=w_0q_{01}/q_{10}=2$. The edge $1\leftrightarrow2$ gives $w_2=w_1q_{12}/q_{21}=2\cdot2/(\tfrac43)=3$.

Check: the three balance equations are $1\cdot2=2\cdot1$, $2\cdot2=3\cdot\tfrac43$, and $3\cdot1=1\cdot3$. All hold. The weights sum to $1+2+3=6$, so the normalized reversible probability is $(\tfrac16,\tfrac13,\tfrac12)$. For example, its weighted rates on $0\leftrightarrow2$ are $\tfrac16\cdot3=\tfrac12$ and $\tfrac12\cdot1=\tfrac12$.

Worked Example: A Symmetric Square with Inconsistent Rates

Take $S=\{0,1,2,3\}$, with clockwise rates $q_{01}=q_{12}=q_{23}=1$, $q_{30}=2$, and reverse rates $q_{10}=q_{21}=q_{32}=q_{03}=1$. Set $q_{00}=-2,\ q_{11}=-2,\ q_{22}=-2,\ q_{33}=-3$. The row sums are $-2+1+1=0$, $-2+1+1=0$, $-2+1+1=0$, and $-3+1+2=0$, respectively. The support is symmetric.

On the cycle $0\to1\to2\to3\to0$, the clockwise product is $1\cdot1\cdot1\cdot2=2$, while the reverse product is $1\cdot1\cdot1\cdot1=1$. Since $2\ne1$, the cycle condition fails. Therefore no strictly positive detailed-balance weights exist. The contradiction can also be seen by trying to propagate weights: $w_1=w_0$, then $w_2=w_1$, then $w_3=w_2$. The edge $3\leftrightarrow0$ would require $w_3q_{30}=w_0q_{03}$, or $2w_0=w_0$, impossible for $w_0>0$.

Worked Example: Why Symmetric Support Must Be Checked

Let $S=\{1,2\}$, with $q_{12}=1$ and $q_{21}=0$. The conservative generator is $Q=\begin{bmatrix}-1&1\\0&0\end{bmatrix}$; its first row sums to $-1+1=0$ and its second to $0+0=0$. There is no cycle using only bidirectional edges, so a test that checks only cycle products would pass vacuously.

But support is not symmetric: $q_{12}>0$ while $q_{21}=0$. Detailed balance would require $w_1\cdot1=w_2\cdot0$, which reduces to $w_1=0$, contradicting strict positivity. Thus no positive reversible weights exist. The correction is to treat symmetric support as an independent necessary condition, not as a consequence of the cycle test.

Countable State Spaces and Normalization

The criterion applies to countable state spaces because it concerns finite paths and finite cycles, not a finite matrix calculation. A particularly useful case is a birth–death chain on $S=\{0,1,2,\ldots\}$, where the only possible moves are between neighboring states. If each neighboring pair has positive rates in both directions, the graph is a line and contains no cycles. The cycle condition is therefore automatic, and positive weights can be built recursively. This does not by itself guarantee that the weights sum to a finite number.

Worked Example: Reversible Rates Without a Stationary Probability

On $S=\{0,1,2,\ldots\}$, set $q_{n,n+1}=2$ for every $n\ge0$, and $q_{n,n-1}=1$ for $n\ge1$. Set $q_{00}=-2$ and $q_{nn}=-3$ for $n\ge1$. The row sum at state $0$ is $-2+2=0$; at every $n\ge1$, it is $-3+1+2=0$. Exit rates are bounded by $3$, so the chain is nonexplosive. Support is symmetric and the line graph has no cycles.

Starting with $w_0=1$, balance on the edge $n\leftrightarrow n+1$ requires $w_n\cdot2=w_{n+1}\cdot1$. Hence $w_{n+1}=2w_n$, giving $w_n=2^n$. Substitution verifies every edge equation: $2^n\cdot2=2^{n+1}\cdot1$. But $\sum_{n=0}^{\infty}2^n=\infty$, so these weights cannot be normalized to a probability distribution. The cycle criterion proves positive reversibility with respect to weights; it does not assert the existence of an equilibrium probability.

For a reducible chain, check symmetric support across the whole state space before considering components. If support is symmetric, each connected component can be assigned its own positive scale, as the theorem shows. Those independent constants can matter when asking whether the resulting weights can be normalized. If support is asymmetric anywhere, constructing weights separately on components of a bidirectional-edge graph does not repair the one-way rate: detailed balance fails on that edge itself.

Common mistake. It is incorrect to say that a vacuous cycle test guarantees reversibility, or that a failed cycle test can be repaired by rescaling weights. In the two-state example, there are no bidirectional cycles, but $w_1q_{12}=w_1$ and $w_2q_{21}=0$ cannot be equal for positive $w_1,w_2$. In the square example, multiplying every weight by the same constant leaves the unequal cycle products $2$ and $1$ unchanged. Always check support symmetry first, then cycle products, and normalize only after a positive weight function has been constructed.

Check Your Understanding

For each question, distinguish the support condition, the cycle equations, and the possibility of normalizing weights.

For a three-state cycle, what equation must the six directed rates satisfy for the cycle criterion to hold?
Why does a positive rate $q_{ij}$ with $q_{ji}=0$ rule out positive detailed-balance weights, even if no cycle contains that pair?
On a bidirectional line of states, why is the cycle condition automatic, and how can the weights still fail to define a probability distribution?
Suppose two connected components each satisfy the cycle criterion and have symmetric support. Which aspects of their weights can be chosen independently?
For the square example, identify the exact pair of products whose inequality rules out detailed balance.

The Cycle Criterion for Reversibility

What You'll Learn