The chains designed for MCMC in previous sections are reversible, and therefore the theory of reversible chains developed in this book is available. Unfortunately there is very little extra to say – in that sense, there is no “theory of MCMC”. What follows is rather fragmentary observations.
Consider the Metropolis chain
The requirement that a step of a chain be constructible as a proposal from followed by acceptance/rejection, is the requirement that . Recall the asymptotic variance rate
Given and , let be a reversible chain with and with stationary distribution . Then .
Proof. Reversibility of implies
and hence
where . So the result follows directly from Peskun’s lemma (yyy Lemma 11.5, to be moved elsewhere).
This result can be interpreted as saying that the Metropolis rates (11.5) are the optimal way of implementing a proposal-rejection scheme. Loosely speaking, a similar result holds in any natural Metropolis-like construction of a reversible chain using a acceptance probability.
It is important to notice that Lemma 11.1 does not answer the following question, which (except for highly symmetric graphs) seems intractable.
Question. Given a connected graph and a probability distribution on its vertices, consider the class of reversible chains with stationary distribution and with transitions only across edges of the graph. Within that class, which chain has smallest relaxation time?
Unfortunately, standard comparison theorems don’t take us much further in comparing MCMC methods. To see why, consider Metropolis on with isotropic Normal proposal steps. This has some relaxation time , where is the target density. For , the normal densities satisfy . So the comparison theorem (Chapter 3 Lemma 29) (yyy 9/2/94 version) shows
But this is no help in determining the optimal .
Though unrealistic in practical settings, the specialization of the Metropolis chain to the case where the proposal chain is i.i.d., that is where , is mathematically a natural object of study. In this setting the transition matrix (11.5) becomes
where . It turns out there is a simple and sharp coupling analysis, based on the trick of labeling states as so that (Liu [236] used this trick to give an eigenvalue analysis, extending part (b) below). Let be the chance that a proposed step from state is rejected (count a proposed step from state to as always accepted). So
For the Metropolis chain over independent proposals, with
states ordered as above,
(a)
(b) The relaxation time .
Proof. For the chain started at state , the time of the first acceptance of a proposed step satisfies
Recall from (yyy Chapter 4-3 section 1; 10/11/99 version) the notion of coupling. For this chain a natural coupling is obtained by using the same random variable to implement the accept/reject step (accept if ) in two versions of the chain. It is easy to check this coupling respects the ordering: if then . At time the fact that a proposed jump from is accepted implies that a jump from any other state must be accepted. So is a coupling time, and the coupling inequality (yyy Chapter 4-3 section 1.1; 10/11/99 version) implies . This establishes (a), and the general inequality implies . On the other hand, for the chain started at state , on the time- distribution is ; in other words
But this says that is an eigenvalue of (corresponding to the eigenvector ), establishing (b).
In the continuous-space setting, with a proposal distribution uniform on and target density with , part (b) implies the relaxation time equals . So (unsurprisingly) Metropolis-over-independent is comparable to the basic rejection sampling scheme (section 11.1.2), which gives an exact sample in mean steps.