9 A Second Look at General Markov Chains (April 21, 1995)

9.4 Making reversible chains from irreversible chains

Let 𝐏{\bf P} be an irreducible transition matrix on II with stationary distribution π\pi. The following straightforward lemma records several general ways in which to construct from 𝐏{\bf P} a transition matrix 𝐐{\bf Q} for which the associated chain still has stationary distribution π\pi but is reversible. These methods all involve the time-reversed matrix 𝐏*{\bf P}^{*}

πipij=πjpji*\pi_{i}p_{ij}=\pi_{j}p^{*}_{ji}

and so in practice can only be used when we know π\pi explicitly (as we have observed several times previously, in general we cannot write down a useful explicit expression for π\pi in the irreversible setting).

Lemma 9.20

The following definitions each give a transition matrix 𝐐{\bf Q} which is reversible with respect to π\pi.

The additive reversiblization: 𝐐(1)=12(𝐏+𝐏*)\displaystyle{\bf Q}^{(1)}=\frac{1}{2}({\bf P}+{\bf P}^{*})
The multiplicative reversiblization: 𝐐(2)=𝐏𝐏*\displaystyle{\bf Q}^{(2)}={\bf P}{\bf P}^{*}
The Metropolis reversiblization; 𝐐i,j(3)=min(pi,j,pj,i*),  ji.\displaystyle{\bf Q}^{(3)}_{i,j}=\min(p_{i,j},p^{*}_{j,i}),\ j\neq i.

Of these three construction, only 𝐐(1){\bf Q}^{(1)} 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 (i1,,in)(i_{1},\ldots,i_{n}).

(𝐐(1){\bf Q}^{(1)}). To (i2,,in,0)(i_{2},\ldots,i_{n},0) or (i2,,in,1)(i_{2},\ldots,i_{n},1) or (0,i1,,in-1)(0,i_{1},\ldots,i_{n-1}) or (1,i1,,in-1)(1,i_{1},\ldots,i_{n-1}), with probability 1/41/4 each.

(𝐐(2){\bf Q}^{(2)}). To (0,i2,,in)(0,i_{2},\ldots,i_{n}) or (1,i2,,in)(1,i_{2},\ldots,i_{n}), with probability 1/21/2 each. So the state space decomposes into 22-element classes.

(𝐐(3){\bf Q}^{(3)}). Here a “typical” ii is isolated.

We shall discuss two aspects of the relationship between irreversible chains and their reversibilizations.

9.4.1 Mixing times

Because the theory of L2L^{2} convergence to stationarity is nicer for reversible chains, a natural strategy to study an irreversible chain (transition matrix 𝐏{\bf P}) would be to first study a reversibilization 𝐐{\bf Q} and then seek some general result relating properties of the 𝐏{\bf P}-chain to properties of the 𝐐{\bf Q}-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

9.4.2 Hitting times

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 𝐙{\bf Z} is the fundamental matrix associated with 𝐏{\bf P}, and 𝐏*{\bf P}^{*} is the time-reversal.

Proposition 9.21

trace 𝐙(𝐏*-𝐏)0{\bf Z}({\bf P}^{*}-{\bf P})\geq 0.

Conjecture 9.22

trace 𝐙2(𝐏*-𝐏)0\mbox{trace }{\bf Z}^{2}({\bf P}^{*}-{\bf P})\geq 0.

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 𝐕{\bf V} with largest eigenvalue <1<1,

trace (m=1𝐕m)(𝐕-𝐕T)0.\mbox{trace }(\sum_{m=1}^{\infty}{\bf V}^{m})({\bf V}-{\bf V}^{T})\leq 0. (9.19)

Applying this to vij=sπi1/2pijπj-1/2v_{ij}=s\pi_{i}^{1/2}p_{ij}\pi_{j}^{-1/2} for s<1s<1 gives

trace (m=0sm(pij(m)-πj))(𝐏-𝐏*)=trace (m=0sm𝐏(m))(𝐏-𝐏*)\mbox{trace }(\sum_{m=0}^{\infty}s^{m}(p^{(m)}_{ij}-\pi_{j}))({\bf P}-{\bf P}^% {*})=\mbox{trace }(\sum_{m=0}^{\infty}s^{m}{\bf P}^{(m)})({\bf P}-{\bf P}^{*})
=s-1trace (m=0𝐕m)(𝐕-𝐕T)0.=s^{-1}\mbox{trace }(\sum_{m=0}^{\infty}{\bf V}^{m})({\bf V}-{\bf V}^{T})\leq 0.

Letting s1s\uparrow 1 gives the Proposition as stated. \Box

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 nn-state chain

abπapabEbTa=n-1.\sum_{a}\sum_{b}\pi_{a}p_{ab}E_{b}T_{a}=n-1. (9.20)

The next result shows that replacing EbTaE_{b}T_{a} by EaTbE_{a}T_{b} gives an inequality. This arose as an ingredient in work of Tetali [327] discussed at xxx.

Corollary 9.23

abπapabEaTbn-1\sum_{a}\sum_{b}\pi_{a}p_{ab}E_{a}T_{b}\leq n-1.

Proof. We argue backwards. By (9.20), the issue is to prove

abπapab(EbTa-EaTb)0.\sum_{a}\sum_{b}\pi_{a}p_{ab}(E_{b}T_{a}-E_{a}T_{b})\geq 0.

Using Lemma yyy, the quantity in question equals

abπapab(Zaaπa-Zbaπa-Zbbπb+Zabπb)\sum_{a}\sum_{b}\pi_{a}p_{ab}\left(\frac{Z_{aa}}{\pi_{a}}-\frac{Z_{ba}}{\pi_{a% }}-\frac{Z_{bb}}{\pi_{b}}+\frac{Z_{ab}}{\pi_{b}}\right)
=trace 𝐙-trace 𝐏𝐙-trace 𝐙+trace 𝐏*𝐙=trace (𝐏*-𝐏)𝐙0.=\mbox{trace }{\bf Z}-\mbox{trace }{\bf P}{\bf Z}-\mbox{trace }{\bf Z}+\mbox{% trace }{\bf P}^{*}{\bf Z}=\mbox{trace }({\bf P}^{*}-{\bf P}){\bf Z}\geq 0.

\Box

Here is the motivation for Conjecture 9.22. For 0λ10\leq\lambda\leq 1 let 𝐏(λ)=(1-λ)𝐏+λ𝐏*{\bf P}(\lambda)=(1-\lambda){\bf P}+\lambda{\bf P}^{*}, so that 𝐏(1/2){\bf P}(1/2) is the “additive reversiblization” in Lemma 9.20. Consider the average hitting time parameters τ0=τ0(λ)\tau_{0}=\tau_{0}(\lambda) from Chapter 4.

Corollary 9.24

Assuming Conjecture 9.22 is true, τ0(λ)τ0(1/2)\tau_{0}(\lambda)\leq\tau_{0}(1/2) for all 0λ10\leq\lambda\leq 1.

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 𝐐{\bf Q} such that

jqij=0i; qij=0 whenever pij=0.\sum_{j}q_{ij}=0\ \forall i;\ \ q_{ij}=0\mbox{ whenever }p_{ij}=0. (9.21)

Then 𝐏+θ𝐐{\bf P}+\theta{\bf Q} is a transition matrix, for θ\theta is some neighborhood of 00. Write ddθ\frac{d}{d\theta}\ for the derivative at θ=0\theta=0. Then, writing Ni(t)N_{i}(t) for the number of visits to ii before time tt,

ddθEaTb=iEaNi(Tb)jqijEjTb.\frac{d}{d\theta}\ E_{a}T_{b}=\sum_{i}E_{a}N_{i}(T_{b})\ \sum_{j}q_{ij}E_{j}T_% {b}.

This holds because the j\sum_{j} term gives the effect on ETbET_{b} of a 𝐐{\bf Q}-step from ii. Using general identities from Chapter 2 yyy, and (9.21), this becomes

ddθEaTb=i(πi(zab-zbb)πb+zbi-zai)jqijzjb/πb.\frac{d}{d\theta}\ E_{a}T_{b}=\sum_{i}\left(\frac{\pi_{i}(z_{ab}-z_{bb})}{\pi_% {b}}+z_{bi}-z_{ai}\right)\ \sum_{j}q_{ij}z_{jb}/\pi_{b}.

Now specialize to the case where π\pi is the stationary distribution for each 𝐏+θ𝐐{\bf P}+\theta{\bf Q}, that is where

iπiqij=0j.\sum_{i}\pi_{i}q_{ij}=0\ \forall j.

Then the expression above simplifies to

ddθEaTb=i(zbi-zai)jqijzjb/πb.\frac{d}{d\theta}\ E_{a}T_{b}=\sum_{i}(z_{bi}-z_{ai})\ \sum_{j}q_{ij}z_{jb}/% \pi_{b}.

Averaging over aa, using aπazai=0\sum_{a}\pi_{a}z_{ai}=0,

ddθEπTb=ijzbiqijzjb/πb\frac{d}{d\theta}\ E_{\pi}T_{b}=\sum_{i}\sum_{j}z_{bi}q_{ij}z_{jb}/\pi_{b}

and then averaging over bb,

ddθτ0= trace 𝐙𝐐𝐙= trace 𝐙2𝐐.\frac{d}{d\theta}\ \tau_{0}=\mbox{ trace }{\bf Z}{\bf Q}{\bf Z}=\mbox{ trace }% {\bf Z}^{2}{\bf Q}.

So consider λ<1/2\lambda<1/2 in Corollary 9.24. Then

ddλτ0(λ)\displaystyle\frac{d}{d\lambda}\tau_{0}(\lambda) =\displaystyle= trace 𝐙2(λ)(𝐏*-𝐏)\displaystyle\mbox{ trace }{\bf Z}^{2}(\lambda)({\bf P}^{*}-{\bf P})
=\displaystyle= (1-2λ)-1 trace 𝐙2(λ)(𝐏*(λ)-𝐏(λ))\displaystyle(1-2\lambda)^{-1}\mbox{ trace }{\bf Z}^{2}(\lambda)({\bf P}^{*}(% \lambda)-{\bf P}(\lambda))

and Conjecture 9.22 would imply this is 0\geq 0, implying the conclusion of Corollary 9.24.