Kolmogorov's Cycle Criterion

Why Compare a Cycle With Its Reversal?

Reversibility asks whether the transition behavior of a chain in equilibrium is unchanged when time is run backward. Detailed balance expresses this as a pairwise equality: the stationary flow from state \(i\) to state \(j\) equals the flow from \(j\) to \(i\). Kolmogorov’s cycle criterion packages those pairwise balances into a test involving products of transition probabilities around closed paths. The test is useful because it can rule out reversibility without first solving for a stationary distribution.

Throughout, let \((X_n)_{n\ge0}\) be a time-homogeneous discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\); each row sums to \(1\). The chain is irreducible if every state can be reached from every other state with positive probability in some finite number of steps. The initial distribution does not affect the criterion.

Thus a cycle is an ordered closed walk, not necessarily a loop with distinct intermediate states. Length one gives the loop \(i_0,i_0\), for which the two products agree automatically. For length two, the forward and reversed products also agree automatically. The informative tests usually involve cycles of length at least three.

Here, a finite irreducible chain is called reversible if it has a stationary probability distribution \(\pi\) satisfying detailed balance, \(\pi_i p_{ij}=\pi_j p_{ji}\) for all \(i,j\). For such a chain, \(\pi_i>0\) for every state; positivity follows from irreducibility and stationarity. Reversibility is stronger than stationarity: a stationary distribution alone does not guarantee that the chain is reversible.

Why Detailed Balance Implies the Cycle Test

The necessity direction explains why the products arise. At each step around a cycle, detailed balance allows the stationary weight at the current state and the transition probability to be exchanged for the stationary weight and reverse transition at the next state. Around a closed cycle, all the stationary weights cancel.

Proposition. If a chain has a strictly positive probability distribution \(\pi\) satisfying detailed balance, then the cycle-product equality holds for every cycle.

Proof. Fix a cycle \(i_0,i_1,\ldots,i_m=i_0\). Detailed balance gives \(\pi_{i_r}p_{i_r i_{r+1}}=\pi_{i_{r+1}}p_{i_{r+1}i_r}\) for each \(r=0,\ldots,m-1\). Multiply these \(m\) equalities. The left side is \(\bigl(\prod_{r=0}^{m-1}\pi_{i_r}\bigr)\bigl(\prod_{r=0}^{m-1}p_{i_r i_{r+1}}\bigr)\). The right side is \(\bigl(\prod_{r=0}^{m-1}\pi_{i_{r+1}}\bigr)\bigl(\prod_{r=0}^{m-1}p_{i_{r+1}i_r}\bigr)\). Because \(i_m=i_0\), the two products of stationary probabilities contain the same factors, including repetitions. Each \(\pi_i\) is positive, so canceling their common product yields the cycle-product equality. No transition probability is divided out, so the argument also applies when some transitions have probability zero. \(\square\)

For irreducible finite chains, this proposition proves the necessary direction of the criterion. The other direction is more constructive: cycle equalities allow consistent relative weights to be assigned to states, from which a detailed-balance distribution can be obtained. That construction requires checking that the assigned weights do not depend on the chosen path; it is the subject of the proof that follows this criterion.

How Zero Transition Probabilities Enter

The criterion must be applied as written, including cycles whose product is zero. If the forward product is positive while the reversed product is zero, the equality fails, so the chain is not reversible. Conversely, if both products are zero, that cycle satisfies the equality; a zero on one side is not by itself a failure.

Irreducibility does not mean every one-step transition is possible. It means that paths of some finite length connect every pair of states. It is therefore possible for a chain to be irreducible while having a transition \(i\to j\) with positive probability and a reverse transition \(j\to i\) with probability zero. The cycle condition detects this asymmetry.

Proposition. If an irreducible chain satisfies the cycle-product equality for every cycle, then its one-step support is symmetric: \(p_{ij}>0\) if and only if \(p_{ji}>0\).

Proof. Suppose \(p_{ij}>0\). Irreducibility gives a path from \(j\) back to \(i\) whose transitions all have positive probability. Append that path to the edge \(i\to j\) to form a cycle. Its forward product is positive, since every factor is positive. By the cycle-product equality, the reversed product is also positive. The reversed product includes the factor \(p_{ji}\), so \(p_{ji}>0\). Interchanging \(i\) and \(j\) proves the converse implication. If \(i=j\), the assertion is immediate because it compares \(p_{ii}\) with itself. \(\square\)

This gives a practical preliminary check: in an irreducible chain, a single positive one-way edge rules out reversibility if its reverse edge has probability zero. Once support symmetry has been established, any cycle containing a zero-probability edge has a zero-probability reverse edge at the corresponding place. Both full products are then zero. Cycles consisting entirely of positive transitions remain the nontrivial product comparisons.

Applying the Criterion

A Reliable Testing Procedure

For a finite irreducible chain, organize the test so that zero transitions are not lost:

Common mistake. A tempting but incorrect rule is to test only cycles for which both traversals have positive probability, silently discarding a cycle if its reverse contains a zero. In the deterministic three-state example, that rule would discard \(1,2,3,1\) and miss the decisive comparison. The correction is to include every cycle and compare the products as ordinary nonnegative numbers: here they are \(1\) and \(0\), so the criterion fails. In contrast, in the sparse reversible example the products are \(0\) and \(0\), so that cycle passes. Never divide by a transition probability unless its positivity has first been verified.

The cycle condition is a test of consistency around closed paths, not a substitute for the definition of stationarity. A stationary chain can have a net circulation around a cycle and fail reversibility; the cycle products expose this obstruction. For a reversible chain, detailed balance guarantees equality around every cycle, including cycles with repeated states and zero transitions. The criterion’s sufficiency direction explains why, in a finite irreducible chain, those cycle equalities also permit a consistent stationary weighting of the states.