# On the convergence rate of the “out-of-order”
block Gibbs sampler

Zhumengmeng Jin and James P. Hobert
Department of Statistics
University of Florida

(October 2021)

###### Abstract

It is shown that a seemingly harmless reordering of the steps in a block Gibbs
sampler can actually invalidate the algorithm. In particular, the Markov chain
that is simulated by the “out-of-order” block Gibbs sampler does not have the
correct invariant probability distribution. However, despite having the wrong
invariant distribution, the Markov chain converges at the same rate as the
original block Gibbs Markov chain. More specifically, it is shown that either
both Markov chains are geometrically ergodic (with the same geometric rate of
convergence), or neither one is. These results are important from a practical
standpoint because the (invalid) out-of-order algorithm may be easier to
analyze than the (valid) block Gibbs sampler (see, e.g., Yang and Rosenthal
(2019)).

##  1 Introduction

Let $\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$ be a joint probability
distribution having support
${\mathsf{X}}\times{\mathsf{Y}}\times{\mathsf{Z}}$, and suppose we wish to
construct a Gibbs sampler for this distribution. (Additional mathematical
rigor will be introduced in Section 2.) The simplest version of the Gibbs
sampler is that which cycles through the so-called full conditional
distributions, $\Pi_{X|YZ}(\mathrm{d}x|y,z)$, $\Pi_{Y|XZ}(\mathrm{d}y|x,z)$,
and $\Pi_{Z|XY}(\mathrm{d}z|x,y)$. Let
$\Gamma=\\{(X_{n},Y_{n},Z_{n})\\}_{n=0}^{\infty}$ denote the corresponding
Markov chain. If the current state of the chain $\Gamma$ is
$(X_{n},Y_{n},Z_{n})=(x,y,z)$, then we move to the next state,
$(X_{n+1},Y_{n+1},Z_{n+1})$, using the following well-known three step
procedure.

Iteration $n+1$ of the Gibbs sampler:

  1. 1.

Draw $X_{n+1}\sim\Pi_{X|YZ}(\cdot|y,z)$, and call the observed value
$x^{\prime}$.

  2. 2.

Draw $Y_{n+1}\sim\Pi_{Y|XZ}(\cdot|x^{\prime},z)$, and call the observed value
$y^{\prime}$.

  3. 3.

Draw $Z_{n+1}\sim\Pi_{Z|XY}(\cdot|x^{\prime},y^{\prime})$.

Now suppose that we have the ability to draw from the distribution
$\Pi_{X|Z}(\mathrm{d}x|z)$. This leads to a sequential method of making draws
from $\Pi_{XY|Z}(\mathrm{d}x,\mathrm{d}y|z)$. Indeed, we first draw from
$\Pi_{X|Z}(\mathrm{d}x|z)$, and then from $\Pi_{Y|XZ}(\mathrm{d}y|x,z)$.
Hence, we can consider an alternative algorithm, the so-called block Gibbs
sampler, in which $X$ and $Y$ are sampled jointly given $Z$. It is well
established that sampling a set of variables jointly in this way often leads
to a more efficient algorithm. Denote the block Gibbs Markov chain by
$\tilde{\Gamma}=\\{\big{(}(\tilde{X}_{n},\tilde{Y}_{n}),\tilde{Z}_{n}\big{)}\\}_{n=0}^{\infty}$.
If the current state is
$\big{(}(\tilde{X}_{n},\tilde{Y}_{n}),\tilde{Z}_{n}\big{)}=((x,y),z)$, then we
move to the next state
$\big{(}(\tilde{X}_{n+1},\tilde{Y}_{n+1}),\tilde{Z}_{n+1}\big{)}$ using the
following three step procedure.

Iteration $n+1$ of the block Gibbs sampler:

  1. 1.

Draw $\tilde{X}_{n+1}\sim\Pi_{X|Z}(\cdot|z)$, and call the observed value
$x^{\prime}$.

  2. 2.

Draw $\tilde{Y}_{n+1}\sim\Pi_{Y|XZ}(\cdot|x^{\prime},z)$, and call the
observed value $y^{\prime}$.

  3. 3.

Draw $\tilde{Z}_{n+1}\sim\Pi_{Z|XY}(\cdot|x^{\prime},y^{\prime})$.

The target distribution, $\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$, is the
invariant probability distribution for both $\Gamma$ and $\tilde{\Gamma}$.
(The Markov chains considered in this section are assumed to satisfy standard
regularity conditions - spelled out in Section 2 \- that imply, among other
things, a unique invariant distribution.) Therefore, the Gibbs sampler and the
block Gibbs sampler are both valid Markov chain Monte Carlo (MCMC) algorithms
for exploring $\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$. There is, however, a
very important difference between these two algorithms regarding the ordering
of the steps. The three steps of the regular Gibbs sampler are interchangeable
in the sense that they can be reordered without affecting the validity of the
algorithm. In other words, instead of using the order $X\rightarrow
Y\rightarrow Z$, any of the six possible orderings could be used, and all will
result in a Markov chain with invariant distribution
$\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$. This is not the case, however,
with the block Gibbs sampler. Indeed, the first two steps of the block Gibbs
sampler must be done in order because the same value of $Z$ must be
conditioned on in both. So, we could actually move the third step to the top,
and still have a valid algorithm, but any other change in the order of the
steps will invalidate the algorithm. To be more specific, let
$\Gamma^{*}=\\{(Y^{*}_{n},Z^{*}_{n},X^{*}_{n})\\}_{n=0}^{\infty}$ denote the
Markov chain associated with what we call the “out-of-order” block Gibbs
sampler. If the current state is $(Y^{*}_{n},Z^{*}_{n},X^{*}_{n})=(y,z,x)$,
then we move to the next state $(Y^{*}_{n+1},Z^{*}_{n+1},X^{*}_{n+1})$ using
the following three step procedure.

Iteration $n+1$ of the out-of-order block Gibbs sampler:

  1. 1.

Draw $Y^{*}_{n+1}\sim\Pi_{Y|XZ}(\cdot|x,z)$, and call the observed value
$y^{\ast}$.

  2. 2.

Draw $Z^{*}_{n+1}\sim\Pi_{Z|XY}(\cdot|x,y^{\ast})$, and call the observed
value $z^{\ast}$.

  3. 3.

Draw $X^{*}_{n+1}\sim\Pi_{X|Z}(\cdot|z^{\ast})$.

At first glance, this reordering may seem perfectly harmless, but, in reality,
it invalidates the algorithm. Indeed, $\Gamma^{*}$ does not have the correct
invariant distribution. Again, the reason is that the two steps in the block
Gibbs sampler that together yield a draw from
$\Pi_{XY|Z}(\mathrm{d}x,\mathrm{d}y|z)$ have been separated, so we are no
longer simulating from $\Pi_{XY|Z}(\mathrm{d}x,\mathrm{d}y|z)$. To see that
the invariant distribution has changed, first note that the Markov transition
kernel (Mtk) of $\Gamma^{*}$ is given by

$K^{\ast}\big{(}(y,z,x),(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})\big{)}=\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\,\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x,y^{\prime})\,\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)\;.$

######  Remark 1.

Note that
$K^{\ast}\big{(}(y,z,x),(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})\big{)}$
does not actually depend on $y$. In the sequel, we drop such variables from
the notation when it’s convenient.

Now defining
$\Pi^{\ast}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)=\Pi_{X|Z}(\mathrm{d}x|z)\Pi_{YZ}(\mathrm{d}y,\mathrm{d}z)$,
we have

$\displaystyle\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}K^{\ast}\big{(}(y,z,x),(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})\big{)}\,\Pi^{*}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$
$\displaystyle=$
$\displaystyle\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x,y^{\prime})\,\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)\,\Pi_{X|Z}(\mathrm{d}x|z)\,\Pi_{YZ}(\mathrm{d}y,\mathrm{d}z)$
$\displaystyle=$
$\displaystyle\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\int_{\mathsf{X}}\int_{\mathsf{Z}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x,y^{\prime})\,\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)\,\Pi_{XZ}(\mathrm{d}x,\mathrm{d}z)$
$\displaystyle=$
$\displaystyle\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\int_{\mathsf{X}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x,y^{\prime})\,\Pi_{XY}(\mathrm{d}x,\mathrm{d}y^{\prime})$
$\displaystyle=$
$\displaystyle\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\,\Pi_{YZ}(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime})$
$\displaystyle=$
$\displaystyle\Pi^{*}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime},\mathrm{d}z^{\prime})\;.$

Hence, the invariant distribution of $\Gamma^{*}$ is
$\Pi^{*}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$, not the target distribution
$\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$. A little thought reveals that
basing an MCMC algorithm on $\Gamma^{*}$ is effectively the same as simulating
the correct chain,
$\tilde{\Gamma}=\\{\big{(}(\tilde{X}_{n},\tilde{Y}_{n}),\tilde{Z}_{n}\big{)}\\}_{n=0}^{\infty}$,
but then basing inferences on the shifted version
$\\{(\tilde{Y}_{n},\tilde{Z}_{n},\tilde{X}_{n+1})\\}_{n=0}^{\infty}$. Since
$\Pi$ and $\Pi^{*}$ share many of the same marginal and conditional
distributions, some (MCMC) estimators based on $\Gamma^{*}$ will be valid, but
others will not. For example, since (in general)
$\Pi^{*}_{XY}(\mathrm{d}x,\mathrm{d}y)=\int_{{\mathsf{Z}}}\Pi_{X|Z}(\mathrm{d}x|z)\Pi_{YZ}(\mathrm{d}y,\mathrm{d}z)\neq\Pi_{XY}(\mathrm{d}x,\mathrm{d}y)$,
the $\Gamma^{*}$-based estimator of the expectation of $g(X,Y)$ with respect
to $\Pi$, that is, $n^{-1}\sum_{i=0}^{n-1}g(X_{i}^{*},Y_{i}^{*})$, will be
inconsistent (assuming that $g(X,Y)$ actually depends on both $X$ and $Y$).

We now explain how our work on the out-of-order block Gibbs sampler was
motivated by an analysis in Yang and Rosenthal (2019). Consider the following
simple random effects model:

$y_{i}=\theta_{i}+e_{i}\,,$ (1)

for $i=1,\dots,m$, where the components of
${\boldsymbol{\theta}}=(\theta_{1},\dots,\theta_{m})^{T}$ are iid
$\mbox{N}(\mu,A)$, the components of $\boldsymbol{e}=(e_{1},\dots,e_{m})^{T}$
are iid $\mbox{N}(0,V)$, and ${\boldsymbol{\theta}}$ and $\boldsymbol{e}$ are
independent. The error variance, $V$, is assumed known. The basic idea is that
we will observe the $y_{i}$s, and then attempt to make inferences about the
unknown parameters, $A$ and $\mu$. Consider a Bayesian statistical model in
which $A$ and $\mu$ are taken to be a priori independent with

$\pi(\mu)\propto 1\;\;\;\mbox{and}\;\;\;A\sim\mbox{IG}(a,b)\;,$ (2)

where $a,b>0$, and we say $W\sim\mbox{IG}(a,b)$ if its density is proportional
to $w^{-a-1}e^{-b/w}I_{(0,\infty)}(w)$. Denote the resulting posterior
distribution as
$\Pi(\mathrm{d}A,\mathrm{d}\mu,\mathrm{d}{\boldsymbol{\theta}}\,|\,{\boldsymbol{y}})$,
where ${\boldsymbol{y}}=(y_{1},\dots,y_{m})^{T}$ represents the observed data.

Rosenthal (1996) derived and analyzed a block Gibbs sampler for
$\Pi(\mathrm{d}A,\mathrm{d}\mu,\mathrm{d}{\boldsymbol{\theta}}\,|\,{\boldsymbol{y}})$.
In terms of the general block Gibbs sampler described above, $(A,\mu)$ plays
the role of $(X,Y)$, and ${\boldsymbol{\theta}}$ plays the role of $Z$. So
${\mathsf{X}}=(0,\infty)$, ${\mathsf{Y}}=\mathbb{R}$ and
${\mathsf{Z}}=\mathbb{R}^{m}$. Denote the Markov chain by
$\tilde{\Lambda}=\\{\big{(}(A_{n},\mu_{n}),{\boldsymbol{\theta}}_{n}\big{)}\\}_{n=0}^{\infty}$.
If the current state is
$\big{(}(A_{n},\mu_{n}),{\boldsymbol{\theta}}_{n}\big{)}=\big{(}(A,\mu),{\boldsymbol{\theta}}\big{)}$,
then we move to the next state
$\big{(}(A_{n+1},\mu_{n+1}),{\boldsymbol{\theta}}_{n+1}\big{)}$ using the
following three step procedure.

Iteration $n+1$ of Rosenthal’s block Gibbs sampler:

  1. 1.

Draw
$A_{n+1}\sim\mbox{IG}\Big{(}a+\frac{m-1}{2},b+\frac{1}{2}\sum_{i=1}^{m}(\theta_{i}-\bar{\theta})^{2}\Big{)}$.

  2. 2.

Draw $\mu_{n+1}\sim\mbox{N}\Big{(}\bar{\theta},\frac{A_{n+1}}{m}\Big{)}$.

  3. 3.

For $i=1,2,\dots,m$, draw the $i$th component of ${\boldsymbol{\theta}}_{n+1}$
from
$\mbox{N}\Big{(}\frac{V\mu_{n+1}+A_{n+1}y_{i}}{A_{n+1}+V},\frac{A_{n+1}V}{A_{n+1}+V}\Big{)}$.

The first two steps of this algorithm constitute a joint draw from the
distribution of $(A,\mu)$ given $({\boldsymbol{\theta}},{\boldsymbol{y}})$,
which we write as
$\Pi_{1}(\mathrm{d}A,\mathrm{d}\mu\,|\,{\boldsymbol{\theta}},{\boldsymbol{y}})$.
In particular, if we factor $\Pi_{1}$ as follows

$\Pi_{1}(\mathrm{d}A,\mathrm{d}\mu\,|\,{\boldsymbol{\theta}},{\boldsymbol{y}})=\Pi_{21}(\mathrm{d}A\,|\,{\boldsymbol{\theta}},{\boldsymbol{y}})\Pi_{22}(\mathrm{d}\mu\,|\,A,{\boldsymbol{\theta}},{\boldsymbol{y}})\;,$

then in the first step we draw
$A_{n+1}\sim\Pi_{21}(\cdot\,|\,{\boldsymbol{\theta}},{\boldsymbol{y}})$, and
in the second step we draw
$\mu_{n+1}\sim\Pi_{22}(\cdot\,|\,A_{n+1},{\boldsymbol{\theta}},{\boldsymbol{y}})$.
In the posterior distribution, the components of ${\boldsymbol{\theta}}$ are
conditionally independent given $(\mu,A,{\boldsymbol{y}})$, which is why the
third step of the algorithm consists of $m$ univariate draws.

Recently, Yang and Rosenthal (2019) set out to perform a more nuanced analysis
of Rosenthal’s (1996) block Gibbs sampler, but ended up analyzing the out-of-
order version of Rosenthal’s (1996) algorithm instead. Let
$\Lambda^{*}=\\{(\mu^{*}_{n},{\boldsymbol{\theta}}^{*}_{n},A^{*}_{n})\\}_{n=0}^{\infty}$
denote their Markov chain. If the current state is
$(\mu^{*}_{n},{\boldsymbol{\theta}}^{*}_{n},A^{*}_{n})=(\mu,{\boldsymbol{\theta}},A)$,
then we move to the next state
$(\mu^{*}_{n+1},{\boldsymbol{\theta}}^{*}_{n+1},A^{*}_{n+1})$ using the
following three step procedure.

Iteration $n+1$ of Yang & Rosenthal’s algorithm:

  1. 1.

Draw $\mu^{*}_{n+1}\sim\mbox{N}\big{(}\bar{\theta},\frac{A}{m}\big{)}$.

  2. 2.

For $i=1,2,\dots,m$, draw the $i$th component of
${\boldsymbol{\theta}}^{*}_{n+1}$ from
$\mbox{N}\Big{(}\frac{V\mu^{*}_{n+1}+Ay_{i}}{A+V},\frac{AV}{A+V}\Big{)}$.

  3. 3.

Draw
$A^{*}_{n+1}\sim\mbox{IG}\Big{(}a+\frac{m-1}{2},b+\frac{1}{2}\sum_{i=1}^{m}(\theta^{*}_{n+1,i}-\bar{\theta}_{n+1}^{*})^{2}\Big{)}$.

It appears that Yang and Rosenthal (2019) changed the order of the steps in
Rosenthal’s (1996) block Gibbs sampler because the resulting Markov chain was
easier to analyze. However, they were apparently unaware that the modified
algorithm they analyzed is not a valid MCMC algorithm for the target posterior
distribution
$\Pi(\mathrm{d}A,\mathrm{d}\mu,\mathrm{d}{\boldsymbol{\theta}}\,|\,{\boldsymbol{y}})$.
Thus, without supplementary results relating $\tilde{\Lambda}$ and
$\Lambda^{*}$, the convergence results developed by Yang and Rosenthal (2019)
are not entirely germane to the exploration of
$\Pi(\mathrm{d}A,\mathrm{d}\mu,\mathrm{d}{\boldsymbol{\theta}}\,|\,{\boldsymbol{y}})$.

In this note, we develop general results relating the convergence behaviors of
the (valid) block Gibbs Markov chain, $\tilde{\Gamma}$, and the (invalid) out-
of-order block Gibbs Markov chain, $\Gamma^{*}$. In particular, we develop
inequalities that relate the total variation distance to stationarity for one
Markov chain to that of the other, and these bounds imply that the two chains
mix at essentially the same rate. (Keep in mind that these two Markov chains
have different invariant distributions.) We also show that $\tilde{\Gamma}$ is
geometrically ergodic if and only if $\Gamma^{*}$ is geometrically ergodic,
and that their convergence rates are the same. Our results demonstrate that
one can perform convergence analysis of the block Gibbs sampler indirectly by
analyzing the out-of-order block Gibbs sampler, which may be easier to handle,
as was apparently the case for Yang and Rosenthal (2019).

##  2 Main Results

We begin with some general state space Markov chain theory. Let $E$ be a set,
and let ${\cal E}$ be a countably generated $\sigma$-algebra of subsets of
$E$. Let $P:E\times{\cal E}\rightarrow[0,1]$ be a Mtk, and assume that the
corresponding Markov chain is irreducible, aperiodic and positive Harris
recurrent. (See Meyn and Tweedie (2009) for definitions.) Let $\Pi$ denote the
unique invariant probability measure, and let $P^{n}$ denote the $n$-step Mtk
(so, as usual, $P\equiv P^{1}$). If $\mu$ is a probability measure on $E$,
then we use $\mu P^{n}(\cdot)$ to denote the probability measure
$\int_{E}P^{n}(u,\cdot)\mu(du)$. Following Nummelin (1984) and Tierney (1994),
we say that the Markov chain is geometrically ergodic if there exist a non-
negative extended real-valued function $M$ with $\int_{E}M(u)\,\Pi(du)<\infty$
and a $\rho\in[0,1)$ such that

$\lVert P^{n}(u,\cdot)-\Pi(\cdot)\rVert\leq M(u)\rho^{n}$ (3)

for all $n\in\mathbb{N}$ and all $u\in E$. Here, $\lVert\cdot\rVert$ denotes
the usual total variation norm for signed measures. We define the geometric
convergence rate of the chain, $\rho_{*}$, to be the infimum over
$\rho\in[0,1]$ such that (3) holds for some non-negative extended real-valued
function $M$, integrable with respect to $\Pi$. Clearly, the chain is
geometrically ergodic if and only if $\rho_{*}<1$.

######  Remark 2.

This definition of geometric ergodicity is slightly less standard than an
alternative definition in which $M$ is not assumed to be integrable with
respect to $\Pi$, but is assumed to be finite $\Pi$-almost everywhere. While
Roberts and Rosenthal’s (1997) Proposition 2.1 shows that the two definitions
are actually equivalent, the geometric convergence rates under the two
definitions are not necessarily equal.

A standard result concerning total variation distance is as follows (see,
e.g., Roberts and Rosenthal, 2004, Proposition 3). If $\mu$ and $\nu$ are
probability measures on $E$, then

$\lVert\mu(\cdot)-\nu(\cdot)\rVert=\sup_{f:E\rightarrow[0,1]}\bigg{|}\int
fd\mu-\int fd\nu\bigg{|}\;.$

This fact will be used repeatedly in our proofs.

Now let $K$ denote the Mtk of the block Gibbs Markov chain,
$\tilde{\Gamma}=\\{\big{(}(\tilde{X}_{n},\tilde{Y}_{n}),\tilde{Z}_{n}\big{)}\\}_{n=0}^{\infty}$,
described in the Introduction. So we have

$K\big{(}(x,y,z),(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime},\mathrm{d}z^{\prime})\big{)}=\Pi_{Z|XY}(\mathrm{d}z^{\prime}\,|\,x^{\prime},y^{\prime})\,\Pi_{XY|Z}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime}\,|\,z)\;.$

(We assume that all Markov chains considered in this section satisfy the basic
regularity conditions laid out at the start of this section.) It is well known
that the sequences $\\{(\tilde{X}_{n},\tilde{Y}_{n})\\}_{n=0}^{\infty}$ and
$\\{\tilde{Z}_{n}\\}_{n=0}^{\infty}$ are themselves (reversible) Markov chains
with invariant distributions given by $\Pi_{XY}(\mathrm{d}x,\mathrm{d}y)$ and
$\Pi_{Z}(\mathrm{d}z)$, respectively (see, e.g., Liu et al. (1994)). Let
$K_{XY}$ denote the Mtk of the $(X,Y)$-marginal chain, and define $K_{Z}$
similarly. For example,

$K_{XY}\big{(}(x,y),(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime})\big{)}=\int_{{\mathsf{Z}}}\Pi_{XY|Z}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime}\,|\,z)\,\Pi_{Z|XY}(\mathrm{d}z\,|\,x,y)\;.$

As mentioned in the Introduction, there is one way to reorder the steps in the
block Gibbs sampler without invalidating the algorithm. The corresponding
Markov chain has Mtk given by

$K^{\dagger}\big{(}(z,x,y),(\mathrm{d}z^{\prime},\mathrm{d}x^{\prime},\mathrm{d}y^{\prime})\big{)}=\Pi_{XY|Z}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime}\,|\,z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}\,|\,x,y)\;.$

All four of these Markov chains ($K$, $K^{\dagger}$, $K_{XY}$ and $K_{Z}$)
converge at the same rate (Roberts and Rosenthal, 2001; Diaconis et al.,
2008). As in the Introduction, let $K^{*}$ denote the Mtk of the out-of-order
chain, so, again,

$K^{*}\big{(}(y,z,x),(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})\big{)}=\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\,\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x,y^{\prime})\,\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)\;.$

Here is our first result.

######  Proposition 3.

Fix $z\in{\mathsf{Z}}$ and let $\nu_{z}$ denote the probability measure of the
random vector $(X,Z)$ such that $Z=z$ w.p. 1, and the conditional distribution
of $X$ given $Z$ is $\Pi_{X|Z}(\cdot|z)$. Then

$\lVert K^{n}\big{(}(x,y,z),\cdot\big{)}-\Pi(\cdot)\rVert\leq\lVert
K_{Z}^{n-1}(z,\cdot)-\Pi_{Z}(\cdot)\rVert\leq\lVert\nu_{z}K^{*(n-2)}(\cdot)-\Pi^{\ast}(\cdot)\rVert\;.$
(4)

Fix $(x,z)\in{\mathsf{X}}\times{\mathsf{Z}}$ and let $\nu_{(x,z)}$ denote the
probability measure of the random vector $(X,Y)$ such that $X=x$ w.p. 1, and
the conditional distribution of $Y$ given $X$ is $\Pi_{Y|XZ}(\cdot|x,z)$. Then

$\lVert
K^{*n}\big{(}(y,z,x),\cdot)-\Pi^{*}(\cdot)\rVert\leq\lVert\nu_{(x,z)}K_{XY}^{n-1}(\cdot)-\Pi_{XY}(\cdot)\rVert\leq\lVert\nu_{(x,z)}K^{\dagger(n-1)}(\cdot)-\Pi(\cdot)\rVert\;.$
(5)

###### Proof.

We begin with (4). The first inequality follows immediately from Lemma 2.4 of
Diaconis et al. (2008). Now, it is straightforward to show that

$\displaystyle K^{n}_{Z}(z,\mathrm{d}z^{\prime})$ $\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})K^{*(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\int_{{\mathsf{X}}}K^{*(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\nu_{z}K^{*(n-1)}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\;.$
(6)

Also,

$\displaystyle\Pi_{Z}(\mathrm{d}z^{\prime})$
$\displaystyle=\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}\int_{\mathsf{Y}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi_{YZ}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime\prime})$
$\displaystyle=\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}\int_{\mathsf{Y}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\;.$

Hence for the second inequality in (4),

$\displaystyle\big{\lVert}K^{n}_{Z}(z,\cdot)-\Pi_{Z}(\cdot)\big{\rVert}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{Z}}}f(z^{\prime})\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\nu_{z}K^{*(n-1)}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{Z}}}f(z^{\prime})\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\bigg{]}\nu_{z}K^{*(n-1)}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\bigg{]}\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\bigg{]}$
$\displaystyle\hskip
199.16928pt\bigg{[}\nu_{z}K^{*(n-1)}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})-\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{]}\bigg{|}$
$\displaystyle\leq$ $\displaystyle\sup_{0\leq g\leq
1}\bigg{|}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}g(x^{\prime},y^{\prime\prime},z^{\prime\prime})\bigg{[}\nu_{z}K^{*(n-1)}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})-\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{]}\bigg{|}$
$\displaystyle=$
$\displaystyle\big{\lVert}\nu_{z}K^{*(n-1)}(\cdot)-\Pi^{\ast}(\cdot)\big{\rVert}\;.$

Now for (5). It is straightforward to show that

$\displaystyle
K^{*n}\big{(}(y,z,x),(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})\big{)}$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})K_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)$
(7) $\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{[}\int_{{\mathsf{Y}}}K_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\bigg{]}$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\nu_{(x,z)}K_{XY}^{n-1}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\;.$

Also,

$\Pi^{*}(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})=\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{YZ}(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime})=\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\;.$

Hence for the first inequality of (5),

$\displaystyle\big{\lVert}K^{\ast
n}\big{(}(y,z,x),\cdot\big{)}-\Pi^{\ast}(\cdot)\big{\rVert}$ $\displaystyle=$
$\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(x^{\prime},y^{\prime},z^{\prime})\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\nu_{(x,z)}K_{XY}^{n-1}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(x^{\prime},y^{\prime},z^{\prime})\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}f(x^{\prime},y^{\prime},z^{\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{]}\nu_{(x,z)}K_{XY}^{n-1}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}f(x^{\prime},y^{\prime},z^{\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{]}\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}f(x^{\prime},y^{\prime},z^{\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{]}$
$\displaystyle\hskip
184.9429pt\bigg{[}\nu_{(x,z)}K_{XY}^{n-1}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})-\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{]}\bigg{|}$
$\displaystyle\leq$ $\displaystyle\sup_{0\leq g\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}g(x^{\prime\prime},y^{\prime})\bigg{[}\nu_{(x,z)}K_{XY}^{n-1}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})-\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{]}\bigg{|}$
$\displaystyle=$
$\displaystyle\big{\lVert}\nu_{(x,z)}K_{XY}^{n-1}(\cdot)-\Pi_{XY}(\cdot)\big{\rVert}\;,$

The second inequality follows from the fact that

$\nu_{(x,z)}K_{XY}^{n}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime})=\int_{{\mathsf{Z}}}\nu_{(x,z)}K^{\dagger
n}\big{(}\mathrm{d}z^{\prime},(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime})\big{)}\;.$

∎

In light of Proposition 3, it should not be surprising that the block Gibbs
Markov chain is geometrically ergodic if and only if the out-of-order block
Gibbs Markov chain is geometrically ergodic, and that they have the same rate
of convergence. This is the subject of our next result.

######  Proposition 4.

There are only two possibilities: (i) $\tilde{\Gamma}$ and $\Gamma^{*}$ are
both geometrically ergodic with the same geometric convergence rate, or (ii)
neither chain is geometrically ergodic.

###### Proof.

First, assume that $\Gamma^{*}$ is geometrically ergodic. That is, for all
$n\in\mathbb{N}$ and all
$(y,z,x)\in{\mathsf{Y}}\times{\mathsf{Z}}\times{\mathsf{X}}$,

$\big{\lVert}K^{*n}((y,z,x),\cdot)-\Pi^{*}(\cdot)\big{\rVert}\leq
M_{1}(x,z)\rho_{1}^{n}$

where $\rho_{1}\in[0,1)$ and
$\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}M_{1}(x,z)\Pi^{*}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)<\infty$.
We now show that this implies the geometric ergodicity of the $Z$-marginal.
It’s easy to see that

$\displaystyle\Pi_{Z}(\mathrm{d}z^{\prime})$ $\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi_{YZ}(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi^{\ast}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)\;.$

Combining this with (2), we have

$\displaystyle\big{\lVert}K^{n}_{Z}(z,\cdot)-\Pi_{Z}(\cdot)\big{\rVert}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{Z}}}f(z^{\prime})\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})$
$\displaystyle\hskip
170.71652ptK^{\ast(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{Z}}}f(z^{\prime})\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\int_{{\mathsf{Y}}}\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\Pi^{*}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\bigg{[}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\bigg{]}$
$\displaystyle\hskip
170.71652ptK^{\ast(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}\bigg{[}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime},y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x^{\prime},z^{\prime\prime})\bigg{]}\Pi^{*}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)\bigg{|}$
$\displaystyle\leq$ $\displaystyle\sup_{0\leq g\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}g(x^{\prime},y^{\prime\prime},z^{\prime\prime})$
$\displaystyle\hskip
85.35826pt\bigg{[}K^{\ast(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}-\Pi^{*}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{]}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)\bigg{|}$
$\displaystyle\leq$ $\displaystyle\int_{{\mathsf{X}}}\bigg{\\{}\sup_{0\leq
g\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}g(x^{\prime},y^{\prime\prime},z^{\prime\prime})$
$\displaystyle\hskip
85.35826pt\bigg{[}K^{\ast(n-1)}\big{(}(x^{\prime\prime},z),(\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime},\mathrm{d}x^{\prime})\big{)}-\Pi^{*}(\mathrm{d}x^{\prime},\mathrm{d}y^{\prime\prime},\mathrm{d}z^{\prime\prime})\bigg{]}\bigg{|}\bigg{\\}}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{X}}}\big{\lVert}K^{\ast(n-1)}\big{(}(x^{\prime\prime},z),\cdot\big{)}-\Pi^{\ast}(\cdot)\big{\rVert}\Pi_{X|Z}(\mathrm{d}x^{\prime\prime}|z)\;.$

Now using the assumed geometric ergodicity of $K^{*}$, we have

$\big{\lVert}K_{Z}^{n}(z,\cdot)-\Pi_{Z}(\cdot)\big{\rVert}\leq\rho_{1}^{n-1}\int_{{\mathsf{X}}}M_{1}(x,z)\Pi_{X|Z}(\mathrm{d}x|z)=\frac{M^{\prime}_{1}(z)}{\rho_{1}}\rho_{1}^{n}\;,$

where we have defined
$M^{\prime}_{1}(z):=\int_{{\mathsf{X}}}M_{1}(x,z)\,\Pi_{X|Z}(\mathrm{d}x|z)$.
Now using the integrability of $M_{1}(x,z)$ with respect to
$\Pi^{*}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$, we have

$\displaystyle\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}M_{1}(x,z)\,\Pi^{*}(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$
$\displaystyle=\int_{{\mathsf{X}}}\int_{{\mathsf{Z}}}M_{1}(x,z)\,\Pi_{XZ}(\mathrm{d}x,\mathrm{d}z)$
$\displaystyle=\int_{{\mathsf{Z}}}\bigg{[}\int_{{\mathsf{X}}}M_{1}(x,z)\,\Pi_{X|Z}(\mathrm{d}x|z)\bigg{]}\Pi_{Z}(\mathrm{d}z)$
$\displaystyle=\int_{{\mathsf{Z}}}M^{\prime}_{1}(z)\,\Pi_{Z}(\mathrm{d}z)$
$\displaystyle<\infty\;.$

It follows immediately that the $Z$-marginal chain is geometrically ergodic,
and that its geometric rate of convergence is no larger than $\rho_{1}$.
Again, the $Z$-marginal chain and the block Gibbs chain share the same
geometric rate of convergence.

Now assume that the block Gibbs sampler is geometrically ergodic. This implies
that the $(X,Y)$-marginal chain is also geometrically ergodic with the same
rate, so, for all $n\in\mathbb{N}$ and all
$(x,y)\in{\mathsf{X}}\times{\mathsf{Y}}$,

$\big{\lVert}K_{XY}^{n}\big{(}(x,y),\cdot)-\Pi_{XY}(\cdot)\big{\rVert}\leq
M_{2}(x,y)\rho_{2}^{n}$

where $\rho_{2}\in[0,1)$ and
$\int_{\mathsf{X}}\int_{\mathsf{Y}}M_{2}(x,y)\Pi(\mathrm{d}x,\mathrm{d}y)<\infty$.
It’s easy to see that

$\displaystyle\Pi^{*}(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime},\mathrm{d}x^{\prime})$
$\displaystyle=\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{YZ}(\mathrm{d}y^{\prime},\mathrm{d}z^{\prime})$
$\displaystyle=\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\;.$

Combining this with (7), we have

$\displaystyle\big{\lVert}K^{*n}\big{(}(y,z,x),\cdot\big{)}-\Pi^{*}(\cdot)\big{\rVert}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(x^{\prime},y^{\prime},z^{\prime})\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})$
$\displaystyle\hskip
184.9429ptK_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\int_{{\mathsf{Z}}}f(x^{\prime},y^{\prime},z^{\prime})\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\bigg{|}$
$\displaystyle=$ $\displaystyle\sup_{0\leq f\leq
1}\bigg{|}\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}f(x^{\prime},y^{\prime},z^{\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{]}$
$\displaystyle\hskip
184.9429ptK_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)$
$\displaystyle\hskip
28.45274pt-\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}\bigg{[}\int_{{\mathsf{Z}}}\int_{{\mathsf{X}}}f(x^{\prime},y^{\prime},z^{\prime})\Pi_{X|Z}(\mathrm{d}x^{\prime}|z^{\prime})\Pi_{Z|XY}(\mathrm{d}z^{\prime}|x^{\prime\prime},y^{\prime})\bigg{]}\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\bigg{|}$
$\displaystyle\leq$ $\displaystyle\sup_{0\leq g\leq
1}\bigg{|}\int_{{\mathsf{Y}}}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}g(x^{\prime\prime},y^{\prime})\bigg{[}K_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}-\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{]}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\bigg{|}$
$\displaystyle\leq$ $\displaystyle\int_{{\mathsf{Y}}}\bigg{\\{}\sup_{0\leq
g\leq
1}\bigg{|}\int_{{\mathsf{X}}}\int_{{\mathsf{Y}}}g(x^{\prime\prime},y^{\prime})\bigg{[}K_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\big{)}-\Pi_{XY}(\mathrm{d}x^{\prime\prime},\mathrm{d}y^{\prime})\bigg{]}\bigg{|}\bigg{\\}}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)$
$\displaystyle=$
$\displaystyle\int_{{\mathsf{Y}}}\big{\lVert}K_{XY}^{n-1}\big{(}(x,y^{\prime\prime}),\cdot\big{)}-\Pi_{XY}(\cdot)\big{\rVert}\Pi_{Y|XZ}(\mathrm{d}y^{\prime\prime}|x,z)\;.$

Now using the assumed geometric ergodicity of $K_{XY}$, we have

$\big{\lVert}K^{*n}\big{(}(y,z,x),\cdot)-\Pi^{*}(\cdot)\big{\rVert}\leq\rho_{2}^{n-1}\int_{{\mathsf{Y}}}M_{2}(x,y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)=\frac{M^{\prime}_{2}(x,z)}{\rho_{2}}\rho_{2}^{n}\;,$

where we have defined
$M^{\prime}_{2}(x,z):=\int_{\mathsf{Y}}M_{2}(x,y^{\prime})\Pi_{Y|XZ}(\mathrm{d}y^{\prime}|x,z)$.
Using the integrability of $M_{2}(x,y)$ with respect to
$\Pi_{XY}(\mathrm{d}x,\mathrm{d}y)$, we have

$\displaystyle\int_{\mathsf{X}}\int_{\mathsf{Y}}M_{2}(x,y)\,\Pi_{XY}(\mathrm{d}x,\mathrm{d}y)$
$\displaystyle=\int_{\mathsf{X}}\int_{\mathsf{Y}}\int_{\mathsf{Z}}M_{2}(x,y)\,\Pi(\mathrm{d}x,\mathrm{d}y,\mathrm{d}z)$
$\displaystyle=\int_{\mathsf{X}}\int_{\mathsf{Z}}\bigg{[}\int_{\mathsf{Y}}M_{2}(x,y)\,\Pi_{Y|XZ}(\mathrm{d}y|x,z)\bigg{]}\Pi_{XZ}(\mathrm{d}x,\mathrm{d}z)$
$\displaystyle=\int_{\mathsf{X}}\int_{\mathsf{Z}}M^{\prime}_{2}(x,z)\,\Pi_{XZ}(\mathrm{d}x,\mathrm{d}z)$
$\displaystyle<\infty\;.$

It follows immediately that the out-of-order chain is geometrically ergodic,
and that its geometric rate of convergence is no larger than $\rho_{2}$.

∎

Acknowledgment. The authors are grateful to Qian Qin for helpful
conversations.

## References

  * Diaconis et al. [2008] Persi Diaconis, Kshitij Khare, and Laurent Saloff-Coste.  Gibbs sampling, exponential families and orthogonal polynomials (with discussion).  _Statistical Science_ , 23:151–200, 2008.
  * Liu et al. [1994] J. S. Liu, W. H. Wong, and A. Kong.  Covariance structure of the Gibbs sampler with applications to comparisons of estimators and augmentation schemes.  _Biometrika_ , 81:27–40, 1994.
  * Meyn and Tweedie [2009] Sean P. Meyn and Richard L. Tweedie.  _Markov Chains and Stochastic Stability_.  Cambridge University Press, Cambridge, U.K., 2 edition, 2009.
  * Nummelin [1984] Esa Nummelin.  _General Irreducible Markov Chains and Non-negative Operators_.  Cambridge, London, 1984.
  * Roberts and Rosenthal [1997] Gareth O. Roberts and Jeffrey S. Rosenthal.  Geometric ergodicity and hybrid Markov chains.  _Electronic Communications in Probability_ , 2:13–25, 1997\.
  * Roberts and Rosenthal [2001] Gareth O. Roberts and Jeffrey S. Rosenthal.  Markov chains and de-initializing processes.  _Scandinavian Journal of Statistics_ , 28:489–504, 2001\.
  * Roberts and Rosenthal [2004] Gareth O. Roberts and Jeffrey S. Rosenthal.  General state space Markov chains and MCMC algorithms.  _Probability Surveys_ , pages 20–71, 2004.
  * Rosenthal [1996] Jeffrey S. Rosenthal.  Analysis of the Gibbs sampler for a model related to James-Stein estimators.  _Statistics and Computing_ , 6:269–275, 1996.
  * Tierney [1994] Luke Tierney.  Markov chains for exploring posterior distributions (with discussion).  _Annals of Statistics_ , 22:1701–1728, 1994.
  * Yang and Rosenthal [2019] Jun Yang and Jeffrey S. Rosenthal.  Complexity results for MCMC derived from quantitative bounds.  _arXiv:1708.00829_ , 2019.