The chain that runs the same backwards

Finding a chain’s long-run shares means solving a linear system, and for a chain of any size that is real work. For one class of chains it is no work at all: the answer is written on the diagram.

The class is the reversible chains, and the condition defining them says something much more specific than the shares do not move. It says the traffic along each edge is equal in the two directions, one edge at a time.

Two conditions, and which is stronger #

A distribution $\pi$ is stationary when $\sum_i \pi_i P_{ij} = \pi_j$ for every $j$: the total flowing into each state equals the total flowing out.

It satisfies detailed balance when $\pi_i P_{ij} = \pi_j P_{ji}$ for every pair $i, j$: the flow from $i$ to $j$ equals the flow back, edge by edge.

Detailed balance implies stationarity immediately — sum the balance equations over $i$ and the left side is the inflow to $j$ while the right side is $\pi_j$ times the row sum, which is $\pi_j$. The converse is false, and the right-hand panel of the hero figure is a counterexample.

So detailed balance is a local condition and stationarity is a global one, and the local one is strictly stronger. That is the useful direction: a local condition can be checked and solved edge by edge.

Weights on a graph give the answer free #

The construction that makes this concrete is a walk on a weighted graph.

Put a non-negative weight $w_{ij} = w_{ji}$ on each pair of states, let $d_i = \sum_j w_{ij}$ be the total weight at $i$, and define $P_{ij} = w_{ij}/d_i$. That is a legitimate transition matrix as long as every $d_i$ is positive.

Now check detailed balance with $\pi_i = d_i / \sum_k d_k$:

$$\pi_i P_{ij} = \frac{d_i}{\sum_k d_k}\cdot\frac{w_{ij}}{d_i} = \frac{w_{ij}}{\sum_k d_k},$$

which is symmetric in $i$ and $j$ because the weights are. So the balance equation holds, and $\pi$ is stationary.

No system was solved. The stationary distribution is proportional to the total weight at each state, which is a number readable off the drawing, and the figure checks it against the answer from Gaussian elimination to twelve decimal places.

The simplest case is the most used #

Take every weight equal to one on the edges of a graph and zero elsewhere: a walk that steps to a uniformly chosen neighbour. Then $d_i$ is the degree of $i$, and the stationary share of a state is its degree over twice the number of edges.

That single sentence answers an enormous number of questions. On a cycle every state has degree two and the shares are equal. On a star the centre has degree $n-1$ and each leaf has degree one, so the centre holds half the time in the long run whatever $n$ is. On a chessboard’s knight-move graph the shares are proportional to how many squares each square’s knight can reach — which is a fact about the board, not about the walk.

The knight case is worth stating because the answer is surprising and takes one line. A knight walking at random on an empty board spends its long-run time in proportion to its mobility, so it is in a corner a quarter as often as in the middle — and the expected time for it to return to a corner is $168$ moves, which follows from the reciprocal identity the next rung is about.

The knight, done properly #

The chessboard example is worth completing, because it is the case where reading the answer off the graph beats every alternative by the largest margin.

A knight on an empty board has between two and eight moves depending where it stands: two from a corner, three from the squares beside a corner, and eight from any of the sixteen central squares. Adding those over the sixty-four squares gives $336$, which is twice the number of edges in the knight’s graph.

So a knight moving to a uniformly chosen legal square has stationary share $d_i/336$ at square $i$. The corner’s share is $2/336 = 1/168$; a central square’s is $8/336 = 1/42$. The knight is four times as likely to be found in the middle as in a corner, and the ratio is exactly the ratio of the mobilities.

Solving that as a linear system means sixty-four equations in sixty-four unknowns. Reading it off the degrees takes one addition. The saving is entirely because the chain is reversible, and it is reversible because the knight’s move relation is symmetric — if a knight can go from here to there it can come back.

The chain with a current #

The right-hand panel is the reason the distinction matters, and it is the smallest chain that makes it.

Three states in a cycle, stepping forward with probability $0.8$ and backward with $0.2$. By symmetry the stationary distribution is uniform — each state holds a third — and the figure checks that by solving.

Detailed balance fails. The flow from $A$ to $B$ is $\tfrac13 \times 0.8$ and the flow back is $\tfrac13 \times 0.2$, so there is a net current of $0.2$ round the cycle, and the figure computes it and checks it is the same across all three edges.

A film of this chain played backwards is a different chain — one that goes round the other way — and that is what reversibility means and what this chain lacks. Stationarity says each state’s totals balance; reversibility says each edge balances; and a circulating current satisfies the first while violating the second.

The current is a conserved quantity #

The number the figure prints for the cycle is worth a section, because it turns out to be more than a measurement of one chain’s asymmetry.

Define the net flow across an edge as $\pi_i P_{ij} - \pi_j P_{ji}$. Stationarity says that the net flows out of each state add to zero — what comes in goes out — so the net flows form what a physicist would call a divergence-free field on the graph, and a graph theorist would call a circulation.

On a graph with no cycles the only such field is zero, which is the earlier observation that a tree is always reversible. On a graph with one cycle the field is determined up to a scalar by conservation, so the net flow is the same across every edge of that cycle — which is exactly what the figure checks, finding $0.2$ on all three edges of the triangle.

So the current is not a property of an edge but of a cycle, and the reversible chains are the ones whose currents all vanish. On a graph with many independent cycles there is one current per cycle, and the space of possible circulations has dimension equal to the number of independent cycles.

That is the same count that appears whenever a network’s independent loops are counted — the cycle rank of a graph — and it says how far from reversible a chain on a given graph is able to be.

What reversibility buys #

The reason to care is that reversible chains have a spectral theory that general chains do not.

A reversible chain’s transition matrix is self-adjoint with respect to the inner product weighted by $\pi$. So its eigenvalues are all real, its eigenvectors are orthogonal in that inner product, and the whole apparatus of symmetric matrices applies.

For a general chain the eigenvalues can be complex, and the cycle in the figure has a pair of them at $e^{\pm 2\pi i/3}$ times something — which is exactly what a rotation looks like spectrally. Complex eigenvalues mean the approach to stationarity spirals rather than decays, and no orthogonal basis is available.

That difference is not cosmetic. Every clean statement about how a chain approaches its stationary distribution is a statement about eigenvalues, and having them real and having an orthogonal basis is what makes such statements provable rather than merely true.

Every two-state chain is reversible #

A small fact worth knowing, since it explains why the phenomenon needs three states to appear.

Take any chain on two states with $P_{12} = a$ and $P_{21} = b$, both positive. The stationary distribution is $\pi = (b, a)/(a+b)$, and detailed balance asks whether $\pi_1 P_{12} = \pi_2 P_{21}$ — that is, whether $ba = ab$. It always does.

So there is no two-state counterexample, and the smallest chain that is stationary without being reversible has three states. That is the cycle in the figure, and any three-state chain with a current is essentially it.

The reason is structural: with two states there is only one edge, so the local condition and the global one are the same equation. A current has to go round something, and there is nothing to go round until there are three states.

The distinction between local and global constraints is invisible until the system is large enough to have a cycle, which is a general fact about such conditions and not a fact about chains. The lazy two-state chain the first rung draws is therefore reversible, as every two-state chain is, and the fact was never mentioned because it could not fail.

Kolmogorov’s criterion #

There is a way to test reversibility without knowing $\pi$ at all, which is useful since $\pi$ is usually what one is trying to find.

Kolmogorov’s criterion: a chain is reversible exactly when, for every cycle of states $i_1 \to i_2 \to \cdots \to i_k \to i_1$, the product of the transition probabilities round the cycle equals the product round the reverse cycle.

The cycle in the figure fails it in the smallest possible way: forward the product is $0.8^3 = 0.512$ and backward it is $0.2^3 = 0.008$, and those differ by a factor of sixty-four. A walk on a weighted graph passes it automatically, since the product round any cycle is the same as the reverse by symmetry of the weights.

The criterion turns a question about an unknown distribution into a question about products round cycles, which is checkable from the matrix alone. It is the practical test, and it is also the reason trees are always reversible: a tree has no cycles, so the condition is vacuous.

Designing a chain to have a given answer #

The direction that makes reversibility valuable in practice is backwards: fix the distribution wanted, then build a chain with it.

Detailed balance is one equation per edge in the unknowns $P_{ij}$, so with $\pi$ given there is a great deal of freedom, and the standard solution is to propose a move and accept it with a probability that makes the equation hold. That is the construction a walk that samples a distribution is about, and its whole correctness argument is the balance equation checked edge by edge.

The reason detailed balance rather than stationarity is used there is exactly the local-versus-global distinction. Stationarity is one equation per state involving every state that can reach it; detailed balance is one equation per edge involving two states. The second can be arranged by a rule that looks at one proposed move at a time, and the first cannot.

So the stronger condition is the easier one to impose, which is a pleasant inversion and the reason nearly every constructed chain in use is reversible.

Conductance, and the electrical picture #

The weighted-graph construction has a second reading that makes several theorems obvious, and it is worth having even in outline.

Treat each edge weight as an electrical conductance and the graph as a resistor network. Then the stationary distribution is proportional to the total conductance at each node; the probability that a walk from $a$ reaches $b$ before returning to $a$ is the effective conductance between them divided by $a$’s total; and expected hitting times are voltages.

That correspondence is exact, not an analogy, and it holds precisely for reversible chains. The reason is that both objects satisfy the same equations: a harmonic function on a network is one whose value at each node is the conductance-weighted average of its neighbours’ values, and a hitting probability is harmonic away from its boundary.

The consequence is that facts about resistors become facts about walks. Adding an edge cannot increase effective resistance, so adding an edge cannot make a walk take longer to get somewhere in a certain precise sense; resistances in series add, so hitting times on a path add; and the recurrence of a walk in low dimensions becomes the question of whether an infinite grid has finite resistance to infinity, which is where Polya’s theorem gets its cleanest proof.

None of that is available for a non-reversible chain, because there is no network whose equations match. The electrical picture is exactly the reversible case.

Where the term comes from #

The word is literal and worth unpacking, because it explains the whole definition.

Run a reversible chain from its stationary distribution and record a stretch of the trajectory. Then the reversed stretch has exactly the same probability as the forward one: for any sequence of states, $\pi_{i_0}P_{i_0i_1}\cdots P_{i_{k-1}i_k}$ equals $\pi_{i_k}P_{i_ki_{k-1}}\cdots P_{i_1i_0}$, which follows by applying detailed balance $k$ times.

So a recording of the chain, played backwards, is statistically indistinguishable from one played forwards. There is no arrow of time in it.

The circulating cycle has one: played backwards it goes the other way round, and a long enough recording reveals which direction was forward. Reversibility is the absence of an arrow of time, and that is a much more vivid statement of the condition than the equations are.

What the pictures cannot show #

The shares are numbers, and the check is not visible. The figure prints each state’s share beside it and asserts it against the answer from solving; a reader sees two decimals and not the elimination behind the second one.

The current is drawn as a label rather than as motion. A net flow of $0.2$ round a cycle is a statement about long-run traffic, and a still picture of arrows cannot show traffic. The three arrowheads say which way is forward and the number says how much.

And the eigenvalues are not drawn at all. The claim that a reversible chain has real eigenvalues and the cycle has complex ones is the substance of the section on what reversibility buys, and it is arithmetic on the matrix rather than anything in the diagram.

Where the ladder goes next #

Both this rung and the first computed the stationary distribution as a limit or as a solve, and neither said what it means for a single trajectory. The next rung closes that: one walk, run long enough, spends a share of its time in each state equal to that state’s stationary share, and the expected time to come back to a state is exactly the reciprocal of its share.

Sideways: a walk that samples a distribution is detailed balance used as a design principle, and the chain that stops is what happens when there is no stationary distribution to find.

What is worth carrying away #

A stronger hypothesis is often the easier one to arrange.

Detailed balance implies stationarity and not conversely, so it is the more demanding condition — and it is the one that can be checked edge by edge, imposed one move at a time, and read off a drawing. Stationarity, the weaker condition, requires solving a system.

The reason is that the stronger condition is local. A global constraint on a system of $n$ states couples all of them; a local one couples two, and $n^2$ small problems are easier than one large one. Whenever a condition can be strengthened into a local form at acceptable cost, the strengthening usually pays for itself.

The cost here is real and worth naming. Reversible chains are a genuine restriction — the cycle in the figure is not one, and neither is any process with a preferred direction — so imposing detailed balance rules out models that may be the right ones. What makes the trade good in practice is that when a chain is being designed rather than observed, the direction is not wanted anyway, and the freedom given up was never going to be used.