Let be an irreducible transition matrix on with stationary distribution . The following straightforward lemma records several general ways in which to construct from a transition matrix for which the associated chain still has stationary distribution but is reversible. These methods all involve the time-reversed matrix
and so in practice can only be used when we know explicitly (as we have observed several times previously, in general we cannot write down a useful explicit expression for in the irreversible setting).
The following definitions each give a transition matrix which is reversible with respect to .
The additive reversiblization: | ||||
The multiplicative reversiblization: | ||||
The Metropolis reversiblization; |
Of these three construction, only is automatically irreducible. Consider for instance the “patterns in coin tossing” example (Chapter 2 Example yyy). Here are the distributions of a step of the chains from state .
(). To or or or , with probability each.
(). To or , with probability each. So the state space decomposes into -element classes.
(). Here a “typical” is isolated.
We shall discuss two aspects of the relationship between irreversible chains and their reversibilizations.
Because the theory of convergence to stationarity is nicer for reversible chains, a natural strategy to study an irreversible chain (transition matrix ) would be to first study a reversibilization and then seek some general result relating properties of the -chain to properties of the -chain. There are (see Notes) general results relating spectra, but we don’t pursue these because (cf. section 9.5) there seems no useful way to derive finite-time results for irreversible chains from spectral gap estimates.
xxx Persi, Fill etc stuff
Here are a matrix-theoretic result and conjecture, whose probabilistic significance (loosely relating to mean hitting times and reversiblization) will be discussed below. As usual is the fundamental matrix associated with , and is the time-reversal.
trace .
.
Proposition 9.21 is essentially due to Fiedler et al [146]. In fact, what is proved in ([146], p. 91) is that, for a positive matrix with largest eigenvalue ,
(9.19) |
Applying this to for gives
Letting gives the Proposition as stated.
The proof in [146] of (9.19) has no simple probabilistic interpretation, and it would be interesting to find a probabilistic proof. It is not clear to me whether Conjecture 9.22 could be proved in a similar way.
Here is the probabilistic interpretation of Proposition 9.21. Recall the elementary result (yyy) that in a -state chain
(9.20) |
The next result shows that replacing by gives an inequality. This arose as an ingredient in work of Tetali [327] discussed at xxx.
.
Proof. We argue backwards. By (9.20), the issue is to prove
Using Lemma yyy, the quantity in question equals
Here is the motivation for Conjecture 9.22. For let , so that is the “additive reversiblization” in Lemma 9.20. Consider the average hitting time parameters from Chapter 4.
Assuming Conjecture 9.22 is true, for all .
In other words, making the chain “more reversible” tends to increase mean hitting times.
Proof. This depends on results about differentiating with respect to the transition matrix, which we present as slightly informal calculations. Introduce a “perturbation” matrix such that
(9.21) |
Then is a transition matrix, for is some neighborhood of . Write for the derivative at . Then, writing for the number of visits to before time ,
This holds because the term gives the effect on of a -step from . Using general identities from Chapter 2 yyy, and (9.21), this becomes
Now specialize to the case where is the stationary distribution for each , that is where
Then the expression above simplifies to
Averaging over , using ,
and then averaging over ,
So consider in Corollary 9.24. Then
and Conjecture 9.22 would imply this is , implying the conclusion of Corollary 9.24.