Why look backwards?
A transition matrix tells us how to predict the next state from the present one. A different question arises when a stationary record is played backwards: given the present state, how likely was each possible previous state? The answer depends both on the forward transitions and on how often the chain visits each state. A rare state may move to a common one with high probability, while the reverse move is infrequent.
This section studies finite, time-homogeneous chains. We use row distributions and assume familiarity with conditional probability and matrix multiplication.
Flux and the reverse chain
Let be a stochastic matrix on a finite state space , and suppose that is a stationary probability with every . Start the chain with . Its law at every later time is then . Define the stationary one-step flux
Stationarity means that total incoming and outgoing fluxes agree at each state: . It does not say that the two fluxes on each individual edge agree.
Theorem 2.10.1
(Reversing a stationary finite chain)
For put
For any fixed horizon , the reversed sequence , , is a Markov chain with transition matrix and initial distribution . Moreover and .
Proof
(Telescoping the stationary weights along a path)
The row sums are , and nonnegativity is clear. For a forward path , the product equals
because the factors of telescope. This is exactly the path probability prescribed by the reversed initial law and transitions, establishing the Markov property on the finite horizon. Also , and applying the formula a second time returns . The assumption is needed for division; states of zero stationary mass are never observed in a stationary record and require separate treatment.
The same formula for a particular backwards step follows from Bayes' rule. The path proof supplies the stronger statement that the entire reversed record is Markov. The finite-horizon wording avoids assuming a two-sided process has already been constructed.
Detailed balance is stronger than stationarity
Definition 2.10.2
(Reversibility)
The stationary chain is reversible if every finite path has the same probability as the path read in reverse. This is equivalent to , or to the detailed balance equations
Indeed equality of the probabilities of two-state paths gives the equations. Conversely the equations make ; the path theorem then gives equality for paths of any finite length.
Concept lensAlgebraic
Reversibility as a symmetric flux matrix
Detailed balance says that the flux matrix , with , is symmetric. Equivalently, is self-adjoint for the weighted inner product on column vectors:
and these agree for all exactly when . Then is a real symmetric matrix similar to , so a reversible chain has only real eigenvalues. The circulating chain below has the complex eigenvalues , which already shows it cannot be reversible for any stationary law.
Detailed balance is the usual way to find a stationary law, because it is a pairwise condition rather than a system indexed by vertices.
Proposition 2.10.3
(Detailed balance implies stationarity)
If a probability vector satisfies for all , then . The converse is false in general.
Proof
(Sum the pairwise equations over the starting state)
For each , summing detailed balance over gives , since row of sums to one. The converse fails: stationarity balances the total flow at a vertex, while detailed balance demands cancellation separately across every pair. The circulating chain in the worked examples is stationary for the uniform law but has .
A practical construction is to find positive weights satisfying and normalize by . On a finite space the sum is finite. For a countable chain, a finite sum cannot be taken for granted, as the next example shows.
Counterexample mode
Detailed-balance weights need a finite total
Claim: on a countable state space, positive weights satisfying detailed balance always normalize to a stationary probability. Take the walk on that steps right with probability and left with probability , where . The weights satisfy detailed balance on every edge: and . But , because one of the two tails is a divergent geometric series. This walk is in fact transient and has no stationary probability at all. The repaired statement adds the hypothesis ; then the proposition shows that is a reversible stationary probability.
Worked examples
Worked example 2.10.4
(A two-state chain)
Let
Balance across the two states gives , so . Both directed edge fluxes equal ; diagonal equations are automatic. Thus . In fact every two-state chain with a strictly positive stationary distribution is reversible: the single nontrivial stationarity equation is exactly the single nontrivial detailed-balance equation.
Worked example 2.10.5
(Stationary circulation without reversibility)
On states , let . The uniform distribution is stationary: one unit of probability flow enters each state as one leaves it. But and . The reversed chain moves deterministically in the opposite direction, so it is not the forward chain. The chain is periodic; periodicity does not prevent stationarity, although it can prevent convergence from a fixed state.
If an aperiodic example is desired, replace by . Its uniform distribution remains stationary and while . The self-loops remove the period but not the circulation. Neither stationarity nor aperiodicity implies reversibility.
The third example uses detailed balance to find directly, and then checks that the reversed matrix is not the transpose.
Worked example 2.10.6
(A birth–death chain on three states)
Let
Only neighboring states communicate in one step, so detailed balance has two nontrivial equations: and . Hence and , and normalization gives . Check stationarity in the first column: . The chain is reversible, so . The transpose is different: its first row sums to , so is not even stochastic. The edge case here is that the transition graph is a path with no cycles; for such a graph the cycle test below is vacuous, and detailed balance can always be solved edge by edge.
A cycle test and its limits
The circulation example suggests that non-reversibility is a property of cycles. The following criterion makes this exact.
Theorem 2.10.7
(Cycle criterion for reversibility)
Let be a finite irreducible chain with exactly when . Then is reversible with respect to a strictly positive stationary distribution if and only if, for every directed cycle using positive transitions,
Proof
(Build the weights along paths from a root)
Necessity follows by multiplying detailed balance around the cycle and canceling the positive factors. For sufficiency, choose a root and set . Along a positive path from to , define the successive ratios . Any two paths give the same product: follow the first and then the reverse of the second to form a closed walk, and apply the cycle condition. Irreducibility supplies a path to every state. The weights then satisfy detailed balance on every positive edge; zero edges pose no problem by the symmetric-support assumption. Normalize the positive weights to obtain , which is stationary by the proposition.
Proof X-ray
Why the weights are well defined
The sufficiency proof defines by a product along a path, so its one real difficulty is independence of the path. That is exactly where the cycle condition is used: two paths from to combine into a closed walk, and the condition for closed walks makes their products agree. A closed walk may revisit states, but it decomposes into directed cycles, so the condition on cycles suffices.
The symmetric-support hypothesis is used twice: the ratio needs a nonzero denominator, and an edge with satisfies detailed balance trivially. Irreducibility makes every defined, and finiteness makes finite, which is the step that fails in the countable counterexample above. This is also why checking only one chosen cycle is insufficient when a graph has several independent cycles: a single unbalanced cycle makes two paths disagree.
Common mistakes
Common mistake
(Reversing with the transpose)
The reversed chain is , not . The two coincide only when is uniform, as for doubly stochastic matrices. In the birth–death example has a row summing to , so it is not a transition matrix at all.
Common mistake
(Concluding reversibility from stationarity)
Solving never certifies detailed balance by itself. The circulating chain is stationary for the uniform law, yet and . One must check every pair , or the cycle criterion on every cycle.
Practice with solutions
Quick check
(For , find and in stationarity.)
A two-state chain has one nontrivial balance equation.
Solution · Answer
The equation with total one gives . Detailed balance holds, so .
Quick check
(A three-state chain moves clockwise with probability and anticlockwise with probability . Find its stationary law and reversed transition probabilities. Is it reversible?)
Check the column sums first.
Solution · Answer
Each column sums to one, so . The reversed chain swaps the two directional probabilities: clockwise , anticlockwise . Since the corresponding edge fluxes differ, it is not reversible. Equivalently, the clockwise cycle has product and its reverse .
Quick check
(Suppose is reversible with a strictly positive stationary distribution . Show that for all .)
Compare a path with its reverse.
Solution · Answer
The reversed -step path has the same probability as the forward path. Sum the path equality over all intermediate states to obtain the stated identity. Equivalently, use and the telescoping formula for paths.
Quick check
(A student finds a positive vector satisfying detailed balance on a countably infinite state space and concludes that is a probability. Give a counterexample and identify the missing step.)
Try a symmetric walk.
Solution · Answer
For simple symmetric random walk on the integers, obeys detailed balance on every edge, but . Normalization requires a finite, nonzero total. These weights are an invariant measure, not a probability distribution.