∎

11institutetext: Guanyang Wang 22institutetext: 501 Hill Center 110
Frelinghuysen Road Piscataway, NJ 08854
Tel.: +1-6504228730
22email<EMAIL_ADDRESS>
# Exact Convergence Rate Analysis of the Independent Metropolis-Hastings
Algorithms

Guanyang Wang

(Received: date / Accepted: date)

###### Abstract

A well-known difficult problem regarding Metropolis-Hastings algorithms is to
get sharp bounds on their convergence rates. Moreover, different
initializations may have different convergence rates so a uniform upper bound
may be too conservative to be used in practice. In this paper, we study the
convergence properties of the Independent Metropolis-Hastings (IMH) algorithms
on both general and discrete state spaces. Under mild conditions, we derive
the exact convergence rate and prove that different initializations of the IMH
algorithm have the same convergence rate. In particular, we get the exact
convergence speed for IMH algorithms on general state spaces under certain
conditions, which is the first ‘exact convergence’ result for general state
MCMC algorithms to the author’s best knowldege . Connections with the Random
Walk Metropolis-Hastings (RWMH) algorithm are also discussed, which solve the
conjecture proposed by Atchadé and Perron AP (07) using a counterexample.

###### Keywords:

Independent Metropolis-Hastings Convergence Geometrically Ergodic

## Acknowledgement

The author would like to thank Richard Smith and Persi Diaconis for helpful
discussions, and Jeffrey Rosenthal for pointing out some useful references,
and David Sichen Wu and Zhengqing Zhou for helpful suggestions in improving
this paper.

## Data Availability Statement

Data sharing not applicable to this article as no datasets were generated or
analysed during the current study. All simulation codes are available upon
request.

##  1 Introduction

Markov chain Monte Carlo methods, such as the Metropolis-Hastings algorithms
MRR+ (53) Has (70), the Gibbs sampler GG (84) GS (90), have revolutionized
statistics, especially statistical computing and Bayesian methodology. When
facing a complicated probability distribution, no matter discrete or
continuous, low or high dimensional, MCMC methods provide powerful simulation
tools to draw samples from the target distribution. The idea of learning a
system by simulating it with random sampling has been proven to be useful in
almost every quantitative subject of study. This makes MCMC methods ubiquitous
in many areas including physics, biology, chemistry, and computer science. In
particular, the Metropolis algorithm is recognized as the ‘top 10 algorithms’
in the 20th century Cip (00).

Mathematically speaking, given a target distribution $\pi(x)$, the MCMC
algorithm generates a Markov chain $\Phi\doteq\\{\Phi_{1},\Phi_{2},\cdots\\}$
whose stationary distribution is designed to be $\pi$. Under mild conditions,
classical Markov chain theory guarantees that the Markov chain $\Phi$ will
converge to its stationary distribution when the chain runs long enough.

However, the convergence result mentioned above does not give any quantitative
convergence rate analysis. Therefore, a central part of the MCMC theory is to
establish convergence rate analysis for MCMC algorithms. Unfortunately,
getting sharp bounds for the convergence rates is known to be very difficult
in Markov chain theory, especially for general state Markov chains. Consider a
Markov chain $\pi(x)$ with stationary distribution $\pi(x)$ in
$\mathbb{R}^{d}$, most of the existing theoretical works are established under
the notion of geometric ergodicity. Roughly speaking, a Markov chain with
transition probability $P$ is said to be geometrically ergodic if the
following inequality holds for $\pi$-almost everywhere $x$:

$\|P^{n}(x,\cdot)-\pi(\cdot)\|\leq C(x)r^{n},$ (1.1)

where $r$ is a constant between $0$ and $1$, $\|\cdot\|$ is some distance
metric between two probability measures, usually taken as the total variation
(TV) distance.

Formula 1.1 guarantees that, for almost all initializations, the convergence
rate of $\Phi$ can be uniformly upper bounded by a constant $r$. However, one
can ask several natural questions regarding Formula 1.1, for example:

  * •

(Q1) How to get sharp convergence rate $r$ in the right-hand side of
inequality 1.1 sharp? In practice, geometric ergodicity is often established
under the ‘drift-and-minorization’ framework. But the quantitative bound $r$
given by this framework is often very conservative and thus far from the exact
convergence rate. For example, there are some cases where sharp rates of
convergence can be derived, and the resulting bounds are usually much sharper
than those based on ‘drift-and-minorization’. We refer the interested readers
to the paper by Diaconis et al. DKSC08a , the discussion on the previous paper
by Jones and Johnson JJ (08), and the rejoinder DKSC08b  for a concrete
example.

  * •

(Q2) Does every point $x$ have the same convergence rate? From the expression
of inequality 1.1. It is tempting to believe that all the points have the same
convergence rate. However, as we will see shortly, this is not true in
general. Therefore, even if one could get a ‘sharp rate’ for 1.1, this still
only tells the ‘slowest’ convergence rate among all the initial states.
Suppose there exists a Markov chain, such that the convergence rate at one
point (say $x_{1}$) equals $0.001$, while the convergence rate at another
point (say $x_{2}$) equals $0.999$. Then the bound $r$ given by 1.1 would be
practically useless when one starts the chain at $x_{1}$. Therefore, a more
precise but perfectly natural question would be inquiring the convergence
rates $r(x)$ for different initializations.

We believe both Q1 and Q2 would be of both theorist and practitioner’s
interest. First of all, most of the present MCMC convergence theories focus on
the upper bound of the convergence speed. Thus it is natural to ask for a
sharp upper bound, or a useful lower bound. Secondly, an a priori bound for
the convergence rate would be very helpful for users to evaluate the
computation cost, or choose a fast MCMC algorithm among many candidates before
implementing them all. Lastly, it seems Q2 has not been seriously discussed
and studied before. At first glance, 1.1 seems to suggest that every point has
the same convergence rate $r$. However, it only shows every point has
convergence rate upper-bounded by $r$. The following example shows different
initializations may have significantly different convergence rates.

######  Example 1 (Markov Chain on Three Points)

Let $\Phi$ be a Markov chain on state space
$\mathcal{X}=\\{x_{1},x_{2},x_{3}\\}$ with transition matrix:

$\displaystyle P=\begin{pmatrix}1/3&1/3&1/3\\\ 1/3&2/3&0\\\ 1/3&0&2/3\\\
\end{pmatrix}$

Then it can be verified directly that the stationary distribution $\pi$ is the
uniform distribution on $\mathcal{X}$, i.e., $\pi(x_{i})=1/3$ for every $i$.
Meanwhile, since $P(x_{1},\cdot)=\pi(\cdot)$, the chain will converge after
one step when starting at $x_{1}$, i.e., $\|P^{n}(x_{1},\cdot)-\pi(\cdot)\|=0$
for any $n\geq 1$. However, the convergence rates at $x_{2}$ and $x_{3}$ are
both strictly greater than $0$, as they do not converge perfectly after any
finitely many steps. To be more precise, we can calculate
$\|P^{n}(x_{i},\cdot)-\pi(\cdot)\|_{\sf TV}$ explicitly for $i=2$ or $3$. It
turns out that

$\|P^{n}(x_{2},\cdot)-\pi(\cdot)\|_{\sf
TV}=\|P^{n}(x_{3},\cdot)-\pi(\cdot)\|_{\sf
TV}=\frac{1}{2}\bigg{(}\frac{2}{3}\bigg{)}^{n}.$

Therefore, the convergence rate at both $x_{2}$ and $x_{3}$ equals
$\frac{2}{3}$.

Admittedly, Example 1 is an artificial example just for illustration. But as
we can see in Section 5 Example 6 , even for Random-walk Metropolis-Hastings
algorithms (RWMH) on general state spaces, the same phenomenon may occur as
well. We do not know if the fact ‘different initializations have different
convergence rates’ is true in general. If so, then such insight may shed light
on practical applications as a careful selection of initialization would
greatly increase the algorithm’s efficiency. Therefore, we believe Q2 is an
interesting and meaningful question to investigate.

However, getting precise answers for Q1 and Q2 are known to be very difficult
due to the complicated nature of Markov chains. Sharp convergence rate
analysis is very rare for MCMC algorithms on general state spaces, even for
toy models. In this paper, we focus on studying the convergence of the
Independent Metropolis-Hastings (IMH) algorithm which is a widely-used special
class of MCMC methods. We show that both Q1 and Q2 can be answered precisely
for IMH chains on both discrete and general state spaces. Under mild
conditions, we could calculate the non-asymptotic convergence speed for IMH
algorithms on general state spaces exactly, with the exact convergence rate
and the exact constant. To the author’s best knowledge, this is the first
‘exact convergence analysis’ for a class of MCMC algorithms on general state
spaces, with the upper bound matches perfectly with the lower bound. We also
show that, all the initializations converge to stationary at the same rate for
IMH algorithms (though not true for general MCMC algorithms). Our work extends
the previous results of Smith and Tierney ST (96) on general state spaces and
Liu Liu (96) on discrete state spaces.

###  1.1 Our contributions

In this paper, we consider the IMH chain on general and discrete state space
separately. Our target is to answer the questions Q1 and Q2 proposed in
Section 1. Our results are summarized in Table 1, and explained below.

Table 1: Summary of our convergence results for the IMH algorithms  State Space $\mathcal{X}$ |  | (Exact) Convergence
---
Rate
| (Exact) Convergence
---
Speed
| Convergence Rate for
---
Different Initializations
Continuous |  $1-\frac{1}{w^{\star}}$ (Thm 3.2, 3.3) |  $(1-\frac{1}{w^{\star}})^{n}$ (Thm 3.2) | All equals $1-\frac{1}{w^{\star}}$ (Thm 3.4)
Discrete |  $1-\frac{1}{w^{\star}}$(Thm 4.1) |  | $[(1-\pi_{1})(1-\frac{1}{w^{\star}})^{n},(1-\frac{1}{w^{\star}})^{n}]$
---
(Thm 4.1)
All equals $1-\frac{1}{w^{\star}}$ (Thm 4.2)

In short, our results include:

  1. 1.

(Q1) Exact convergence rate analysis for the IMH algorithm:

     * •

For IMH on general state spaces, we prove that, under certain conditions, we
have the following ‘exact convergence’ result:

$\sup_{x}\|P^{n}(x,\cdot)-\pi\|_{\sf TV}=(r^{\star})^{n}$ (1.2)

where $r^{\star}=1-\frac{1}{w^{\star}}$ is a computable constant which will
soon be clear (defined in Section 3.1). It is worth mentioning that formula
1.2 gives an equality instead of an upper or lower bound, so it completely
characterizes the convergence speed for the IMH chain.

     * •

For IMH on discrete state space, we prove that:

$c(r^{\star})^{n}\leq\sup_{x}\|P^{n}(x,\cdot)-\pi\|_{\sf
TV}\leq(r^{\star})^{n},$ (1.3)

where $r^{\star}$ is the same as above, $c$ is a computable constant which
will be defined in Section 4. We also provide examples to show formula 1.3
cannot be further improved without further assumptions.

  2. 2.

(Q2) Convergence rate analysis with different initializations:

     * •

For IMH on general state spaces, we prove that, under certain conditions, for
every $x\in\mathcal{X}$, the induced probability measure $P^{n}(x,\cdot)$
converges to $\pi$ at the same rate.

     * •

For IMH on discrete state space, we prove that $P^{n}(x,\cdot)$ converges to
$\pi$ at the same rate for all $x\in\mathcal{X}$ without any further
assumptions.

  3. 3.

We discuss the similarities and differences between IMH algorithms and RWMH
algorithms. We provide examples to show that RWMH do not enjoy some of the
nice properties as IMH. In particular, we solve the conjecture proposed by
Atchadé and Perron AP (07) by means of a counterexample which is constructed
in Theorem 5.1.

Theorem 3.2 gives a simple, clean formula for the exact speed of convergence,
with lower bound matches perfectly with the upper bound under certain
conditions. Theorem 4.1 is the discrete variant of Theorem 3.2. It is
interesting that the exact result in Theorem 3.2 for general state space does
not hold anymore when the state space is discrete, though the convergence rate
is still the same. Theorem 3.4 and Theorem 4.2 are also somewhat surprising as
they show the IMH chain converges at the same rate for arbitrary
initializations, which gives precise quantitative results on convergence
rates.

###  1.2 Organization

The rest of this paper is organized as follows. In Section 2, we introduce our
notations and review previous works. Section 3 analyzes the IMH chain on
general state spaces. Section 4 analyzes the IMH chain on discrete state
space. Connections between IMH and RWMH algorithms as well as some future
directions are discussed in Section 5.

##  2 Preliminaries

###  2.1 The Metropolis-Hastings algorithm

Let $(\mathcal{X},\mathcal{F},\pi)$ be a probability space, equipped with
$\sigma$-algebra $\mathcal{F}$ and a probability measure $\pi$. In practice,
$\mathcal{X}$ usually stands for one of the following four possibilities:

  1. 1.

$\mathcal{X}$ is a finite set. For example, $\mathcal{X}=\\{1,2,\cdots,n\\}$.

  2. 2.

$\mathcal{X}$ is a countably infinite set. For example,
$\mathcal{X}=\mathbb{N}$.

  3. 3.

$\mathcal{X}$ is the Euclidean space, i.e., $\mathcal{X}=\mathbb{\mathbb{R}}$
or $\mathbb{R}^{p}$.

  4. 4.

$\mathcal{X}$ is a subset of the Euclidean space. For example,
$\mathcal{X}=\mathbb{R}^{+}$ or $\mathcal{X}=\\{x\in\mathbb{R}^{p}:\|x\|\leq
c\\}$ for some constant $c$.

When $\mathcal{X}$ is a finite or countably infinite set, $\mathcal{F}$ is
usually taken as $2^{\mathcal{X}}$ and thus all the subsets of $\mathcal{X}$
are measurable. When $\mathcal{X}$ is the Euclidean space or a subset of the
Euclidean space, $\mathcal{F}$ is usually taken as the Borel $\sigma$-algebra.
The four possibilities of $\mathcal{X}$ cover almost all the practical
applications of our interest. Therefore, without further specification, we
shall assume the measurable space $\mathcal{X}$ falls into one of the four
categories mentioned above henceforth. Throughout this paper, $\mathcal{X}$ is
called ‘state space’ as it also serves as the state space for the Markov
chains. Naturally, we say ‘discrete state space’ when $\mathcal{X}$ finite or
countably infinite, and ‘continuous state space’ or ‘general state space’ when
$\mathcal{X}$ is the Euclidean space or a subset of the Euclidean space. In
particular, when $\mathcal{X}$ is a general state space, we further assume the
probability measure $\pi$ has a density on $\mathcal{X}$. We slightly abuse
the notation and use $\pi$ to denote both the probability mass function (pmf)
on discrete state spaces and probability density function (pdf) on general
state spaces.

Given a target probability distribution $\pi$, the Metropolis-Hastings (MH)
algorithm is designed to draw samples from $\pi$ approximately. The details of
the Metropolis-Hastings algorithm are described in Algorithm 1.

Algorithm 1 Metropolis-Hastings Algorithm (MH)

Input: initial setting $x$, number of iterations $T$, Markov transition kernel
$q$

1:for $t=1,\cdots T$ do

2: Propose $x^{\prime}\sim q(x,x^{\prime})$

3: Compute  $a=\frac{q(x^{\prime},x)\pi(x^{\prime})}{q(x,x^{\prime})\pi(x)}$

4: Draw $r\sim\text{Uniform}[0,1]$

5: If $(r<a)$ then set $x=x^{\prime}$. Otherwise, leave $x$ unchanged.

6:end for

Algorithm 1 is arguably the most popular class of Markov chain Monte Carlo
(MCMC) methods. It is first proposed by Metropolis et al. MRR+ (53) in 1953 to
simulate a liquid in equilibrium with its gas phase. Hastings generalized the
algorithm in 1970 Has (70) and thus simulations following this scheme are
called the Metropolis-Hastings algorithm. The idea the of MH algorithm is to
construct a Markov chain $\Phi$ with stationary distribution $\pi$. If we run
$\Phi$ for a long time and collect the samples $\Phi_{1},\Phi_{2},\cdots$,
then the distribution of $\Phi_{n}$ will be very close to our target $\pi$ for
large enough $n$ under mild conditions.

It is worth mentioning that one of the most appealing features of the MH (and
other MCMC) algorithm is that, one can know $\pi$ up to a normalizing
constant. In many practical applications such as Bayesian computation, the
target distribution $\pi$ is often of the following form:

$\pi(x)=\frac{\pi_{u}(x)}{c},$

where $c=\int_{\mathcal{X}}\pi_{u}$ is referred to as the ‘normalizing
constant’. In practice, often one can easily evaluate $\pi_{u}$ but evaluating
the integral $\int_{\mathcal{X}}\pi_{u}$ is difficult. The MH algorithm is
still implementable under this setting as the following simple identity holds
for Step 3 of Algorithm 1:

$\frac{q(x^{\prime},x)\pi(x^{\prime})}{q(x,x^{\prime})\pi(x)}=\frac{q(x^{\prime},x)\pi_{u}(x^{\prime})}{q(x,x^{\prime})\pi_{u}(x)}.$

Therefore the ‘acceptance ratio’ is irrelevant to the normalizing constant
$c$. This is one reason that MCMC methods turn out to be extremely helpful in
sampling complicated distributions and become very popular in the Bayesian
statistical community.

As mentioned in Algorithm 1, one needs to specify a Markov transition kernel
$q$ before running the MH algorithm. Some popular choices of the proposals
include:

  1. 1.

Independent proposal: Here $q(x,y)=q(y)$ which does not depend on the current
state of the Markov chain. For example, $q=\mathcal{N}(0,\sigma^{2})$ for
$\sigma>0$.

  2. 2.

Random walk proposal: Here $q(x,y)=q(|x-y|)$. For example, at each state $x$,
the proposal may be chosen as $\mathcal{N}(x,\sigma^{2})$ for $\sigma>0$.

  3. 3.

Metropolis-adjusted Langevin algorithm (MALA): For example, at each state $x$,
the proposal may be chosen as
$\mathcal{N}(x+\frac{\delta}{2}\nabla\log\pi(x),\delta)$ for $\delta>0$.

An MH algorithm using an independent proposal is called the Independent
Metropolis-Hastings (IMH) algorithm, which is the main focus of our paper. The
IMH algorithm is one of the most commonly used MCMC algorithms. Some modern
applications of IMH algorithm include the Adaptive IMH HHH+ (09) and the
Particle IMH ADH (10), MDDJ (19).

###  2.2 Markov chain convergence

Let $\Phi=\\{\Phi_{1},\Phi_{2},\cdots\\}$ be an aperiodic, irreducible Markov
chain on state space $\mathcal{X}$ with transition kernel $P$. In the general
state space setting, it is further assumed that $P(x,\cdot)$ is absolute
continuous with density $p(x,y)$ with respect to the Lebesgue measure
$\lambda$, except perhaps for an atom $P(x,\\{x\\})>0$.

Standard Markov chain theory (see, for example, MT (12) Chapter 13) guarantees
that $\rVert P(x,\cdot)-\pi\lVert_{\sf TV}\rightarrow 0$ as
$n\rightarrow\infty$ for $\pi$-almost everywhere $x\in\mathcal{X}$.
Furthermore, a Markov chain $\Phi$ with transition kernel $P$ is said to be
uniformly ergodic if

######  Definition 1 (Uniformly Ergodic)

$\sup_{x}\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\leq Cr^{n}$ (2.1)

for $C>0$ and $0<r<1$.

When $\mathcal{X}$ is a continuous, unbounded space, then a Markov chain often
fails to be uniformly ergodic. Therefore, the following concept ‘geometrically
ergodic’ is needed. $\Phi$ is said to be geometrically ergodic if

######  Definition 2 (Geometrically Ergodic)

$\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\leq C(x)r^{n},$ (2.2)

for some $0<r<1$, and $\pi$-almost everywhere $x\in\mathcal{X}$.

Roughly speaking, both uniform ergodicity and geometric ergodicity guarantee
the Markov chain converges to its stationary distribution at a geometric rate
for $\pi$-a.e. initialization position $x$. However, it is a well-known
difficult problem to give sharp bounds on the right-hand side of 2.1 and 2.2.
In the next section, we will review some existing works on bounding the
convergence rates of MH algorithms.

###  2.3 Related works

There are numerous studies concerning the convergence rate of Markov chains.
The techniques for bounding convergence rates are significantly different
between Markov chains on general and discrete state spaces.

When $\mathcal{X}$ is finite (but possibly very large), it is clear from
Definition 1 and Definition 2 that every geometrically ergodic chain must be
uniformly ergodic, as we could take the supremum of $C(x)$ in formula 2.2 over
the state space $\mathcal{X}$. There are many techniques including
eigenanalysis, group theory, geometric inequalities, Fourier analysis,
multicommodity flows for getting upper and lower bounds of the convergence
rates. These techniques can sometimes turn into very sharp bounds of 2.1, see
Bayer and DiaconisBD+ (92), Diaconis and Saloff-Coste DSC (93)DSC+ (96),
Diaconis and ShahshahaniDS (81), Liu Liu (96) for inspiring examples. We also
refer the readers to Diaconis Dia (09), and Diaconis and Saloff-CosteD+ (13),
which give extensive reviews of the existing tools and results.

For general state Markov chains, uniform ergodicity is often ‘too good to be
true’ when the state space is continuous and unbounded (see, for example,
Theorem 3.1 of Mengerson and Tweedie MT+ (96)). Even geometrically ergodic is
not at all trivially satisfied by usual Markov chains. General conditions for
geometric ergodicity are established in the seminal works of Rosenthal Ros
(95), Mengerson and Tweedie MT+ (96), and Roberts and Tweedie RT (96). More
refined estimates for explicit $C(x)$ and $r$ are often referred to as ‘honest
bounds’ and are mostly developed under the ‘drift-and-minorization’ framework
by Rosenthal Ros (95). However, choosing a suitable ‘drift function’ is often
difficult in practical applications, and the estimates given by the ‘drift-
and-minorization’ framework are usually very conservative. There are very few
examples of sharp rates of convergence for the Metropolis algorithm, even for
toy models. Therefore, natural questions like Q1 and Q2 mentioned in the
introduction usually can not be answered. For more about the convergence of
Markov chains on general state spaces, we refer the readers to an excellent
survey by Roberts and Rosenthal RR (04).

For IMH algorithms, Liu Liu (96) has computed explicitly the eigenvalues and
eigenvectors of the Markov transition matrix on a discrete state space. For
IMH algorithms on general state spaces, Mengerson and Tweedie have shown that
uniform ergodicity and geometric ergodicity are equivalent. They have also
provided the necessary and sufficient condition for the IMH algorithm being
uniformly ergodic in Theorem 2.1 of MT+ (96). The exact transition
probabilities for the IMH algorithm are derived by Smith and Tierney ST (96).
The whole spectrum of the IMH algorithm is derived by Atchadé and Perron AP
(07). Quantitative convergence bounds for non-geometric IMH algorithms are
studied by Roberts and Rosenthal RR (11).

##  3 IMH on general state spaces

Now we are ready to state and prove our main results. Suppose one wish to
sample from a probability distribution with density $\pi$ on the general state
space $\mathcal{X}$. Let $p$ be a probability density function that we are
able to sample from. Throughout this section, we assume both $p$ and $\pi$ are
continuous therefore it makes sense to discuss the behavior of our Markov
chain at every point $x$ and avoids the measurability issues. We further
assume that the support of $\pi$ is contained in that of $p$, i.e.,
$\text{Supp}(\pi)\subset\text{Supp}(p)$. The IMH algorithm is defined as
follows:

Algorithm 2 Independent Metropolis-Hastings Algorithm (IMH)

Input: initial setting $x$, number of iterations $T$, proposal distribution
$p$

1:for $t=1,\cdots T$ do

2: Propose $x^{\prime}\sim p(x^{\prime})$

3: Compute  $a(x,x^{\prime})=\frac{p(x)\pi(x^{\prime})}{p(x^{\prime})\pi(x)}$

4: Draw $r\sim\text{Uniform}[0,1]$

5: If $(r<a)$ then set $x=x^{\prime}$. Otherwise, leave $x$ unchanged.

6:end for

This section is divided into two parts. In Section 3.1, we give the exact
convergence speed of the IMH algorithm, which answers Q1 proposed in Section
1. In Section 3.2, we provide the answer of Q2 for the IMH algorithm.

###  3.1 Exact convergence speed

Let $w$ be the ratio betwen densities $\pi$ and $p$, i.e.,

$\displaystyle w(x)=\frac{\pi(x)}{p(x)}.$

Then it’s clear that the acceptance ratio $a$ can be written as

$\displaystyle a(x,x^{\prime})=\frac{w(x^{\prime})}{w(x)}.$

The following theorem is proved by Mengerson and Tweedie, which gives the
necessary and sufficient conditions for IMH being geometrically ergodic.

######  Theorem 3.1 (Mengerson and Tweedie MT+ (96), Theorem 2.1)

With all the notations as above, we have

  1. 1.

Let $\Phi\doteq\\{\Phi_{1},\Phi_{2},\cdots\\}$ be the Markov chain associated
with the IMH algorithms, with target density $\pi$ and proposal density $p$.
Then the followings are equivalent:

     * •

$\Phi$ is uniformly ergodic

     * •

$\Phi$ is geometrically ergodic

     * •

Function $w(x)$ is unformly bounded, i.e., there exists $M>0$ such that
$w(x)\leq M$ for all $x\in\mathcal{X}$

  2. 2.

Suppose $w(x)\leq M$ for all $x\in\mathcal{X}$, then for any $n\geq 1$

$\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\leq(1-\frac{1}{M})^{n}$ (3.1)

Theorem 3.1 shows that $w$ being uniformly upper bounded is the necessary and
sufficient condition for the IMH algorithm being geometrically ergodic. In
particular, uniformly ergodic and geometrically ergodic are equivalent for the
IMH chain. It is therefore convenient to define:

###### Definition 3

[Maximal Variation Distance]

$d_{\text{IMH}}(t)\doteq\max_{x\in\mathcal{X}}\|P^{t}(x,\cdot)-\pi\|_{\sf
TV}.$

$d_{\text{IMH}}(t)$ describes the distance to the equilibrium distribution in
the worst-case scenario. It is worth mentioning that $d(t)$ is also called the
‘maximal variation distance’ and is widely used in the Markov chain
literature. For example, a primary objective of analyzing Markov chains on
discrete state spaces is to bound $d(t)$, see Levin et al. LP (17), Aldous and
Diaconis AD (87) for discussions.

For the IMH chain, an immediate corollary for Theorem 3.1 is:

###### Corollary 1

Let $w^{\star}\doteq\sup_{x}w(x)$, then for any $n\geq 1$

$d_{\text{IMH}}(n)\leq(1-\frac{1}{w^{\star}})^{n}$ (3.2)

Corollary 1 gives the best possible upper bound of Theorem 3.1. Our next
theorem shows, suppose $w^{\star}$ can be attained at some
$x^{\star}\in\mathcal{X}$, then $(1-\frac{1}{w^{\star}})^{n}$ is also a lower
bound and is thus the exact convergence speed of the IMH chain.

###### Theorem 3.2

With all the notations as above, assume that there exists $x\in\mathcal{X}$
such that $w(x^{\star})=w^{\star}$, then we have:

$d_{\text{IMH}}(n)=(1-\frac{1}{w^{\star}})^{n}$ (3.3)

We will show both $d_{\text{IMH}}(n)\leq(1-\frac{1}{w^{\star}})^{n}$ and
$d_{\text{IMH}}(n)\geq(1-\frac{1}{w^{\star}})^{n}$ holds. Though the first
part is already shown in Mengerson and Tweedie MT+ (96), we provide give a
coupling proof here for the sake of completeness.

######  Proof (Proof of the upper bound in Theorem 3.2)

We prove the upper bound by a coupling argument. We define a coupling of the
IMH algorithm to be a pair of two stochastic processes
$(\Phi,\tilde{\Phi})\doteq(\Phi_{i},\tilde{\Phi}_{i})_{i=0}^{\infty}$ such
that both $\Phi$ and $\tilde{\Phi}$ are both IMH chains with proposal density
$p$, though they may have different initial distributions. We further require
the two chains stay together after they visit the same state, i.e.:

$\text{If }\Phi_{i}=\tilde{\Phi}_{i}\text{ for some }i,\text{ then for any
}j\geq i:\Phi_{j}=\tilde{\Phi}_{j}.$ (3.4)

Moreover, suppose $\tilde{\Phi}$ starts at stationary, in other words,

$\tilde{\Phi}_{0}\sim\pi,$ (3.5)

then it is clear that $\tilde{\Phi}_{i}$ is also distributed according to
$\pi$. Then the following inequality is standard in Markov chain theory, see
Levin et al. LP (17) Theorem 5.2, or Rosenthal Ros (95) page 16 for a proof .

###### Fact 1

Let $(\Phi,\tilde{\Phi})$ be an arbitrary coupling satisfying 3.4 and 3.5. Let
$T$ be the first time the two chains meet:

$T\doteq\min\\{n,\Phi_{n}=\tilde{\Phi}_{n}\\}.$ (3.6)

Then we have:

$\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\leq\mathbb{P}(T\geq n)$ (3.7)

To use inequality 3.7, it suffices to design a coupling between $\Phi$ and
$\tilde{\Phi}$ and bound the tail probability of meeting time $T$.

In our IMH algorithm example, given any current state $x$, the actual
transition density from $x$ to $y$ is given by:

$P(x,y)=p(y)\min\\{\frac{w(y)}{w(x)},1\\}\geq\frac{p(y)w(y)}{w^{\star}}=\frac{\pi(y)}{w^{\star}}.$

Therefore, the transition kernel $P$ satisfies the following minorization
condition:

$P(x,\cdot)\geq\frac{1}{w^{\star}}\pi(\cdot)$ (3.8)

for any $x\in\mathcal{X}$.

Inequality 3.8 allows us to spilt $P(x,\cdot)$ into a mixture of two
probability distributions:

$P(x,\cdot)=\frac{1}{w^{\star}}\pi(\cdot)+(1-\frac{1}{w^{\star}})q_{\text{res}}(x,\cdot)$
(3.9)

where $q_{\text{res}}(x,\cdot)$ is the residual measure defined by

$q_{\text{res}}(x,A)=\frac{\pi(A)-\frac{1}{w^{\star}}P(x,A)}{1-\frac{1}{w^{\star}}}$
(3.10)

for any measureable set $A$.

Now we are ready to define our coupling. At time $k$, let $x,x^{\prime}$ be
two arbitrary current states of $\Phi$ and $\tilde{\Phi}$, respectively.
Assume $x^{\prime}=x$, then sample $\Phi_{k+1}$ from $P$ and set
$\Phi_{k+1}=\tilde{\Phi}_{k+1}$. Otherwise, flip a coin with head probability
$\frac{1}{w^{\star}}$, if it comes up heads, sample $\Phi_{k+1}$ according to
$\pi$ and set $\Phi_{k+1}=\tilde{\Phi}_{k+1}$. Otherwise, sample $\Phi_{k+1}$
and $\Phi_{k+1}$ from $q_{\text{res}}(x,\cdot)$ and
$q_{\text{res}}(x^{\prime},\cdot)$ independently. It is not hard to verify the
pair $(\Phi,\tilde{\Phi})$ defined above is a coupling satisfying 3.4 and 3.5.
Meanwhile, at each step before $\Phi$ and $\tilde{\Phi}$ meets, the meeting
probability equals $\frac{1}{w^{\star}}$. Therefore the following inequality
holds:

$\mathbb{P}(T\geq n)\leq(1-\frac{1}{w^{\star}})^{n}.$ (3.11)

Combining 3.7 with 3.11, we have

$d_{\text{IMH}}(n)\leq(1-\frac{1}{w^{\star}})^{n},$ (3.12)

as desired.

The lower bound proof requires the following two lemmas. The first lemma shows
the total variation distance is lower bounded by a geometric series with the
‘rejection probability’ as the common ratio.

###### Lemma 1

Let $R(x)$ be the ‘rejected probability’ given current state $x$, more
precisely,

$R(x)=\int_{\mathcal{X}}(1-\min\\{\frac{w(y)}{w(x)},1\\})p(y)dy$ (3.13)

Then

$\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\geq(R(x))^{n}$ (3.14)

######  Proof (Proof of Lemma 1)

Given a Markov chain starting at $x$, then it is clear that the probability of
staying at $x$ after $n$ steps is no less than $(R(x))^{n}$. Therefore, we
have

$P^{n}(x,\\{x\\})\geq(R(x))^{n}.$

Meanwhile, it is clear that $\pi(\\{x\\})=0$ as $\pi$ is a continuous
distribution. We have:

$\|P^{n}(x,\cdot)-\pi\|_{\sf
TV}=\max_{A\subset\mathcal{X}}\|P^{n}(x,A)-\pi(A)\|\geq(R(x))^{n}-0=(R(x))^{n},$

as desired.

The next lemma gives the formula for computing $R(x)$

###### Lemma 2

With all the notations as above, we have

$R(x)=1-\frac{\int_{y\in C(w(x))}\pi(y)dy}{w(x)}-\int_{y\in
C^{c}(w(x))}p(y)dy$ (3.15)

where $C(w)\doteq\\{z:w(z)\leq w\\}$ is a subset of $\mathcal{X}$ with ratio
no larger than $w$.

In particular

$R(x^{\star})=1-\frac{1}{w^{\star}}.$ (3.16)

######  Proof (Proof of Lemma 2)

For fixed $x$, we could split $\mathcal{X}$ into $C(w(x))$ and $C^{c}(w(x))$,
straightforward calculation gives:

$\displaystyle R(x)$
$\displaystyle=\int_{\mathcal{X}}(1-\min\\{\frac{w(y)}{w(x)},1\\})p(y)dy$
$\displaystyle=1-\frac{\int_{y\in C(w(x))}p(y)w(y)dy}{w(x)}-\int_{y\in
C^{c}(w(x))}p(y)dy$ $\displaystyle=1-\frac{\int_{y\in
C(w(x))}\pi(y)dy}{w(x)}-\int_{y\in C^{c}(w(x))}p(y)dy.$

In particular, $C(w(x^{\star}))=C(w^{\star})=\mathcal{X}$ by definition,
therefore

$R(x^{\star})=1-\frac{\int_{y\in\mathcal{X}}\pi(y)dy}{w^{\star}}=1-\frac{1}{w^{\star}},$

which completes our proof.

The lower bound of Theorem 3.2 is immediate after combining Lemma 1 and Lemma
2.

######  Proof (Proof of the lower bound in Theorem 3.2)

Combining Lemma 1 and Lemma 2, we have:

$\displaystyle d_{\text{IMH}}(t)$
$\displaystyle=\max_{x\in\mathcal{X}}\|P^{t}(x,\cdot)-\pi\|_{\sf TV}$
$\displaystyle\geq\|P^{t}(x^{\star},\cdot)-\pi\|_{\sf TV}$ $\displaystyle\geq
R^{n}(x^{\star})$ $\displaystyle=(1-\frac{1}{w^{\star}})^{n},$

which completes the proof.

###### Remark 1

Another way of showing the lower bound is as follows. It is not hard to verify
that
$P(x^{\star},\cdot)=R(x^{\star})\delta_{x^{\star}}+\frac{1}{w^{\star}}\pi(\cdot)$,
where $\delta_{x^{\star}}$ is the point mass at $x^{\star}$. As $\pi$ is
invariant under the action of $P$, i.e., $\pi P=\pi$, we have:

$\displaystyle P^{2}(x^{\star},\cdot)$
$\displaystyle=R(x^{\star})P(x^{\star},\cdot)+\frac{1}{w^{\star}}\pi(\cdot)$
$\displaystyle=R^{2}(x^{\star})\delta_{x^{\star}}+(1-R^{2}(x^{\star}))\pi(\cdot)$

The last step uses the equality $R(x^{\star})=1-\frac{1}{w^{\star}}$. By
induction, we have

$P^{n}(x^{\star},\cdot)=R^{n}(x^{\star})\delta_{x^{\star}}+(1-R^{n}(x^{\star}))\pi(\cdot),$

and therefore $\|P^{n}(x^{\star},\cdot)-\pi\|_{\sf
TV}=R^{n}(x^{\star})\|\delta_{x^{\star}}-\pi\|_{\sf
TV}=(1-\frac{1}{w^{\star}})^{n}$.

Theorem 3.2 gives the exact converge speed as the upper bound matches with the
lower bound exactly. This result closes the gap in the literature regarding
the convergence speed of IMH algorithm. For example, Smith and Tierney ST (96)
proved that $d_{\text{IMH}}(t)$ is upper bounded by a term of order at most
$(1-\frac{1}{w^{\star}})^{n}$ (see page 5 of ST (96)). Similar result is also
proved by Tierney (Tie (94), Corollary 4). Mengerson and Tweedie (MT+ (96),
Theorem 2.1) proves $d_{\text{IMH}}(t)\leq(1-\frac{1}{w^{\star}})^{n}$. But it
seems none of the previous results contain the lower bound.

The main assumption in Theorem 3.2 is that $w^{\star}$ is attained at some
$x^{\star}\in\mathcal{X}$. When the supremum cannot be actually attained, the
exact formula 3.3 does not hold . But our next result shows
$d_{\text{IMH}}(n)$ still decays at the rate of $1-\frac{1}{w^{\star}}$.

###### Theorem 3.3

Assume $w^{\star}=\sup_{x}w(x)<\infty$ and $w(x)<w^{\star}$ for all $x$. Then

  1. 1.

For any $\epsilon>0$, we have

$(1-\frac{1}{w^{\star}}-\epsilon)^{n}\leq
d_{\text{IMH}}(n)\leq(1-\frac{1}{w^{\star}})^{n}$ (3.17)

  2. 2.

$\lim_{n\rightarrow\infty}\frac{\log
d_{\text{IMH}}(n)}{n}=1-\frac{1}{w^{\star}}$ (3.18)

###### Remark 2

Formula 3.18 shows the decay rate of $d_{\text{IMH}}(n)$ is
$1-\frac{1}{w^{\star}}$. It is worth mentioning that 3.18 is slightly weaker
than $d_{\text{IMH}}(n)=\Theta((1-\frac{1}{w^{\star}})^{n})$. For example,
sequences such as $(1-\frac{1}{w^{\star}})^{n}/n$ satisfies 3.18 but is not
$\Theta((1-\frac{1}{w^{\star}})^{n})$.

###### Proof

We only prove the first part of Theorem 3.3 as the second part is then
immediate. Moreover, it suffices to prove the left part of inequality 3.17, as
the right part is proved in Theorem 3.2.

For any $\epsilon>0$, choose $\delta>0$ such that
$\delta<\frac{\epsilon(w^{\star})^{2}}{1+\epsilon w^{\star}}$. By definition,
there exists $x_{\delta}$ such that $w(x_{\delta})>w^{\star}-\delta$. Then
$R(x_{\delta})$ can be bounded by 3.13

$R(x_{\delta})\geq\int_{\mathcal{X}}(1-\frac{w(y)}{w(x_{\delta})})p(y)dy=1-\frac{1}{w(x_{\delta})}>1-\frac{1}{w^{\star}-\delta}\geq(1-\frac{1}{w^{\star}}-\epsilon)$
(3.19)

By Lemma 1, we have:

$\displaystyle d_{\text{IMH}}(t)$
$\displaystyle=\max_{x\in\mathcal{X}}\|P^{t}(x,\cdot)-\pi\|_{\sf TV}$
$\displaystyle\geq\|P^{t}(x_{\delta},\cdot)-\pi\|_{\sf TV}$ $\displaystyle\geq
R^{n}(x_{\delta})$ $\displaystyle=(1-\frac{1}{w^{\star}}-\epsilon)^{n},$

which finishes our proof.

Now we provide some concrete examples to help illustrate the use of Theorem
3.2 and Theorem 3.3. The next example is discussed in Smith and Tierney ST
(96), and Jones and Hobert JH (01).

######  Example 2 (Exponential target with exponential proposal)

Suppose the target distribution is $\text{Exp}(1)$, that is, $\pi(x)=e^{-x}$
and $\mathcal{X}=[0,\infty)$. Consider the IMH chain $\Phi$ with an
$\text{Exp}(\theta)$ proposal, that is, $p(x)=\theta e^{-\theta x}$. Therefore
the weight function has the following form

$w(x)=\frac{\pi(x)}{p(x)}=\frac{1}{\theta}e^{-(1-\theta)x}.$

It is not hard to verify that $\sup w(x)<\infty$ is equivalent to
$0<\theta\leq 1$. Therefore, when $\theta\in(0,1]$, the algorithm is uniformly
ergodic; otherwise, it is not geometrically ergodic.

For any fixed $\theta\in(0,1]$, we have $w^{\star}(\theta)=\frac{1}{\theta}$
which is attained at $x=0$. Therefore we could apply Theorem 3.2 and conclude
that:

$d_{\text{IMH}}(\theta,n)=(1-\theta)^{n}.$

This also shows the ‘optimal choice’ of $\theta$ is $\theta=1$, which is
obviously true as $\theta=1$ corresponds to sampling from the stationary
distribution $\text{Exp}(1)$ directly.

For any arbitrary fixed $\theta$ and accuracy $\epsilon$, we could also solve
the equation

$\epsilon=(1-\theta)^{n}.$

for $n$ to derive the number of steps that is necessary and sufficient for the
IMH chain to converge within $\epsilon$-accuracy. In this case we have

$n=\frac{\log\epsilon}{\log(1-\theta)}$ (3.20)

steps are both necessary and sufficient. Let the accuracy $\epsilon$ be fixed
at $0.01$, then 3.20 gives us $n=6.64$ when $\theta=0.5$; $n=43.71$ when
$\theta=0.1$; and $n=458.21$ when $\theta=0.01$. The relationship between $n$
and $\theta$ is also shown in Figure 1. As expected, when $\theta$ is getting
closer to $1$, the IMH algorithm is converging faster.

Figure 1: Number of steps for the IMH algorithm to converge, $\epsilon=0.01$

The next example is a higher-dimensional example with is related to Bayesian
statistics.

######  Example 3 (Bayesian inference with Multinomial Likelihood)

Let $\vec{x}=(x_{1},\cdots,x_{K})$ be a sample of size $N=\sum_{i=1}^{K}x_{i}$
from a $K$-category multinomial distribution with parameter
$\vec{\theta}=(\theta_{1},\cdots,\theta_{K})$. In other words, the likelihood
of is of the following form

$p_{\vec{\theta}}(\vec{x})=\frac{N!}{\prod_{i=1}^{K}x_{i}!}\theta_{i}^{x_{i}}.$
(3.21)

Let $\pi(\vec{\theta})$ be a fixed prior on the K-simplex $\Theta$, i.e.,

$\Theta=\\{\theta\in
R^{K}:\sum_{i=1}^{K}\theta_{i}=1~{}\text{and}~{}\theta_{i}\geq 0~{}\text{for
all}~{}i\\}$

. Given data $x$, it is of our interest to sample from the posterior
distribution $\pi(\vec{\theta}|\vec{x})$ which has density

$\pi(\vec{\theta}|\vec{x})\propto\pi(\vec{\theta})p_{\vec{\theta}}(\vec{x}).$

In this example, we assume the prior is chosen as a Dirichlet distribution,
with parameter $\vec{\alpha}$, i.e.,

$\pi(\vec{\theta})\propto\theta_{i}^{\alpha_{i}-1}.$ (3.22)

Since Dirichlet distribution is the conjugate prior of the multinomial
likelihood, standard calculation shows the posterior is still a Dirichlet
distribution, with parameter
$\vec{\alpha}+\vec{x}=(\alpha_{1}+x_{1},\cdots,\alpha_{K}+x_{K})$.

Consider the IMH chain $\Phi$ with a $\text{Uniform}(\Theta)$ proposal.
Therefore the weight function can be calculated as:

$w(\vec{\theta}|\vec{x})=\frac{\pi(\vec{\theta}|\vec{x})}{p(\vec{\theta})}=\frac{(N+\alpha-1)!}{(K-1)!\prod_{i=1}^{K}(x_{i}+\alpha_{i}-1)!}\prod_{i=1}^{k}\theta_{i}^{x_{i}+\alpha_{i}-1},$
(3.23)

where $\alpha\doteq\sum_{i}\alpha_{i}$.

It is clear that the maximum of $w(\vec{\theta}|\vec{x})$ is attained at

$\theta^{\star}=(\frac{x_{1}+\alpha_{1}-1}{N+\alpha-K},\cdots,\frac{x_{K}+\alpha_{K}-1}{N+\alpha-K}),$

therefore we have:

$w^{\star}=\frac{\pi(\vec{\theta}|\vec{x})}{p(\vec{\theta})}=\frac{(\alpha+N-1)!}{(K-1)!\prod_{i=1}^{K}(x_{i}+\alpha_{i}-1)!}\frac{\prod_{i=1}^{k}(x_{i}+\alpha_{i}-1)^{x_{i}+\alpha_{i}-1}}{(x+\alpha-K)^{x+\alpha-K}}.$
(3.24)

Therefore, we can apply Theorem 3.2 and conclude that:

$d_{\text{IMH}}(n|\vec{x})=(1-\frac{1}{w^{\star}})^{n},$

where $w^{\star}$ is defined in 3.24.

We can also investigate the asymptotic behavior of 3.24. Assume $K$ is fixed,
and

$\frac{\vec{x}}{N}\rightarrow\vec{p}=(p_{1},\cdots,p_{K})$

when $N\rightarrow\infty$. Here $\vec{p}$ can be understand as the true (but
unknown) parameter for the multinomial distribution. When the number of trials
$N$ is large enough, the law of large numbers guarantees the porpotion of each
category converges to $\vec{p}$. Sterling’s formula gives the following
approximation of $w^{\star}$:

$w^{\star}\sim\frac{1}{(K-1)!}\sqrt{\frac{N^{K-1}}{(2\pi)^{K-1}\prod_{i=1}^{K}p_{i}}}.$
(3.25)

Therefore, the number of steps for convergence with $\epsilon$-accuracy is
approximately:

$n(\epsilon)=\frac{\log\epsilon}{\log(1-\frac{1}{w^{\star}})}\sim(\log\epsilon)w^{\star}\sim\frac{\log\epsilon}{\sqrt{(2\pi)^{K-1}\prod_{i=1}^{K}p_{i}}}N^{\frac{K-1}{2}},$

so $\Theta(N^{\frac{K-1}{2}})$ steps are necessary and sufficient for
convergence.

When $K=2$, the model is known as Beta-Binomial example. Suppose we choose
prior $\pi=\text{Uniform}(\Theta)$, where $\Theta=\\{(p,q)|0\leq p\leq
1,q=1-p\\}$. The relation between $n(0.01)$ and $N$ is shown in Figure 2. As
shown in Figure 2, the algorithm converges faster when $p$ is closer to $0.5$,
and $n(\epsilon)$ grows sublinearly with respect to $N$.

###### Remark 3

If one uses some non-conjugate priors such as truncated Gaussian prios, then
the calculation for $w^{\star}$ is much more complicated. The asymptotics can
still go through using a comparison argument, so $\Theta(N^{\frac{K-1}{2}})$
steps are still necessary and sufficient for convergence. Detailed
calculations of the Beta likelihood with non-conjugate priors can be found in
Section 4.2.1 of Wang Wan (20).

Figure 2: Number of steps for the IMH algorithm to converge, $\epsilon=0.01$

Now we briefly conclude this part, in this part we provide answer to our first
question (Q1) proposed in Section 1 for the IMH algorithm on general state
spaces. Our results can be briefly summarized below:

  1. 1.

If $w^{\star}=\infty$, then the IMH chain is not geometrically ergodic, thus
the chain does not converge at a geometric rate.

  2. 2.

If $w^{\star}<\infty$ and can be attained at some $x^{\star}\in\mathcal{X}$,
then we can derive the following exact converge speed:

$d_{\text{IMH}}(n)=(1-\frac{1}{w^{\star}})^{n}$

  3. 3.

If $w^{\star}<\infty$ but cannot be attained at any $x\in\mathcal{X}$, then
the exact convergence rate is still $(1-\frac{1}{w^{\star}})$, though Formula
3.3 may not hold.

###  3.2 Convergence rate at every point

In Section 3.1, we have shown the maximum distance between the IMH chain and
its stationary distribution decays at the rate of $(1-\frac{1}{w^{\star}})$.
However, as we mentioned in Section 1, this only gives an upper bound for the
convergence rate of among all possible initializations. To be more precise, we
define the following functions to describe the convergence rate at a single
point $x$.

###### Definition 4

Let

$r_{-}(x)\doteq\liminf_{n\rightarrow\infty}\frac{\log\|P^{n}(x,\cdot)-\pi\|_{\sf
TV}}{n}$

and

$r_{+}(x)\doteq\limsup_{n\rightarrow\infty}\frac{\log\|P^{n}(x,\cdot)-\pi\|_{\sf
TV}}{n}.$

In particular, if $r_{-}(x)=r^{+}(x)$ for some $x\in\mathcal{X}$, we define
the convergence rate at $x$ to be

$r(x)\doteq\lim_{n\rightarrow\infty}\frac{\log\|P^{n}(x,\cdot)-\pi\|_{\sf
TV}}{n}.$

The follwing corollary is immediate using Lemma 1, Theorem 3.2, and Theorem
3.3

###### Corollary 2

With all the notations as above, we have

  * •

For every $x\in\mathcal{X}$,

$R(x)\leq r_{-}(x)\leq r^{+}(x)\leq 1-\frac{1}{w^{\star}}.$

  * •

$\sup_{x}r^{+}(x)=\sup_{x}r_{-}(x)=1-\frac{1}{w^{\star}}$

  * •

If there is $x^{\star}\in X$ such that $w(x^{\star})=w^{\star}$, then
$r(x^{\star})=1-\frac{1}{w^{\star}}$.

Corollary 2 gives a lower bound on $r_{-}(x)$ as well as an upper bound on
$r^{+}(x)$. However, the lower bound does not match the upper lower unless
$x=x^{\star}$. For example, let $x_{n}$ be a sequence of points such that
$w(x_{n})\rightarrow\inf_{x}w(x)$, then it is clear from 3.13 that
$R(x_{n})\rightarrow 0$. However, the upper bound is a constant
$1-\frac{1}{w^{\star}}$ so the two bounds does not match with each other.

It is therefore natural to ask whether $r(x)$ always exists, if so, what is
the value of $r(x)$? Our next result shows, for the IMH algorithm, every
initialization converge at the same rate, which is $1-\frac{1}{w^{\star}}$.

###### Theorem 3.4

Suppose $w^{\star}<\infty$. If one of the following two assumptions holds:

  * •

$w^{\star}=w(x^{\star})$ for some $x^{\star}\in\mathcal{X}$, and both $p$ and
$\pi$ are locally Lipschitz.

  * •

$w^{\star}>w(x)$ for any $x\in\mathcal{X}$, and $w$ is Lipschitz continuous.

Then for every $x\in\mathcal{X}$:

$r(x)=r_{-}(x)=r^{+}(x)=1-\frac{1}{w^{\star}}.$ (3.26)

In other words, the convergence rate for every $x$ equals
$1-\frac{1}{w^{\star}}$.

To prove Theorem 3.4, we need to first introduce the previous result by Smith
and Tierney ST (96) on the exact transition probabilities for the IMH chain.
Let $\tilde{\Pi}$ and $\tilde{P}$ be two probability distribution functions
(PDF) on $\mathbb{R}^{+}$ defined by:

$\displaystyle\tilde{\Pi}(w)\doteq\pi(C(w))=\int_{y\in C(w)}\pi(y)dy$
$\displaystyle\tilde{P}(w)\doteq\pi(C(w))=\int_{y\in C(w)}p(y)dy,$

and let $\tilde{\Pi}(dw)$ and $\tilde{P}(dw)$ denote the corresponding
probability measure on Borel sets of $R^{+}$.

Furthermore, let function $\lambda:\mathbb{R}^{+}\rightarrow\mathbb{R}$ be

$\lambda(w)\doteq\int_{v\leq
w}(1-\frac{v}{w})\tilde{P}(dv)=\tilde{P}(w)-\frac{\tilde{\Pi}(w)}{w}.$ (3.27)

Comparing 3.27 with 3.13, it is not hard to verify that
$\lambda(w)=1-\frac{1}{w}$ for $w\geq w^{\star}$, and $\lambda(w(x))$ equals
the rejection probability $R(x)$ for any $x\in\mathcal{X}$.

The $n$-step transition probability of the IMH algorithm is given by Theorem 1
of Smith and Tierney ST (96):

######  Theorem 3.5 (Theorem 1 of Smith and Tierney ST (96))

The $n$-step transition kernel for the IMH chain is given by:

$P^{n}(x,dy)=T_{n}(\max\\{w(x),w(y)\\})\pi(y)dy+R^{n}(w(x))\delta_{x}(dy),$
(3.28)

where $T_{n}:\mathbb{R}^{+}\rightarrow\mathbb{R}$ is defined by:

$T_{n}(w)=\int_{w}^{\infty}\frac{n\lambda^{n-1}(v)}{v^{2}}dv.$ (3.29)

Using Theorem 3.5, the proof of Theorem 3.4 is given as follows:

######  Proof (Proof of Theorem 3.4)

We prove Theorem 3.4 under the first assumption. That is, both $p$ and $\pi$
are locally Lipschitz continuous, and $w^{\star}(x)=w(x^{\star})$ for some
$x^{\star}\in\mathcal{X}$. By Corollary 2, it suffices to prove
$r_{-}(x)\geq(1-\frac{1}{w^{\star}})$. We prove this by contradiction. Suppose
there exist an $\epsilon>0$ and some $x_{0}\in\mathcal{X}$ such that

$r_{-}(x_{0})\leq 1-\frac{1}{w^{\star}-\epsilon},$

then we claim $w(x_{0})\leq w^{\star}-\epsilon$. Otherwise we have

$R(x_{0})\geq\int_{\mathcal{X}}(1-\frac{w(y)}{w(x_{0})})p(y)dy=1-\frac{1}{w(x_{0})}>1-\frac{1}{w^{\star}-\epsilon},$

which contradicts with $R(x_{0})\leq r_{-}(x_{0})$

Given $w(x_{0})\leq w^{\star}-\epsilon$, for any $y$ with $w(y)\geq
w^{\star}-\epsilon$, Theorem 3.5 gives us:

$P^{n}(x_{0},dy)=T_{n}(w(y))\pi(y)dy.$ (3.30)

Notice that, we have the following estimate for $T_{n}(w)$:

$\displaystyle T_{n}(w)$
$\displaystyle=\int_{w}^{w^{\star}}\frac{n\lambda^{n-1}(v)}{v^{2}}dv+\int_{w^{\star}}^{\infty}\frac{n(1-\frac{1}{v})^{n-1}}{v^{2}}dv$
$\displaystyle=\int_{w}^{w^{\star}}\frac{n\lambda^{n-1}(v)}{v^{2}}dv+1-(1-\frac{1}{w^{\star}})^{n}$
$\displaystyle\leq
n\lambda^{n-1}(w^{\star})\int_{w}^{w^{\star}}\frac{1}{v^{2}}dv+1-(1-\frac{1}{w^{\star}})^{n}$
$\displaystyle=n(1-\frac{1}{w^{\star}})^{n-1}\frac{w^{\star}-w}{ww^{\star}}+1-(1-\frac{1}{w^{\star}})^{n}$

Let
$D_{n}\doteq\\{y\in\mathcal{X}:w(y)>\max\\{1,w^{\star}-\frac{w^{\star}-1}{2n}\\}$
be a subset of $\mathcal{X}$. Then for any $y\in D_{n}$,

$T_{n}(w(y))\leq 1-\frac{1}{2}(1-\frac{1}{w^{\star}})^{n}$

Therefore, when $n$ is large enough such that
$w^{\star}-\frac{w^{\star}-1}{2n}>w^{\star}-\epsilon$, by 3.30 we have

$\lVert P^{n}(x_{0},\cdot)-\pi\rVert_{\sf TV}\geq\lvert
P^{n}(x_{0},D_{n})-\pi(D_{n})\rvert\geq\frac{1}{2}\pi(D_{n})(1-\frac{1}{w^{\star}})^{n}$

Now we claim there exists a universal constant $c>0$ such that

$\pi(D_{n})\geq\frac{c}{n}$

If the claim if true, then $r_{-}(x_{0})\geq
1-\frac{1}{w^{\star}}-\lim_{n}\frac{\log n-\log
c/2}{n}=1-\frac{1}{w^{\star}}$, as desired.

To prove the claim, notice that the function $w$ is also locally Lipschitz at
$x^{\star}$ as both $\pi$ and $p$ are locally Lipschitz. Therefore, there
exists some $c^{\prime}>0$ such that when
$y\in[x^{\star}-\frac{c^{\prime}}{n},x^{\star}+\frac{c^{\prime}}{n}]$,
$w(y)\geq w^{\star}-\frac{w^{\star}-1}{2n}$. For $n$ large enough such that
$w^{\star}-\frac{w^{\star}-1}{2n}>1$, we have

$\pi(D_{n})\geq\int_{y\in[x^{\star}-\frac{c^{\prime}}{n},x^{\star}+\frac{c^{\prime}}{n}]}\pi(y)dy\geq\frac{c}{n},$

where the last inequality uses the continuity of $\pi$.

Proof of Theorem 3.4 under the second assumption is almost the same as above.
The only difference is that we need to find a sequence $x_{n}$ such that
$w(x_{n})\rightarrow w^{\star}$, and thus we need to further assume both $p$
and $\pi$ are Lipschitz continuous.

We believe the extra assumption requiring $\pi$ and $p$ locally Lipschitz
continuous (or $w$ Lipschitz continuous) is reasonable and is satisfied in
almost all the practical assumptions. On the one hand, in most of the
practical situations, both $\pi$ and $p$ are continuously differentiable,
which implies locally Lipschitz continuous. On the other hand, we do not know
if Theorem 3.4 is true in full generality. It is an outstanding open problem
to prove (or disprove) $r(x)=1-\frac{1}{w^{\star}}$ for all $x$ without the
‘locally Lipschitz’ assumption.

We can apply Theorem 3.4 to Example 2 and Example 3 to obtain the convergence
rate at every point.

######  Example 4 (Exponential target with exponential proposal, continued)

With all the settings same as Example 2, since both $p$ and $\pi$ are
continuously differentiable and are thus locally Lipschitz, we apply Theorem
3.4 to conclude the convergence rate for every $x\in[0,\infty)$ equals
$1-\theta$. In Section 5 of Smith and Tierney ST (96), they have calculated
the transition probability via formula 3.28 explicitly, and have:

$\mathbb{P}(\Phi_{n}>y|\Phi_{0}=x)=\bigg{(}1+\frac{(1-\theta)^{n}}{n\theta}\bigg{)}e^{-y}+o\bigg{(}\frac{(1-\theta)^{n}}{n}\bigg{)}.$

The dominant term of total variation distance is also $(1-\theta)^{n}$, which
agrees with our result.

######  Example 5 (Bayesian inference with Multinomial likelihood, continued)

With all the settings same as Example 2, since both $p$ and $\pi$ are
continuously differentiable and are thus locally Lipschitz, we apply Theorem
3.4 to conclude the convergence rate for every $\theta\in\Theta$ equals

$1-\frac{1}{w^{\star}}$

, where

$w^{\star}=\frac{(\alpha+N-1)!}{(K-1)!\prod_{i=1}^{K}(x_{i}+\alpha_{i}-1)!}\frac{\prod_{i=1}^{k}(x_{i}+\alpha_{i}-1)^{x_{i}+\alpha_{i}-1}}{(x+\alpha-K)^{x+\alpha-K}}$

as we have calculated in 3.24.

Now we conclude this section. In Section 3.2 we answer Q2 for the IMH
algorithms on general state spaces. Our results suggest, under mild
conditions, the IMH algorithm converges at the same rate (which is
$1-\frac{1}{w^{\star}}$ as shown in 3.1) for every $x\in\mathcal{X}$.
Combining Section 3.1 with Section 3.2, we can answer Q1 and Q2 together in
the following way: For an IMH chain on a general state space, the exact
converge rate equals $1-\frac{1}{w^{\star}}$, and every point has the same
convergence rate. In particular, if $w^{\star}$ can be attained at some
$x^{\star}\in\mathcal{X}$, then the exact convergence speed for $x^{\star}$
equals $(1-\frac{1}{w^{\star}})^{n}$.

##  4 IMH on discrete state spaces

Let $\mathcal{X}=\\{1,2,\cdots,n\\}$ be a finite discrete sample space. Let
$\pi$ and $p$ be the target and proposal probability mass function (PMF),
respectively. Again, we define the ratio function $w\doteq\frac{\pi}{p}$ the
same as Section 3. Without loss of generality, we assume $w$ is non-
increasing, i.e.,

$w_{1}\geq w_{2}\cdots\geq w_{n}.$

In other words, $w^{\star}=w_{1}$, the supremum of function $w$ is attained at
the first state.

The IMH algorithm 2 has the following transition probability kernel:

$P(i,j)=\begin{cases}p_{j}\min\\{1,\frac{w_{j}}{w_{i}}\\}\qquad\text{if }j\neq
i\\\ p_{i}+\sum_{k}p_{k}\max\\{0,1-\frac{w_{k}}{w_{i}}\\}\qquad\text{if
}j=i\end{cases}$ (4.1)

It is tempting to believe that all the results in Section 3 still hold for
discrete state space. However, our next result shows, though the exact
convergence rate is still $(1-\frac{1}{w^{\star}})$, Theorem 3.2 does not
hold.

###  4.1 Exact convergence rate

###### Theorem 4.1

With all the notations as above, we have:

$(1-\pi_{1})(1-\frac{1}{w^{\star}})^{t}\leq
d_{\text{IMH}}(t)\leq(1-\frac{1}{w^{\star}})^{t}$ (4.2)

###### Remark 4

It is worth mentioning that the upper bound is shown by Liu Liu (96), page
117. But the lower bound is not contained in Liu (96).

###### Proof

The right part of inequality 4.2 is already proved in Theorem 3.2. For the
left part, by 4.1, we immediately have:

$P(1,\cdot)=(1-\frac{1}{w_{1}})\delta_{1}+\frac{1}{w_{1}}\pi.$

Therefore, using the fact $\pi P=\pi$, we have:

$P^{t}(1,\cdot)=(1-\frac{1}{w_{1}})^{t}\delta_{1}+(1-(1-\frac{1}{w_{1}})^{t})\pi.$

Then we have

$\displaystyle d_{\text{IMH}}(t)$
$\displaystyle=\max_{x\in\mathcal{X}}\|P^{t}(x,\cdot)-\pi\|_{\sf TV}$
$\displaystyle\geq\|P^{t}(1,\cdot)-\pi\|_{\sf TV}$
$\displaystyle\geq(1-\frac{1}{w_{1}})^{t}\|\delta_{1}-\pi\|_{\sf TV}$
$\displaystyle=(1-\pi_{1})(1-\frac{1}{w_{1}})^{t},$

which finishes the proof.

The following corollary is immediate:

###### Corollary 3

The convergence rate $r$ (defined in Definition 4) at $x=1$ equals
$1-\frac{1}{w_{1}}$.

###### Proof

Taking the logarithm on both sides of inequality 4.2 and the result follows.

Our next result shows inequality 4.2 is sharp in the sense that it cannot be
improved without further assumptions.

###### Proposition 1

There exist two Markov chains $\Phi_{1}$ and $\Phi_{2}$ such that
$d_{\text{IMH}}(\Phi_{1},t)=(1-\frac{1}{w_{1}})^{t}$ and
$d_{\text{IMH}}(\Phi_{2},t)=(1-\pi_{1})(1-\frac{1}{w_{1}})^{t}$

###### Proof

Let $\Phi_{1}$ be the Markov chain with target distribution uniform over
$\\{1,2,\cdots,K\\}$ and proposal distribution uniform over
$\\{1,2,\cdots,2K\\}$. In this case $w_{1}=w^{\star}=2$. Straightforward
calculation gives us:

$\displaystyle\|P^{t}(i,\cdot)-\pi\|_{\sf
TV}=(1-\frac{1}{K})0.5^{t}\qquad\text{for}~{}i~{}\text{in}~{}\\{1,\cdots,K\\}$
$\displaystyle\|P^{t}(j,\cdot)-\pi\|_{\sf
TV}=0.5^{t}\qquad\qquad~{}~{}~{}\text{for}~{}j~{}\text{in}~{}\\{K+1,\cdots,2K\\}$

Therefore, $d_{\text{IMH}}(\Phi_{1},t)=(1-\frac{1}{w_{1}})^{t}$.

Let $\Phi_{2}$ be a Markov chain on $\\{1,2,\cdots,K+1\\}$ with target
distribution:

$\pi(i)=\begin{cases}\frac{1}{2}\qquad\text{if}~{}~{}i=1\\\
\frac{1}{2K}~{}~{}~{}~{}~{}\text{if}~{}~{}i\neq 1,\end{cases}$

and proposal distribution

$q(i)=\begin{cases}\frac{1}{4}\qquad\text{if}~{}~{}i=1\\\
\frac{3}{4K}~{}~{}~{}~{}~{}\text{if}~{}~{}i\neq 1,\end{cases}$

Then it is clear that $w^{\star}=2$. Meanwhile,

$\displaystyle\|P^{t}(1,\cdot)-\pi\|_{\sf TV}=(1-\pi_{1})0.5^{t}=0.5^{t+1}$
(4.3) $\displaystyle\|P^{t}(j,\cdot)-\pi\|_{\sf TV}=0.5-P^{t}(j,1)=0.5^{t+1}.$
(4.4)

Therefore, $d_{\text{IMH}}(\Phi_{2},t)=(1-\pi_{1})(1-\frac{1}{w_{1}})^{t}$.

As we can see in Theorem 3.2, Theorem 4.1, and Proposition 1, the ‘maximal
total variation distance’ $d_{\text{IMH}}$ has different behavior between
general and discrete state spaces. For chains on general state spaces,
$d_{\text{IMH}}(t)=(1-\frac{1}{w_{1}})^{t}$ can be calculated out explicitly.
For chains on discrete state spaces, however, we can only bound
$d_{\text{IMH}}$ between $(1-\pi_{1})(1-\frac{1}{w_{1}})^{t}$ and
$(1-\frac{1}{w_{1}})^{t}$. An intuitive way of understanding this discrepancy
is: As we mentioned in Remark 1 and Theorem 4.1, for both discrete and
continuous state space, a common lower bound for $d_{\text{IMH}}(t)$ is

$(1-\pi(\\{x^{\star}\\}))(1-\frac{1}{w_{1}})^{t},$

and a common upper bound is

$(1-\frac{1}{w_{1}})^{t}.$

If $\mathcal{X}$ is a general state space, then any probability density on
$\mathcal{X}$ is atomless. Therefore we have $\pi(\\{x^{\star}\\})=0$ and the
lower bound matches the upper bound. However, for discrete state
$\mathcal{X}$, $\pi(\\{x^{\star}\\})=\pi_{1}$ not necessarily equals $0$,
therefore the lower bound does not match the upper bound.

In conclusion, in this part, we provide answer to our first question (Q1)
proposed in Section 1 for the IMH algorithm on general state spaces. We show
the exact convergence rate is still $1-\frac{1}{w^{\star}}$. However, unlike
the general state space case, the ‘exact convergence speed’ for the IMH
algorithm is not always $(1-\frac{1}{w^{\star}})^{t}$. We have
$(1-\pi_{1})(1-\frac{1}{w^{\star}})^{t}\leq
d_{\text{IMH}}(n)\leq(1-\frac{1}{w^{\star}})^{t}$ instead.

###  4.2 Convergence rate at every point

In this section, we focus on proving the following theorem, which shows the
convergence rate $r(x)$ equals $1-\frac{1}{w^{\star}}$ for every
$x\in\mathcal{X}$.

###### Theorem 4.2

Let $\Phi$ be an IMH chain on discrete finite state space
$\mathcal{X}=\\{1,\cdots,n\\}$. Then for every $x\in\mathcal{X}$:

$r(x)=r_{-}(x)=r^{+}(x)=1-\frac{1}{w^{\star}}.$ (4.6)

In other words, the convergence rate for every $x$ equals
$1-\frac{1}{w^{\star}}$.

To prove Theorem 4.2, we first review the following result from Liu Liu (96),
which gives all the eigenvalues and the corresponding eigenvectors of the
Markov transition kernel $P$ (defined in 4.1).

######  Theorem 4.3 (Theorem 2.1 of Liu Liu (96))

Let $\Phi$ be the IMH chain with transition kernel $P$ given by 4.1. Then all
the eigenvalues of the transion matrix are:

$\lambda_{0}=1>\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n-1}\geq 0,$
(4.7)

where

$\lambda_{k}=\sum_{i=k}^{n}(p_{i}-\frac{\pi_{i}}{w_{k}}).$

The right eigenvector corresponding to $\lambda_{k}$ ($k>0$) is

$v_{k}=(0,0,\cdots,0,S_{\pi}(k+1),-\pi_{k},\cdots,-\pi_{k})^{\intercal},$
(4.8)

where there are $k-1$ zero entries and
$S_{\pi}(j)=\pi_{j}+\pi_{j+1}+\cdots+\pi_{n}$ for every $j$. Moreover,
$\langle v_{i},v_{j}\rangle_{\pi}=0$ for $i\neq j$.

For self-containedness, we provide a short proof of Theorem 4.3, which is
slightly different from Liu’s original proof. We start with the following
lemma and then show that Theorem 4.3 can be viewed as a special case of this
lemma.

######  Lemma 3 (Rank-one perturbation)

Let $A$ be a $n\times n$ matrix with (not necessarily distinct) eigenvalues
$\lambda_{1},\cdots\lambda_{n}$. Let $u_{1},\cdots,u_{n}$ be the corresponding
(right) eigenvectors. Then for any $u\in\mathbb{R}^{n}$, all the eigenvalues
of the following matrix

$B=A+u_{n}u^{\intercal}$

are

$\lambda_{1},\lambda_{2},\cdots,\lambda_{n-1},\lambda_{n}+u^{\intercal}u_{n}.$

If $u^{\intercal}u_{n}\neq-\lambda_{n}$, then the corresponding eigenvectors
of $B$ can be written as:

$\tilde{u}_{j}=\begin{cases}u_{n}\qquad\qquad~{}~{}~{}~{}\text{if}~{}j=n\\\
u_{j}-\frac{\lambda_{j}-u^{\intercal}u_{j}}{\lambda_{n}+u^{\intercal}u_{n}}u_{n}~{}\text{if}~{}j\neq
n\end{cases}$

###### Proof

The proof is straightforward calculation so we omit it here.

###### Remark 5

When $u^{\intercal}v_{n}=-\lambda_{n}$, the eigenvectors of $B$ can still be
derived without too much effort. Since Lemma 3 is enough to include Theorem
4.3 as a special case, we do not cover any further extension here.

######  Proof (Proof of Theorem 4.3)

Notice that the transition kernel $P$ can be decomposed as the summation of an
upper-diagonal matrix and a rank-one matrix

$P=D+ep^{\intercal}$ (4.9)

where

$D=\begin{pmatrix}\lambda_{1}&\frac{\pi_{2}}{w_{1}}-p_{2}&\cdots&\frac{\pi_{n-1}}{w_{1}}-p_{n-1}&\frac{\pi_{n}}{w_{1}}-p_{n}\\\
0&\lambda_{2}&\cdots&\frac{\pi_{n-1}}{w_{2}}-p_{n-1}&\frac{\pi_{n}}{w_{2}}-p_{n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&\lambda_{n-1}&\frac{\pi_{n}}{w_{n-1}}-p_{n}\\\ 0&0&\cdots&0&0\\\
\end{pmatrix},$ $e=(1,1,\cdots,1)^{\intercal},$
$p=(p_{1},p_{2},\cdots,p_{n})^{\intercal}.$

Since $e$ is a common eigenvector of both $P$ and $ep^{\intercal}$ with
respect to eigenvalue $1$, it is an eigenvector of $D$ with respect to
eigenvalue $0$. We can apply Lemma 3 and the result follows immediately.

Now we are ready to prove Theorem 4.2.

######  Proof (Proof of Theorem 4.2)

Let $f_{k}$ be the normalized eigenfunction of $v_{k}$, that is:

$f_{k}=v_{k}/\langle v_{k},v_{k}\rangle_{\pi}.$

Then the spectral theorem of reversition transition matrix gives us (see Lemma
12.16 of Levin et al. LP (17) for a proof):

$\bigg{\lVert}\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\bigg{\rVert}_{2,\pi}^{2}=\sum_{k=1}^{m-1}f_{k}(x)^{2}\lambda_{k}^{2t}\geq
f_{1}(x)^{2}\lambda_{1}^{2t}$ (4.10)

Notice that $\lambda_{1}=1-\frac{1}{w_{1}}=1-\frac{1}{w^{\star}}$ and
$v_{1}=(1-\pi_{1},-\pi_{1},\cdots,-\pi_{1})$ does not have any zero entry. We
conclude

$\bigg{\lVert}\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\bigg{\rVert}_{2,\pi}\geq
c(\pi)(1-\frac{1}{w^{\star}})^{t}$ (4.11)

for every $x$, where $c(\pi)$ is a positive constant depending only on $\pi$.
Therefore, for every $x\in\mathcal{X}$, the $L_{2}$ convergence between
$P^{t}(x,\cdot)$ to $\pi$ equals $1-\frac{1}{w^{\star}}$ for every $x$.

Now it remains to prove the $L_{1}$ convergence rate also equals
$1-\frac{1}{w^{\star}}$ for every $x$. Notice that:

$\|P^{t}(x,\cdot)-\pi\|_{\sf
TV}=\frac{1}{2}\lVert\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\rVert_{1,\pi}=\frac{1}{2}\sum_{y\in\mathcal{X}}\bigg{\lvert}\frac{P^{t}(x,y)}{\pi(y)}-1\bigg{\rvert}\pi(y)\geq\frac{\pi_{\star}}{2}\max_{y}\bigg{\lvert}\frac{P^{t}(x,y)}{\pi(y)}-1\bigg{\rvert},$
(4.12)

where $\pi_{\star}\doteq\min_{y}\pi(y)$, and

$\bigg{\lVert}\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\bigg{\rVert}_{2,\pi}=\sqrt{\sum_{y\in\mathcal{X}}\bigg{(}\frac{P^{t}(x,y)}{\pi(y)}-1\bigg{)}^{2}\pi(y)}\leq\max_{y}\bigg{\lvert}\frac{P^{t}(x,y)}{\pi(y)}-1\bigg{\rvert}$
(4.13)

Combining 4.11, 4.12, and 4.13, we have:

$\|P^{t}(x,\cdot)-\pi\|_{\sf
TV}\geq\frac{\pi_{\star}}{2}\bigg{\lVert}\frac{P^{t}(x,\cdot)}{\pi(\cdot)}-1\bigg{\rVert}_{2,\pi}\geq\frac{\pi_{\star}c(\pi)}{2}(1-\frac{1}{w^{\star}})^{t}$
(4.14)

for any $x\in\mathcal{X}$.

Taking logarithm on both sides of 4.14 and we have

$r_{-}(x)\geq 1-\frac{1}{w^{\star}}.$

Since Theorem 4.1 gives us $r^{+}(x)\leq 1-\frac{1}{w^{\star}}$, we have
$r(x)=1-\frac{1}{w^{\star}}$, as desired.

Theorem 3.4 and Theorem 4.1 shows that, the IMH chain has the same convergence
rate for every initialization $x\in\mathcal{X}$, regardless of the sample
space is continuous or discrete. This answers Q2 in Section 1.

##  5 Connections with Random-walk Metropolis-Hastings algorithms

In this section, we discuss the connections between the convergence of IMH and
RWMH algorithms as well as some open problems. This section mainly focuses on
algorithms on general state spaces, though many results are still true for
discrete state space.

###  5.1 Geometric ergodicity of RWMH algorithms

In Section 3, Lemma 1, we have shown

$\|P^{n}(x,\cdot)-\pi\|_{\sf TV}\geq R^{n}(x)$

for the IMH algorithm. It is clear that the same result is true for the RWMN
algorithm. Therefore, we have the next corollary:

######  Corollary 4 (Also proved in Roberts and Tweedie RT (96), Theorem 5.1
and Proposition 5.1)

For any Metropolis-Hastings algorithm, if the supremum of rejection
probability is $1$. In other words,

$\text{esssup}_{x\in\mathcal{X}}R(x)=1.$ (5.1)

Then the algorithm is not geometrically ergodic.

Corollary 4 shows that the rejection probability is bounded away from $1$ is a
necessary condition for the geometric ergodicity. For the IMH algorithm,
however, this is not only the necessary but also the sufficient condition for
the geometric ergodicity. In Atchadé and Perron AP (07), it is shown that
Condition 5.1 is the necessary and sufficient condition for the geometric
ergodicity of the MH algorithm if the absolutely continuous part of the Markov
chain’s transition kernel is compact. They have also conjectured (see page 78
of AP (07)) that even without the compactness assumption, Condition 5.1 is
still the necessary and sufficient condition for the geometric ergodicity of
the MH algorithm.

Our next result disproves the conjecture of Atchadé and Perron by a
counterexample.

###### Theorem 5.1

There exists a RWMH chain $\Phi$ such that

$\text{esssup}_{x\in\mathcal{X}}R(x)<1$

but $\Phi$ is not geometrically ergodic.

###### Proof

Consider the RWMH algorithm with Cauchy distribution as target, i.e.,

$\pi(x)=\frac{1}{\pi(1+x^{2})},$

and proposal distribution $p(x,\cdot)\sim U[x-1,x+1]$. It is not hard to check
that

$\text{esssup}_{x\in\mathcal{X}}R(x)=R(0)=1-\frac{1}{2}\int_{-1}^{1}\frac{1}{1+s^{2}}ds=1-\frac{\pi}{2}<1.$

However, for any $x_{0}\in\mathbb{R}$, the support of $P^{n}(x_{0},\cdot)$ is
contained in $[x_{0}-n,x_{0}+n]$. Therefore,

$\displaystyle\|P^{n}(x_{0},\cdot)-\pi\|_{\sf TV}$
$\displaystyle\geq\pi((-\infty,x_{0}-n])+\pi([x_{0}+n,\infty))$
$\displaystyle\geq\int_{|x_{0}|+n}^{\infty}\frac{1}{\pi(1+x^{2})}dx$
$\displaystyle\geq\int_{|x_{0}|+n}^{\infty}\frac{1}{2\pi x^{2}}dx$
$\displaystyle=\frac{1}{2\pi(|x_{0}|+n)}$

Therefore $\|P^{n}(x_{0},\cdot)-\pi\|_{\sf TV}$ has order at least
$\frac{1}{n}$ for every $x_{0}\in\mathbb{R}$, which is of polynomial decay.
Thus $\Phi$ does not satisfy 1.1 and is therefore not geometrically ergodic.

Therefore, Condition 5.1 is necessary but not sufficient for the geometric
ergodicity of RWMH algorithms. In contrast, the sufficient conditions for the
geometric ergodicity of the RWMH algorithm usually require the target
distribution has a sufficiently light tail. We refer the readers to Mengerson
and Tweedie MT+ (96), and Roberts and Tweedie RT (96) for more related
results.

###  5.2 Convergence rate at every point of RWMH algorithms

It is shown by Theorem 3.4 and Theorem 4.1 that the convergence rate at every
point of the IMH algorithms is the same. However, this is not true for RWMH
algorithms. Our next example shows the RWMH algorithm may have different
convergence rates for different initializations.

###### Example 6

Consider a RWMH chain $\Phi$ with uniform target distribution $\pi=U[-1,1]$
and proposal distribution $U[x-\delta,x+\delta]$ for some constant
$1\leq\delta<2$. Let $T$ be the smallest integer such that
$\Phi_{T}\neq\Phi_{0}$. Suppose $\Phi_{0}\in[1-\delta,\delta-1]$, then it is
clear that $\Phi_{t}$ is distributed according to stationary distribution for
all $t\geq T$. Therefore, for any $x_{0}\in[1-\delta,\delta-1]$,

$\displaystyle\|P^{n}(x_{0},\cdot)-\pi\|_{\sf TV}$
$\displaystyle\leq\mathbb{P}(T>n)=(1-\delta^{-1})^{n}$

However, for any $y_{0}>\delta-1$ or $y<1-\delta$, we have

$\displaystyle\|P^{n}(y_{0},\cdot)-\pi\|_{\sf TV}\geq
R^{n}(y_{0})=\bigg{(}\frac{\delta-1+\lvert
y\rvert}{2\delta}\bigg{)}^{n}>(1-\delta^{-1})^{n}$

Therefore, different initializations have different convergence rates. In
particular, if one starts the chain at $0$, then the convergence rate is
$(1-\delta^{-1})$. However, if one starts the chain at $1$ or $-1$, then the
convergence rate is no less than $0.5$. Therefore, if users choose to start in
the range $[1-\delta,\delta-1]$, the algorithm will converge much faster than
starting at $[-1,1-\delta]$ or $[\delta-1,1]$.

Example 6 gives a special RWMH algorithm which has different convergence rates
on different initializations. Alas, little is known about the convergence rate
with different initializations, therefore we do not know if this phenomenon
exists for general RWMH algorithms. As we have explained in Section 1, we
believe this is worth studying and should be of both theorist and
practitioner’s interest.

In conclusion, almost all the previous results on MCMC convergence focus on
establishing the uniform upper bound on the convergence rate. Though helpful
for providing insights, these bounds are usually conservative and hard to use
in practice. Moreover, these results neglect the fact that different
initializations may have different convergence rates. In this paper, we give
the exact convergence rate for the convergence rate of the IMH algorithm, and
show that all the initializations have the same convergence rate on both
general and discrete state space. However, examples indicate that our results
can not be directly generalized to other Metropolis-Hastings algorithms such
as RWMH. This opens up a wide area of research and we hope the reader could
help take it further.

## References

  * AD [87] David Aldous and Persi Diaconis.  Strong uniform times and finite random walks.  Advances in Applied Mathematics, 8(1):69–97, 1987.
  * ADH [10] Christophe Andrieu, Arnaud Doucet, and Roman Holenstein.  Particle markov chain monte carlo methods.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(3):269–342, 2010.
  * AP [07] Yves F Atchadé and François Perron.  On the geometric ergodicity of metropolis-hastings algorithms.  Statistics, 41(1):77–84, 2007.
  * BD+ [92] Dave Bayer, Persi Diaconis, et al.  Trailing the dovetail shuffle to its lair.  The Annals of Applied Probability, 2(2):294–313, 1992.
  * Cip [00] Barry A Cipra.  The best of the 20th century: Editors name top 10 algorithms.  SIAM news, 33(4):1–2, 2000.
  * D+ [13] Persi Diaconis et al.  Some things we’ve learned (about markov chain monte carlo).  Bernoulli, 19(4):1294–1305, 2013.
  * Dia [09] Persi Diaconis.  The markov chain monte carlo revolution.  Bulletin of the American Mathematical Society, 46(2):179–205, 2009\.
  * [8] Persi Diaconis, Kshitij Khare, and Laurent Saloff-Coste.  Gibbs sampling, exponential families and orthogonal polynomials.  Statistical Science, 23(2):151–178, 2008.
  * [9] Persi Diaconis, Kshitij Khare, and Laurent Saloff-Coste.  Rejoinder: Gibbs sampling, exponential families and orthogonal polynomials.  Statist. Sci., 23(2):196–200, 05 2008.
  * DS [81] Persi Diaconis and Mehrdad Shahshahani.  Generating a random permutation with random transpositions.  Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159–179, 1981.
  * DSC [93] Persi Diaconis and Laurent Saloff-Coste.  Comparison theorems for reversible markov chains.  The Annals of Applied Probability, pages 696–730, 1993.
  * DSC+ [96] Persi Diaconis, Laurent Saloff-Coste, et al.  Logarithmic sobolev inequalities for finite markov chains.  The Annals of Applied Probability, 6(3):695–750, 1996.
  * GG [84] Stuart Geman and Donald Geman.  Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.  IEEE Transactions on pattern analysis and machine intelligence, (6):721–741, 1984.
  * GS [90] Alan E Gelfand and Adrian FM Smith.  Sampling-based approaches to calculating marginal densities.  Journal of the American statistical association, 85(410):398–409, 1990.
  * Has [70] W Keith Hastings.  Monte carlo sampling methods using markov chains and their applications.  1970\.
  * HHH+ [09] Lars Holden, Ragnar Hauge, Marit Holden, et al.  Adaptive independent metropolis–hastings.  The Annals of Applied Probability, 19(1):395–413, 2009.
  * JH [01] Galin L Jones and James P Hobert.  Honest exploration of intractable probability distributions via markov chain monte carlo.  Statistical Science, pages 312–334, 2001.
  * JJ [08] Galin L Jones and Alicia A Johnson.  Comment: Gibbs sampling, exponential families, and orthogonal polynomials.  Statistical science, 23(2):183–186, 2008.
  * Liu [96] Jun S Liu.  Metropolized independent sampling with comparisons to rejection sampling and importance sampling.  Statistics and computing, 6(2):113–119, 1996.
  * LP [17] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * MDDJ [19] Lawrence Middleton, George Deligiannidis, Arnaud Doucet, and Pierre E Jacob.  Unbiased smoothing using particle independent metropolis-hastings.  arXiv preprint arXiv:1902.01781, 2019.
  * MRR+ [53] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller.  Equation of state calculations by fast computing machines.  The journal of chemical physics, 21(6):1087–1092, 1953.
  * MT+ [96] Kerrie L Mengersen, Richard L Tweedie, et al.  Rates of convergence of the hastings and metropolis algorithms.  The annals of Statistics, 24(1):101–121, 1996.
  * MT [12] Sean P Meyn and Richard L Tweedie.  Markov chains and stochastic stability.  Springer Science & Business Media, 2012.
  * Ros [95] Jeffrey S Rosenthal.  Minorization conditions and convergence rates for markov chain monte carlo.  Journal of the American Statistical Association, 90(430):558–566, 1995.
  * RR [04] Gareth O Roberts and Jeffrey S Rosenthal.  General state space markov chains and mcmc algorithms.  Probability surveys, 1:20–71, 2004.
  * RR [11] Gareth O Roberts and Jeffrey S Rosenthal.  Quantitative non-geometric convergence bounds for independence samplers.  Methodology and Computing in Applied Probability, 13(2):391–403, 2011.
  * RT [96] Gareth O Roberts and Richard L Tweedie.  Geometric convergence and central limit theorems for multidimensional hastings and metropolis algorithms.  Biometrika, 83(1):95–110, 1996.
  * ST [96] Richard L Smith and Luke Tierney.  Exact transition probabilities for the independence metropolis sampler.  1996\.
  * Tie [94] Luke Tierney.  Markov chains for exploring posterior distributions.  the Annals of Statistics, pages 1701–1728, 1994.
  * Wan [20] Guanyang Wang.  On the theoretical properties of the exchange algorithm.  arXiv preprint arXiv:2005.09235, 2020.