Recall denotes the transition matrix and the stationary distribution of a finite irreducible discrete-time chain . Call the chain reversible if
(3.1) |
Equivalently, suppose (for given irreducible ) that is a probability distribution satisfying (3.1). Then is the unique stationary distribution and the chain is reversible. This is true because (3.1), sometimes called the detailed balance equations, implies
and therefore satisfies the balance equations of (1) in Chapter 2. ††margin: 9/10/99 version
The name reversible comes from the following fact. If is the stationary chain, that is, if has distribution , then
More vividly, given a movie of the chain run forwards and the same movie run backwards, you cannot tell which is which.
It is elementary that the same symmetry property (3.1) holds for the -step transition matrix :
and thence for the matrix of (6) in Chapter 2: ††margin: 9/10/99 version
(3.2) |
But beware that the symmetry property does not work for mean hitting times: the assertion
is definitely false in general (see the Notes for one intuitive explanation). See Chapter 7 ††margin: 1/31/94 versionfor further discussion. The following general lemma ††margin: The lemma has been copied here from Section 1.2 of Chapter 7 (1/31/94 version); reminder: it still needs to be deleted there! will be useful there.
For an irreducible reversible chain, the following are equivalent.
(a)
(b) .
Proof. In either case the stationary distribution is uniform—under (a) by letting , and under (b) by taking , implying . So by reversibility for and . But recall from Chapter 2 ††margin: 9/10/99 versionLemma 25 that the generating functions
satisfy
(3.3) |
For we have seen that , and hence by (3.3)
which is the assertion of Lemma 3.1.
The discussion above extends to continuous time with only notational changes, e.g., the detailed balance equation (3.1) becomes
(3.4) |
For a general chain we can define the time-reversed chain to have transition matrix where
so that the chain is reversible iff . One can check [cf. (3.2)]
(3.5) |
The stationary -chain is just the stationary -chain run backwards in time. Consider Examples 16 and 22 from Chapter 2. ††margin: 9/10/99 versionIn Example 16 (patterns in coin tossing) the time-reversal just “shifts left” instead of shifting right, i.e., from the possible transitions are to and . In Example 22 the time-reversal just reverses the direction of motion around the -cycle:
Warning. These examples are simple because the stationary distributions are uniform. If the stationary distribution has no simple form then typically will have no simple form.
A few facts about reversible chains are really specializations of facts about general chains which involve both and . Here is a simple instance.
For states of a reversible chain,
The explanation is that in a general chain we have
(3.6) |
where refers to the time-reversed chain . Equality (3.6) is intuitively obvious when we visualize running a movie backwards. But a precise argument requires a little sophistication (see Notes). It is however straightforward to verify (3.6) using (3.5) and the mean hitting time formula .
We shall encounter several results which have amusing interpretations as cat-and-mouse games. The common feature of these games is that the cat moves according to a transition matrix and the mouse moves according to the time-reversed transition matrix .
Cat-and-mouse game 1. Both animals are placed at the same state, chosen according to the stationary distribution. The mouse makes a jump according to , and then stops. The cat starts moving according to and continues until it finds the mouse, after steps.
The notable feature of this game is the simple formula for :
(3.7) |
This is simple once you see the right picture. Consider the stationary -chain . We can specify the game in terms of that chain by taking the initial state to be , and the mouse’s jump to be to , and the cat’s moves to be to . So with
And .
Cat-and-mouse game 2. This game, and Proposition 3.3, are rephrasings of results of Coppersmith et al [101]. Think of the cat and the mouse as pieces in a solitaire board game. The player sees their positions and chooses which one to move: if the cat is chosen, it makes a move according to , and if the mouse is chosen, it makes a move according to . Let denote the number of moves until the cat and mouse meet. Then one expects the mean to depend on the initial positions of (cat, mouse) and on the player’s strategy. But consider the example of asymmetric random walk on a -cycle, with (say) chance of moving clockwise and chance of moving counterclockwise. A moment’s thought reveals that the distance (measured clockwise from cat to mouse) between the animals does not depend on the player’s strategy, and hence neither does . In general does depend on the strategy, but the following result implies that the size of the effect of strategy changes can be bounded in terms of a measure of non-symmetry of the chain.
Regardless of strategy,
where hitting times refer to the -chain.
Proof. Consider the functions ††margin: Symbol used here is “defined identically to be”.
The first-step recurrences for and give
(3.8) | |||||
(3.9) |
By the mean hitting time formula
so we may rewrite (3.9) as
(3.10) |
Now let be the positions of (cat, mouse) after moves according to some strategy. Consider
Equalities (3.8) and (3.10) are exactly what is needed to verify
So the optional stopping theorem says , that is,
(3.11) |
But and , so
and the result follows from (3.11).
Remarks. Symmetry conditions in the reversible setting are discussed in Chapter 7. ††margin: 1/31/94 versionVertex-transitivity forces to be independent of , and hence in the present setting implies regardless of strategy. For a reversible chain without this symmetry condition, consider attaining the min and max of . The Proposition then implies and the bounds are attained by keeping one animal fixed. But for general initial states the bounds of the Proposition are not attained. Indeed, the proof shows that to attain the bounds we need a strategy which forces the animals to meet at states attaining the extrema of . Finally, in the setting of random walk on a -vertex graph we can combine Proposition 3.3 with mean hitting time bounds from Chapter 6 ††margin: 10/31/94 versionto show that is at worst .
Recall from Chapter 2 ††margin: 9/10/99 versionSection 3 that for a function with , the asymptotic variance rate ††margin: This subsection adapted from Section 8.1 of Chapter MCMC (1/8/01 version); reminder: it still needs to be deleted there! is
(3.12) |
where . These individual-function variance rates can be compared between chains with the same stationary distribution, under a very strong “(off-diagonal) entrywise ordering” of reversible transition matrices.
Let and be reversible with the same stationary distribution . Suppose for all . Then for all with .
Proof. Introduce a parameter and write
Write for . It is enough to show
By (3.12)
By Chapter MCMC ††margin: 1/8/01 versionLemma 4, . By setting
we find and can rewrite the equality above as
Since is symmetric, it is enough to show that is ††margin: agreed: use negative semidefinite rather than nonpositive definite throughout negative semidefinite. By hypothesis is symmetric with zero row-sums and for . Ordering states arbitrarily, we may write
where is the matrix whose only nonzero entries are and . Plainly is negative semidefinite, hence so is .