9.4 Making reversible chains from irreversible chains

Let ${\bf P}$ be an irreducible transition matrix on $I$ 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}^{*}$

 $\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: $\displaystyle{\bf Q}^{(1)}=\frac{1}{2}({\bf P}+{\bf P}^{*})$ The multiplicative reversiblization: $\displaystyle{\bf Q}^{(2)}={\bf P}{\bf P}^{*}$ The Metropolis reversiblization; $\displaystyle{\bf Q}^{(3)}_{i,j}=\min(p_{i,j},p^{*}_{j,i}),\ j\neq i.$

Of these three construction, only ${\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 $(i_{1},\ldots,i_{n})$.

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

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

(${\bf Q}^{(3)}$). Here a “typical” $i$ 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 $L^{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 ${\bf Z}({\bf P}^{*}-{\bf P})\geq 0$.

Conjecture 9.22

$\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$,

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

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

 $\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^{-1}\mbox{trace }(\sum_{m=0}^{\infty}{\bf V}^{m})({\bf V}-{\bf V}^{T})\leq 0.$

Letting $s\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 $n$-state chain

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

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

Corollary 9.23

$\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

 $\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

 $\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)$
 $=\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\leq\lambda\leq 1$ let ${\bf P}(\lambda)=(1-\lambda){\bf P}+\lambda{\bf P}^{*}$, so that ${\bf P}(1/2)$ is the “additive reversiblization” in Lemma 9.20. Consider the average hitting time parameters $\tau_{0}=\tau_{0}(\lambda)$ from Chapter 4.

Corollary 9.24

Assuming Conjecture 9.22 is true, $\tau_{0}(\lambda)\leq\tau_{0}(1/2)$ for all $0\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

 $\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 $0$. Write $\frac{d}{d\theta}\$ for the derivative at $\theta=0$. Then, writing $N_{i}(t)$ for the number of visits to $i$ before time $t$,

 $\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 $\sum_{j}$ term gives the effect on $ET_{b}$ of a ${\bf Q}$-step from $i$. Using general identities from Chapter 2 yyy, and (9.21), this becomes

 $\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

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

Then the expression above simplifies to

 $\frac{d}{d\theta}\ E_{a}T_{b}=\sum_{i}(z_{bi}-z_{ai})\ \sum_{j}q_{ij}z_{jb}/% \pi_{b}.$

Averaging over $a$, using $\sum_{a}\pi_{a}z_{ai}=0$,

 $\frac{d}{d\theta}\ E_{\pi}T_{b}=\sum_{i}\sum_{j}z_{bi}q_{ij}z_{jb}/\pi_{b}$

and then averaging over $b$,

 $\frac{d}{d\theta}\ \tau_{0}=\mbox{ trace }{\bf Z}{\bf Q}{\bf Z}=\mbox{ trace }% {\bf Z}^{2}{\bf Q}.$

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

 $\displaystyle\frac{d}{d\lambda}\tau_{0}(\lambda)$ $\displaystyle=$ $\displaystyle\mbox{ trace }{\bf Z}^{2}(\lambda)({\bf P}^{*}-{\bf P})$ $\displaystyle=$ $\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 $\geq 0$, implying the conclusion of Corollary 9.24.