Checking Cycle Products in Worked Chains

What a Cycle Test Compares

Detailed balance compares the probability flow across each pair of states. Kolmogorov’s cycle criterion gives a complementary test: instead of solving for a stationary distribution, compare the products of transition probabilities along a closed path in the two directions. A well-chosen path can rule out reversibility with one exact calculation.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The cycle calculations below depend only on \(P\), not on the initial distribution.

A finite chain is reversible if there is a probability distribution \(\pi\) satisfying detailed balance, \(\pi_i p_{ij}=\pi_j p_{ji}\) for all \(i,j\). For a finite irreducible chain, Kolmogorov’s cycle criterion says that the chain is reversible if and only if \(F(C)=R(C)\) for every closed path \(C\). This standard result, including its proof, is given in the earlier material on Kolmogorov’s cycle criterion. Here the emphasis is how to choose and compute useful tests.

When every transition in both directions along a pair is positive, detailed balance requires \(\pi_j/\pi_i=p_{ij}/p_{ji}\). Multiplying these ratios around a closed path cancels the \(\pi\)-terms, leaving the cycle-product equality. This explains why cycles are informative: a failed equality makes all detailed-balance equations impossible. If probabilities are zero, use the products themselves rather than dividing by a transition probability.

Which Cycles Need Checking?

Proof. We use induction on the length of a closed path. If it is simple, the required equality is the assumption. If it is not simple, some state occurs at two positions other than just the initial and final pair. The segment between those occurrences is a shorter closed path. Removing that segment leaves another shorter closed path (a segment of length zero is not removed). The original forward product is the product of the two shorter forward products. Its reverse product is likewise the product of the reverse products of those two paths, because multiplication of the transition probabilities is commutative. By induction, the forward and reverse products agree for each shorter path, so their products agree for the original path. Thus equality holds for every closed path. \(\square\)

This gives a practical reduction: repeated visits do not create fundamentally new tests. It is enough to seek simple cycles, especially short ones. If all transitions are positive, ratios can guide the search: choose a path of edges, infer the relative weights \(\pi_j/\pi_i\) along it, then check whether an alternative route gives the same relative weight. A mismatch is a cycle-product failure.

Proof. If the chain is reversible with distribution \(\pi\), then full support and detailed balance imply every \(\pi_i>0\): if \(\pi_i=0\), detailed balance gives \(\pi_jp_{ji}=0\) for every \(j\), hence \(\pi_j=0\) for every \(j\), contradicting \(\sum_j\pi_j=1\). Multiplying detailed-balance equations around any triangle cancels the three positive \(\pi\)-terms, giving equality of the forward and reverse products.

Conversely, first suppose there are at least three states and all triangle equalities hold. Fix a reference state \(1\), set \(w_1=1\), and for \(i\ne1\) set \(w_i=p_{1i}/p_{i1}\), which is defined and positive by full support. For distinct \(i,j\ne1\), the triangle \(1\to i\to j\to1\) gives \(p_{1i}p_{ij}p_{j1}=p_{1j}p_{ji}p_{i1}\). Dividing by \(p_{i1}p_{j1}>0\) yields \(w_i p_{ij}=w_j p_{ji}\). The same equality for a pair \(1,i\) follows directly from the definition of \(w_i\), and for \(i=j\) it is an identity. Thus all detailed-balance equations hold for the positive weights \(w_i\). Set \(\pi_i=w_i/\sum_k w_k\); these weights sum to one and satisfy detailed balance, so the chain is reversible. If there are two states, choose \(w_1=1\) and \(w_2=p_{12}/p_{21}\); the single off-diagonal detailed-balance equation holds, and the diagonal equations are identities. With one state, \(\pi_1=1\) works. This proves both directions, including the small state spaces. \(\square\)

The full-support hypothesis matters. In a sparse transition matrix, a triangle condition alone may not test a longer cycle, and a ratio such as \(p_{ij}/p_{ji}\) may not exist. In that setting, inspect the actual closed paths and retain zero products in the calculation.

Worked Cycle Checks

Zero Edges and a Common Miscalculation

Proof. Irreducibility means there is a positive-probability directed path from \(j\) back to \(i\). Prepend the edge \(i\to j\) to that path to form a closed path. Its forward product is positive because every edge in it has positive probability. The reverse product contains the factor \(p_{ji}=0\), which is the reverse transition for the initial edge, so the reverse product is zero. The cycle products differ, and Kolmogorov’s cycle criterion rules out reversibility. \(\square\)

There is a subtle point here: the two-step closed path \(i\to j\to i\) has forward product \(p_{ij}p_{ji}=0\), and its reverse product is also \(p_{ji}p_{ij}=0\). That two-step test does not detect the one-way edge. The informative path is the positive directed route that returns to the starting state, together with the one-way edge.

Common pitfall. Do not divide by a reverse transition that is zero, and do not claim that the two-step path detects a one-way edge. Both two-step products are zero in that case. Instead, use irreducibility to find a positive directed path returning from the destination to the origin, then compare the full cycle with its reverse. More generally, choose a cycle whose transitions can be written down exactly; a cycle with zero products in both directions provides no evidence either way.