11 Markov Chain Monte Carlo (January 8 2001)

11.8 Belongs in other chapters

yyy: add to what’s currently sec. 10.2 of Chapter 2, version 9/10/99, but which may get moved to the new Chapter 8.

Where π\pi does not vary with the parameter α\alpha we get a simple expression for ddα𝐙\frac{d}{d\alpha}{\bf Z}.

Lemma 11.4

In the setting of (yyy Chapter 2 Lemma 37), suppose π\pi does not depend on α\alpha. Then

ddα𝐙=𝐙𝐑𝐙.{\textstyle\frac{d}{d\alpha}}{\bf Z}={\bf Z}{\bf R}{\bf Z}.

xxx JF: I see this from the series expansion for 𝐙{\bf Z} – what to do about a proof, I delegate to you!

11.8.1 Pointwise ordered transition matrices

yyy: belongs somewhere in Chapter 3.

Recall from Chapter 2 section 3 (yyy 9/10/99 version) that for a function f:SRf:S\to R with iπifi=0\sum_{i}\pi_{i}f_{i}=0, the asymptotic variance rate is

σ2(𝐏,f):=limtt-1vars=1tf(Xs)=fΓf\sigma^{2}({\bf P},f):=\lim_{t}t^{-1}{\rm var}\ \sum_{s=1}^{t}f(X_{s})=f\Gamma f (11.19)

where Γij=πiZij+πjZji+πiπj-πiδij\Gamma_{ij}=\pi_{i}Z_{ij}+\pi_{j}Z_{ji}+\pi_{i}\pi_{j}-\pi_{i}\delta_{ij}. These individual-function variance rates can be compared between chains with the same stationary distribution, under a very strong “coordinatewise ordering” of transition matrices.

Lemma 11.5 (Peskun’s Lemma [280])

Let 𝐏{\bf P} and 𝐐{\bf Q} be reversible with the same stationary distribution π\pi. Suppose pijqijjip_{ij}\leq q_{ij}\ \forall j\neq i. Then σ2(𝐏,f)σ2(𝐐,f)\sigma^{2}({\bf P},f)\geq\sigma^{2}({\bf Q},f) for all ff with iπifi=0\sum_{i}\pi_{i}f_{i}=0.

Proof. Introduce a parameter 0α10\leq\alpha\leq 1 and write 𝐏α=(1-α)𝐏+α𝐐{\bf P}^{\alpha}=(1-\alpha){\bf P}+\alpha{\bf Q}. Write ()(\cdot)^{\prime} for ddα()\frac{d}{d\alpha}(\cdot) at α=0\alpha=0. It is enough to show

(σ2(𝐏,f))0.(\sigma^{2}({\bf P},f))^{\prime}\leq 0.

By (11.19)

(σ2(𝐏,f))=fΓf=2ijfiπizijfj.(\sigma^{2}({\bf P},f))^{\prime}=f\Gamma^{\prime}f=2\sum_{i}\sum_{j}f_{i}\pi_{% i}z^{\prime}_{ij}f_{j}.

By (yyy Lemma 11.4 above) 𝐙=𝐙𝐏𝐙{\bf Z}^{\prime}={\bf Z}{\bf P}^{\prime}{\bf Z}. By setting

gi=πifi; aij=zij/πj; wij=πipijg_{i}=\pi_{i}f_{i};\quad a_{ij}=z_{ij}/\pi_{j};\quad w_{ij}=\pi_{i}p_{ij}

we can rewrite the equality above as

(σ2(𝐏,f))=2g𝐀𝐖𝐀g.(\sigma^{2}({\bf P},f))^{\prime}=2\ g{\bf A}{\bf W}^{\prime}{\bf A}g.

Since 𝐀{\bf A} is symmetric wsith row-sums equal to zero, it is enough to show that 𝐖{\bf W}^{\prime} is non-negative definite. By hypothesis 𝐖{\bf W}^{\prime} is symmetric and wij0w^{\prime}_{ij}\geq 0 for jij\neq i. These properties imply that, ordering states arbitrarily, we may write

𝐖=i<jwij𝐌ij{\bf W}^{\prime}=\sum\sum_{i<j}w^{\prime}_{ij}{\bf M}^{ij}

where 𝐌ij{\bf M}^{ij} is the matrix whose only non-zero entries are m(i,i)=m(j,j)=-1;  m(i,j)=m(j,i)=1m(i,i)=m(j,j)=-1;\ m(i,j)=m(j,i)=1. Plainly 𝐌ij{\bf M}^{ij} is non-negative definite, hence so is 𝐖{\bf W}^{\prime}.