# A calculus for Markov chain Monte Carlo:
studying approximations in algorithms

Rocco Caprio  Adam M Johansen

(Department of Statistics, University of Warwick
)

###### Abstract

Markov chain Monte Carlo (MCMC) algorithms are based on the construction of a
Markov Chain with transition probabilities $P_{\mu}(x,\cdot)$, where $\mu$
indicates an invariant distribution of interest. In this work, we look at
these transition probabilities as functions of their invariant distributions,
and we develop a notion of derivative in the invariant distribution of a MCMC
kernel. We build around this concept a set of tools that we refer to as Markov
Chain Monte Carlo Calculus. This allows us to compare Markov chains with
different invariant distributions within a suitable class via what we refer to
as mean value inequalities. We explain how MCMC Calculus provides a natural
framework to study algorithms using an approximation of an invariant
distribution, also illustrating how it suggests practical guidelines for MCMC
algorithms efficiency. We conclude this work by showing how the tools
developed can be applied to prove convergence of interacting and sequential
MCMC algorithms, which arise in the context of particle filtering.

##  1 Introduction

###  1.1 Notation

It it convenient to begin by introducing some notation that will be used
throughout. $(\Omega,\mathcal{F},\mathbb{P})$ is some underlying probability
space. $(\mathsf{X},\mathcal{B}(\mathsf{X}))$ is a Polish space equipped with
metric $\varrho$ for which we assume that $x\mapsto\varrho(x,y)$ is
continuously differentiable for all $y\neq x$, and endowed with the associated
Borel $\sigma$-field. $B(x,r)$ denotes a ball in $\mathsf{X}$ centered at $x$
and having radius $r>0$. We will slightly abuse notation and use $1$ to denote
the unit function on any space. $\mathcal{M}(\mathsf{X})$ denotes the set of
finite signed measures on $\mathsf{X}$.
$\mathcal{M}_{\lambda,0}(\mathsf{X})\subset\mathcal{M}(\mathsf{X})$ denotes
the set of $0$–mass signed measures with continuous bounded Radon-Nikodým
derivatives w.r.t. a reference $\sigma$-finite measure $\lambda$.
$\mathcal{P}(\mathsf{X})\subset\mathcal{M}(\mathsf{X})$ denotes the set of
probability measures on $\mathsf{X}$, and similarly
$\mathcal{P}_{\lambda}(\mathsf{X})\subset\mathcal{P}(\mathsf{X})$ denotes the
set of probability measures with continuous bounded densities w.r.t.
$\lambda$. $\Rightarrow$ denotes weak convergence. For
$\chi\in\mathcal{M}(\mathsf{X})$ and a measurable function $f$, we often write
$\chi(f)\mathrel{\mathop{\mathchar 58\relax}}=\int f(x)\chi(dx)$. When
$\chi\in\mathcal{M}_{\lambda}(\mathsf{X})$ for some $\lambda$ which is implied
by the context, we often abuse notation and just write $\chi(x)$ for the value
of $d\chi/d\lambda$ at $x\in\mathsf{X}$. For $V\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\rightarrow[1,\infty)$, we define the $V$-norm of a
measurable function $f\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\mapsto\mathbb{R}$ as

$\left|f\right|_{V}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{x\in\mathsf{X}}\frac{|f(x)|}{V(x)}.$

$\mathbf{B}_{V}(\mathsf{X})$ denotes the space of measurable functions with
$V$-norm lower or equal than 1; $\mathbf{B}_{1}(\mathsf{X})$ that of
measurable functions with supremum norm no greater than 1. The $V$-norm of a
signed measure $\chi\in\mathcal{M}(\mathsf{X})$ is instead defined by

$\mathinner{\\!\left\lVert\chi\right\rVert}_{V}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{f\in\mathbf{B}_{V}(\mathsf{X})}\left|\int fd\chi\right|.$

When $V=1$, the $V$-norm of a function and of a signed measure are just the
supremum norm $\left|\cdot\right|_{\infty}$ and the total variation norm
$\mathinner{\\!\left\lVert\cdot\right\rVert}_{\rm tv}$, respectively.
$\mathbf{C}^{1}_{V}(\mathsf{X})$ is the space of continuously differentiable
functions with $V$-norm lower or equal than 1. We endow
$\mathcal{P}(\mathsf{X})$ with the $\sigma$-algebra generated by
$\mathbf{B}_{1}(\mathsf{X})$.

A Markov kernel on $\mathsf{X}\times\mathcal{B}(\mathsf{X})$ is a function
$P\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\times\mathcal{B}(\mathsf{X})\mapsto[0,1]$ such that (i)
for each $A\in\mathcal{B}(\mathsf{X})$, $P(\cdot,A)$ is a non-negative
measurable function on $\mathsf{X}$ and (ii) for each $x\in\mathsf{X}$,
$P(x,\cdot)\in\mathcal{P}(\mathsf{X})$. $P$ acts on bounded measurable
functions via $P(x,f)\mathrel{\mathop{\mathchar
58\relax}}=Pf(x)\mathrel{\mathop{\mathchar 58\relax}}=\int f(y)P(x,dy)$, and
on probability measures via $\rho P(dx)\mathrel{\mathop{\mathchar
58\relax}}=P(\rho,dx)\mathrel{\mathop{\mathchar
58\relax}}=\int\rho(dy)P(y,dx)\in\mathcal{P}(\mathsf{X})$. Whenever a
probability measure $\mu$ on $\mathsf{X}$ satisfies $\mu(dx)=P(\mu,dx)$, we
say that $\mu$ is an invariant distribution for $P$. A Markov kernel having an
invariant distribution $\mu$ will be denoted $P_{\mu}$ whenever the emphasis
is important.

###  1.2 Markov chain Monte Carlo with approximations and calculus

Markov chain Monte Carlo (MCMC) algorithms are based on the construction of a
Markov Chain with transition probabilities $P_{\mu}(x,\cdot)$, where $\mu$
indicates an invariant density of interest one can evaluate pointwise (up to a
possibly unknown normalizing constant). It often happens, however, that $\mu$
is intractable, or just very hard to target directly. In these situations,
possible and popular remedies include simply using an approximation $\mu_{n}$
of $\mu$ and hence simulating a homogeneous Markov Chain with transitions
$P_{\mu_{n}}$ , or considering an evolving sequence
$\\{\mu_{n}\\}_{n\in\mathbb{N}}$ converging to $\mu$ in some sense, and
simulating an inhomogeneous Markov Chain $\\{P_{\mu_{n}}\\}_{n\in\mathbb{N}}$
perhaps in a tempering-like context. In these situations, one usually has
control over how good the approximation is, and it might be of interest to
ensure that the “approximate” chain $P_{\mu_{n}}$ moves similarly to the
“limiting” chain $P_{\mu}$, and perhaps to quantify how the “degree of
similarity” depends on the quality of our approximation.

Roughly speaking, the ultimate goal of this paper is to look at Markov kernels
as functions of their invariant distribution, and to be able to say that
$P_{\mu_{n}}$ and $P_{\mu}$ are similar whenever we can say both that $\mu$
and $\mu_{n}$ are similar and that the derivative in the invariant
distribution of $P_{\cdot}$ at $\mu$ towards $\mu_{n}$ is bounded. In this
paper, we shall make sense of this sentence, first by introducing a notion of
a family of Markov kernels, where one has a mapping from the invariant
distribution to the Markov kernel (Section 2.1), and then of derivative in the
invariant distribution and of boundedness thereof (Sections 2.2 and 2.3). We
shall then provide a “Fundamental theorem of MCMC Calculus” to compare Markov
chains with different invariant distribution within the same family. When
$\mu,\nu$ have positive densities, this result will allow us to easily derive
_mean-value_ type inequalities

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{\rho,t}dt$

when $\rho$ also has a positive density, and when $\rho=\delta_{x}$,

$\mathinner{\\!\left\lVert P_{\mu}(x,\cdot)-P_{\nu}(x,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{1,t,x}dt+|\mu(x)-\nu(x)|\int_{0}^{1}D_{2,t,x}dt,$

for Hastings type and Gibbs kernels, with explicit values for the “Lipschitz
constants” $\int_{0}^{1}D_{\rho,t}dt$, $\int_{0}^{1}D_{1,t,x}dt$ and
$\int_{0}^{1}D_{2,t,x}dt$ (Propositions 2.7 and 2.9).

When $\\{\mu_{n}\\}_{n\in\mathbb{N}}$ is a sequence of random measures and
which has limiting Gaussian fluctuations around $\mu$, in a sense we shall
make more precise later, we will see that provided the Markov kernel
$P_{\cdot}$ is differentiable in the invariant distribution, then
$P_{\mu_{n}}$ will have also have limiting Gaussian fluctuations around
$P_{\mu}$, with the magnitude of the fluctuations depending explicitly on its
derivative (Proposition 2.10). These results are immediately useful when one
is using an approximate Chain $P_{\mu_{n}}$ and wants it to move like
$P_{\mu}$: it suffices to pick a Markov kernel with finite Lipschitz constants
(which will mean that the kernel has a bounded derivative in the invariant
distribution) or to minimize fluctuations around $P_{\mu}$. In Section 3 we
use our calculus approach to study the efficiency of approximation based MCMC
algorithms like Sequential MCMC or Interacting MCMC in terms of their
asymptotic variance. Our approach allow for a very natural study of these,
allowing us to state conditions for convergence simply in terms of good enough
approximation quality, boundedness of the derivative, and enough uniformity of
ergodic constants along the approximation sequence, and we improve some
existent convergence results in some cases.

##  2 Markov Chain Monte Carlo Calculus

###  2.1 Families of Markov kernels

To compare Markov kernels with different invariant distributions, our main
tool will be the derivative in the invariant distribution of a Markov kernel,
which we introduce in the next section. This quantity will describe the
variation of the transition probabilities of a Markov Chain when $\mu$ is
perturbed. Certainly, there are many possible transition probabilities
associated with each invariant distribution, so to accomplish this we first
have to restrict the class of Markov kernels considered. We introduce the
notion of family of Markov kernels—which is a collection of Markov kernels
indexed by a convex subset of invariant distributions:

######  Definition 2.1 (Family of Markov kernels).

Let $\mathcal{I}$ be a convex subset of $\mathcal{P}(\mathsf{X})$. A family of
Markov kernels $\\{P_{\star}\\}$ is a set
$\\{P_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\times\mathcal{B}(\mathsf{X})\mapsto[0,1]|\mu\in\mathcal{I}\\}$,
where for all $\mu\in\mathcal{I}$ one has $\mu P_{\mu}=\mu$.

According to our definition, if for some $\mu,\nu\in\mathcal{P}(\mathsf{X})$,
$P_{\mu},P_{\nu}\in\\{P_{\star}\\}$, then defining the curve
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$, as the map
$t\in[0,1]\mapsto\mu_{t}\in\mathcal{P}(\mathsf{X})$, interpolating $\mu$ and
$\nu$, we have that $P_{\mu_{t}}\in\\{P_{\star}\\}$ for any $t\in[0,1]$.
$\mu_{t}$ and $P_{\mu_{t}}$ will play an important role. The following two
examples describe some Markov kernel families.

######  Example 2.1 (The Hastings family).

Let $\mu\in\mathcal{P}(\mathsf{X})$ be a probability measure dominated by some
measure $\lambda$ in that $\mu\ll\lambda$, and write $\mu(y)$ for
$d\mu/d\lambda(y)$. Typically, $\lambda$ will be the Lebesgue measure when
$\mathsf{X}=\mathbb{R}^{d}$ and the counting measure when
$\mathsf{X}=\mathbb{Z}$. Let $Q$ be a proposal Markov kernel such that
$Q(x,dy)=q(x,y)\lambda(dy)$ for all $x\in\mathsf{X}$ and let $g$ be a
balancing function satisfying $g(x)=xg(1/x)$, $g(x)\leq 1$. Consider the
Markov kernels of the form

$P_{\mu}(x,f)\mathrel{\mathop{\mathchar 58\relax}}=\int
f(y)Q(x,dy)g(r_{\mu}(x,y))+f(x)\left(1-\int Q(x,dy)g(r_{\mu}(x,y))\right)$ (1)

where

$r_{\mu}(x,y)\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\frac{\mu(y)q(y,x)}{\mu(x)q(x,y)}\quad&\text{if}\quad\mu(x)q(x,y)>0,\\\
1\quad&\text{if}\quad\mu(x)q(x,y)=0.\end{cases}$

These kernels have $\mu$ as invariant distribution and are indexed by the
convex set of all probability distributions $\mu$ with a density w.r.t.
$\lambda$ on $\mathsf{X}$, or any convex subset thereof. That is, they form
proper Markov families as per Definition 2.1. For generic $Q$ and $g$, we
refer to the Hastings family, as [24] introduced kernels of this general form.
When, for instance, $Q$ is a Gaussian Random Walk (RW) and $g(x)=\min(1,x)$
one obtain the RW Metropolis family [34] over the same set of invariant
distributions. If $Q$ is a particular Gaussian RW and $g(x)=x/(1+x)$, they
form the RW Barker family [7] etc. In general, our framework imposes no
requirement that $Q$ be fixed across the family as described in this simple
example and in general it can depend upon $\mu$.

######  Example 2.2 (The Gibbs family).

Suppose $\mu$ is the probability distribution of a random vector
$(U_{1},U_{2})$. Let $P_{1|2}$ and $P_{2|1}$ two Markov kernels on
$\mathsf{X}\times\mathcal{B}(\mathsf{X})$ representing the conditional
distributions of $U_{1}$ given $U_{2}$ and $U_{2}$ given $U_{1}$,
respectively. The Markov kernels on
$\mathsf{X}^{2}\times\mathcal{B}(\mathsf{X}^{2})$ given by

$P_{\mu}((x,x^{\prime}),f)\mathrel{\mathop{\mathchar 58\relax}}=\int
P_{1|2}(x^{\prime},dy)P_{2|1}(y,dy^{\prime})f(y,y^{\prime})$ (2)

are $\mu$-invariant. Kernels of the type (2) form a proper Markov family—the
(two-stage) deterministic scan Gibbs family.

We considered here the two-stage Gibbs family purely for ease for exposition
and simplicity of notation; corresponding results can be obtained for much
more general Gibbs samplers. Considering other Markov kernel families is
possible. For instance, if in Example 2.1 we also allow $Q$ to depend on the
gradient of $\mu$ as in the Metropolis-Adjusted Langevin Algorithm (MALA;
[39]), one could obtain the MALA family (over the probability distributions
with differentiable densities). If $P_{1|2}$, $P_{2|1}$ in Example 2.2 instead
of being conditional distributions are Markov kernels invariant for the same,
one could obtain a Metropolis-within-Gibbs family etc. It is also possible to
consider a Markov family that is using a given type of Markov kernel if the
invariant distribution belong to a certain set (e.g. MALA if the invariant
density is differentiable), and another Markov kernel otherwise (e.g. RW
Metropolis if it is not). For Hastings-type and Gibbs-type algorithms of
Examples 2.1 and 2.2 above, checking that they form a Markov family in the
sense of Definition 2.1 is easily done because the dependence on the invariant
distribution is somehow explicit. In principal one could define Markov
families in which the dependence of kernels on the invariant distribution is
not made so explicit, but checking Definition 2.1 would be harder.

###  2.2 The derivative in the invariant distribution

Let $\\{P_{\star}\\}$ be a Markov family indexed by the convex set of
probability measures admitting densities w.r.t. some $\sigma$-finite measure
$\lambda$, or any convex subset thereof. We will define the derivative with
respect the invariant distribution of $P_{\cdot}$ at a point $\mu$ indexed by
the family by first accurately defining the derivative of the functional
$P_{\cdot}(\rho,f)\mathrel{\mathop{\mathchar
58\relax}}\mu\in\mathcal{P}(\mathsf{X})\mapsto P_{\mu}(\rho,f)\in\mathbb{R}$,
for all $(\rho,f)$ in some suitable class. The derivative of such functional
will first be defined for all $\rho$ in a subset of
$\mathcal{P}_{\lambda}(\mathsf{X})$, and then defined for initial
distributions in its completion by extension.

Throughout this section, we fix a continuously differentiable function
$V\mathrel{\mathop{\mathchar 58\relax}}\mathsf{X}\mapsto[1,\infty)$, and
consider $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$. This function directly
influences how stringent the differentiability statement is, but also what we
are able to say with the objects we introduce next, and its role will become
clear when we introduce mean value inequalities later.

######  Definition 2.2.

For $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$, the derivative of
$P_{\cdot}(\rho,f)$ in the invariant distribution at
$\mu\in\mathcal{P}_{\lambda}(\mathsf{X})$ is the linear functional
$\partial_{\pi}P_{\mu}(\rho,f)[\cdot]\mathrel{\mathop{\mathchar
58\relax}}\mathcal{M}_{\lambda,0}(\mathsf{X})\mapsto\mathbb{R}$ such that for
all $\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$,

$\frac{d}{dt}P_{\mu+t(\nu-\mu)}(\rho,f)\biggr{|}_{t=0}=\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$
(3)

We denote with $\mathcal{D}_{\mu,\lambda}(P,f)$ the set of
$\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ for which $P_{\cdot}(\rho,f)$ is
differentiable at $\mu$. In all our examples, for
$\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$, the action of the functional
$\partial_{\pi}P_{\mu}(\rho,f)$ will be expressible in integral form. In
particular, for a measurable function abusively denoted as
$\partial_{\pi}P_{\mu}(\rho,f)(\cdot)\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\mapsto\mathbb{R}$ we will have

$\displaystyle\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]=\int(\nu(y)-\mu(y))\partial_{\pi}P_{\mu}(\rho,f)(y)\lambda(dy)\quad\text{and}$
(4) $\displaystyle\mu(\partial_{\pi}P_{\mu}(\rho,f)(\cdot))=0.$ (5)

We sometimes distinguish the functional $\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$
from the function of its integral representation only via the brackets that
follow. The context will always make obvious to which object we are referring
to. The function $\partial_{\pi}P_{\mu}(\rho,f)(\cdot)$ will be referred to as
density of the derivative in the invariant distribution. The density of
$\partial_{\pi}P_{\mu}(\rho,f)$ corresponds to the _first variation_ of
$P_{\cdot}(\rho,f)$, and its analogues appears for instance in [12] in the
context of Mean Field Games and in Optimal Transport in [40]. Under some
conditions on $\mathsf{X}$ and $\mathcal{P}(\mathsf{X})$, these can be related
to notions of derivatives in the Wasserstein geometry [2], see also Theorem
2.2. Here, (5) is a centering condition, and it guarantees that the integral
representation is unique. Without, it would be unique only up to constants.
We defined the derivative in general as a linear functional
$\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$ despite in practice it admits an
integral representation for $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ because
this allows us an immediate extension to general
$\rho\in\mathcal{P}(\mathsf{X})$ for which such representation will not in
general be available. Let $d_{p}$ be a distance function metrizing the weak
topology on $\mathcal{P}(\mathsf{X})$. $d_{p}$ could be the Lévy-Prokhorov or
the Bounded Lipschitz metric [17, Chapter 11]. If the functional
$\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ is uniformly continuous
w.r.t. $d_{p}$ on some subset $\mathcal{A}$ of
$\mathcal{D}_{\mu,\lambda}(P,f)$, we can uniquely extend
$\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ on the weak completion
$\tilde{\mathcal{A}}$ of $\mathcal{A}$ in a very natural way via continuity.

######  Proposition 2.1.

If $\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ is uniformly continuous
w.r.t. $d_{p}$ on some subset $\mathcal{A}$ of
$\mathcal{P}_{\lambda}(\mathsf{X})$, we can uniquely extend it on its weak
completion $\tilde{\mathcal{A}}$ by defining

$\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]\mathrel{\mathop{\mathchar
58\relax}}=\lim_{j\rightarrow\infty}\partial_{\pi}P_{\mu}(\rho_{j},f)[\nu-\mu],\quad\text{
where
}\\{\rho_{j}\\}_{j\in\mathbb{N}}\in\mathcal{A}\Rightarrow\rho\in\tilde{\mathcal{A}}\setminus\mathcal{A}.$

Furthermore, the extension is uniformly continuous w.r.t. $d_{p}$ on
$\tilde{\mathcal{A}}$.

###### Proof.

See e.g. [28, Theorem 52]. ∎

We use this proposition to define the derivative of $P_{\cdot}(\rho,f)$ for
initial distributions that are not in $\mathcal{P}_{\lambda}(\mathsf{X})$, but
on which we have sufficient regularity to allow an extension. Let
$\tilde{\mathcal{A}}$ be the weak completion of a subset $\mathcal{A}$ of
$\mathcal{D}_{\mu,\lambda}(P,f)$ for which
$\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ is uniformly continuous
w.r.t. $d_{p}$ for all $\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$.

######  Definition 2.3.

For $\rho\in\tilde{\mathcal{A}}\setminus\mathcal{A}$, the derivative of
$P_{\cdot}(\rho,f)$ in the invariant distribution at $\mu$ is the linear
functional $\partial_{\pi}P_{\mu}(\rho,f)[\cdot]\mathrel{\mathop{\mathchar
58\relax}}\mathcal{M}_{\lambda,0}(\mathsf{X})\mapsto\mathbb{R}$ defined by

$\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]\mathrel{\mathop{\mathchar
58\relax}}=\lim_{j\rightarrow\infty}\partial_{\pi}P_{\mu}(\rho_{j},f)[\nu-\mu],\quad\text{where
}\\{\rho_{j}\\}_{j\in\mathbb{N}}\in\mathcal{A}\Rightarrow\rho\in\tilde{\mathcal{A}}\setminus\mathcal{A}.$
(6)

for all $\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$, where
$\partial_{\pi}P_{\mu}(\rho_{j},f)$ is the derivative in the invariant
distribution of $P_{\cdot}(\rho_{j},f)$ as per Definition 2.2.

The case we are mostly interested is defining
$\partial_{\pi}P_{\mu}(\delta_{x},f)=\mathrel{\mathop{\mathchar
58\relax}}\partial_{\pi}P_{\mu}(x,f)$, the derivative of $P_{\cdot}(x,f)$ in
the invariant distribution at $\mu$. The results above supply its definition
and its uniqueness whenever $\delta_{x}$ is in the weak completion of a subset
of $\mathcal{P}_{\lambda}(\mathsf{X})$ where
$\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)$ is uniformly continuous. We denote
with $\mathcal{D}_{\mu}(P,f)$ the set of initial distributions $\rho$ for
which $P_{\cdot}(\rho,f)$ is differentiable at $\mu$. This comprise all
initial distributions for which we may also obtain a definition by extension,
and it has $\mathcal{D}_{\mu,\lambda}(P,f)$ as subset. It might happen that
$\rho$ is in the weak completion of two different sets $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ on which the derivative is uniformly continuous. In
this case the definition of $\partial_{\pi}P_{\mu}(\rho,f)$ can be defined by
either the limit of
$\lim_{j\rightarrow\infty}\partial_{\pi}P_{\mu}(\rho_{j},$) with $\rho_{j}$ in
$\mathcal{A}$ or the limit
$\lim_{j\rightarrow\infty}\partial_{\pi}P_{\mu}(\rho_{j}^{\prime},$) with
$\rho^{\prime}_{j}$ in $\mathcal{A}^{\prime}$. We have not sought to establish
that these limits coincide, but that is no cause of concern for our purposes.
Any such derivative will satisfy the properties and equations we investigate
next.

We can now leverage these quantities to define the derivative of transition
probabilities.

######  Definition 2.4.

The derivative of $P_{\cdot}(\rho,\cdot)$ in the invariant distribution at
$\mu$ is the operator
$\partial_{\pi}P_{\mu}(\rho,\cdot)[\cdot]\mathrel{\mathop{\mathchar
58\relax}}f\in\mathbf{C}^{1}_{V}(\mathsf{X})\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$,
where $\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$ is defined in Definitions 2.2 and
2.3.

The differentiability of $P_{\cdot}(\rho,\cdot)$ amounts to ask that
$P_{\cdot}(\rho,f)$ is differentiabile in the sense of Definitions 2.2 and 2.3
for all $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$. Hence,
$\mathcal{D}_{\mu}(P)=\bigcap_{f\in\mathbf{C}^{1}_{V}(\mathsf{X})}\mathcal{D}_{\mu}(P,f)$.
We are now in a position to naturally define the derivative of a Markov kernel
itself.

######  Definition 2.5.

The derivative of $P_{\cdot}$ in the invariant distribution at $\mu$ is the
operator $\partial_{\pi}P_{\mu}(\cdot,\cdot)[\cdot]\mathrel{\mathop{\mathchar
58\relax}}(\rho,f)\in\mathcal{D}_{\mu}(P)\times\mathbf{C}^{1}_{V}(\mathsf{X})\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$,
where $\partial_{\pi}P_{\mu}(\rho,f)[\cdot]$ is defined in Definitions 2.2 and
2.3.

We will sometimes refer to the differential and the derivative in the
invariant measure of a Markov Kernel simply as “kernel differentials” and
“kernel derivative”, respectively. Since that is defined indirectly for each
point $(\rho,f)\in\mathcal{D}_{\mu}(P)\times\mathbf{C}^{1}_{V}(\mathsf{X})$,
we sometimes also refer to $\partial_{\pi}P_{\mu}(\rho,f)$ as a kernel
derivative.

Let us come to the interpretation of these derivatives and differentials at
$\mu$: they provide a map from the initial distribution to signed integral
operators which capture the variation of the transitions associated with
Markov kernels within a particularly family with small perturbations of the
associated invariant measure, $\mu$. In other words, the derivative in the
invariant measure quantifies how much the conditional expectation
$P_{\mu}(\rho,\cdot)$ changes when the invariant distribution $\mu$ is
perturbed by the $0$-mass measure $\chi=\nu-\mu$ or—alternatively—since
$\mu+t\chi=(1-t)\mu+t\nu$, when $\mu$ is contaminated infinitesimally by any
$\nu$. In a spatial perspective, it quantifies the variation in mean
displacement of a particle in Markovian motion $P_{\mu}$ initially distributed
as $\rho$ when $\mu$ is perturbed by $\nu$. The density of the kernel
derivative $\partial_{\pi}P_{\mu}(\rho,f)(y)$—when it exists—can be
heuristically interpreted as the change in the transition probabilities when
$\mu$ is contaminated infinitesimally by a point mass $\delta_{y}$ for all
$y\in\mathsf{X}$. In fact, using (3)-(5) we informally see that

$\partial_{\pi}P_{\mu}(\rho,f)(y)=\partial_{\pi}P_{\mu}(\rho,f)[\delta_{y}-\mu]=\int\partial_{\pi}P_{\mu}(\rho,f)(y^{\prime})d(\delta_{y}-\mu)(y^{\prime})=\frac{d}{dt}P_{\mu+t(\delta_{y}-\mu)}(\rho,f)\bigg{|}_{t=0}.$

This is similar to the role played by Influence functions in robust
statistics, which describe variations in estimators when the data distribution
is contaminated - see [26].

In the remainder of this section we develop some basic properties to build up
our intuition and understanding of kernel derivatives. In the end of the
section we investigate the differentiability of Hastings and Gibbs families.
The next proposition supplies a recursive formula for the derivative of
iterated kernels. These recursions are really expression of the
Chapman–Kolmogorov equations. Consider the conventions
$P^{0}_{\mu}(\cdot,f)\mathrel{\mathop{\mathchar 58\relax}}=f$ and
$P^{0}_{\mu}(\rho,\cdot)\mathrel{\mathop{\mathchar 58\relax}}=\rho$.

######  Proposition 2.2.

Let $k\in\mathbb{N}$ and assume that
$P^{j}_{\mu}(\rho,\cdot)\in\mathcal{D}_{\mu,\lambda}(P,f)$ and that
$P^{j}_{\mu}(\cdot,f)\in\mathbf{C}^{1}_{V}(\mathsf{X})$ for all $j\leq k$. For
all $k\in\mathbb{N}$ the derivative in the invariant distribution of an
iterated Markov kernel satisfy the formulæ

$\partial_{\pi}P_{\mu}^{k}(\rho,f)=\sum_{j=0}^{k-1}\partial_{\pi}P_{\mu}(P^{k-j-1}_{\mu}(\rho,\cdot),P^{j}_{\mu}(\cdot,f)).$

provided one can differentiate inside the integral
$P^{k}_{\mu+t(\nu-\mu)}(\rho,f)$ at $t=0$.

###### Proof.

Let $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ and
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$, we have

$\displaystyle\frac{d}{dt}P^{k}_{\mu+t(\nu-\mu)}(\rho,f)\bigg{|}_{t=0}$
$\displaystyle=\frac{d}{dt}\int
P_{\mu+t(\nu-\mu)}(\rho,dz)P^{k-1}_{\mu_{t}}(z,f)\bigg{|}_{t=0}$
$\displaystyle=\frac{d}{dt}P_{\mu+t(\nu-\mu)}(\rho,P^{k-1}_{\mu}(\cdot,f))\bigg{|}_{t=0}+\frac{d}{dt}P_{\mu+t(\nu-\mu)}^{k-1}(P_{\mu}(\rho,\cdot),f)\bigg{|}_{t=0}$
$\displaystyle=\partial_{\pi}P_{\mu}(\rho,P^{k-1}_{\mu}(\cdot,f))[\nu-\mu]+\partial_{\pi}P_{\mu}^{k-1}(P_{\mu}(\rho,\cdot),f)[\nu-\mu]$

therefore, exploiting this recursion yields,

$\displaystyle\partial_{\pi}P_{\mu}^{k}(\rho,f)$
$\displaystyle=\partial_{\pi}P_{\mu}(\rho,P^{k-1}_{\mu}(\cdot,f))+\partial_{\pi}P_{\mu}^{k-1}(P_{\mu}(\rho,\cdot),f)=\sum_{j=0}^{k-1}\partial_{\pi}P_{\mu}(P^{k-j-1}_{\mu}(\rho,\cdot),P^{j}_{\mu}(\cdot,f)).$

∎

Ergodicity can give us some information on how the derivative of iterated
kernels behave when $k\rightarrow\infty$. A kernel derivative quantifies
variations in transition probabilities $P^{k}_{\mu}(\rho,f)$ when the
invariant changes is perturbed infinitesimally by
$\chi\mathrel{\mathop{\mathchar 58\relax}}=\nu-\mu$. Under ergodicity for
large $k$ we will have $P^{k}_{\mu}(\rho,f)\approx\mu(f)$, hence, intuitively,
in the limit the kernel derivative ought to be $\chi(f)$. Define

$\mathcal{N}(\mu,\nu)\mathrel{\mathop{\mathchar
58\relax}}=\\{\mu_{t}\in\mathcal{P}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}\mu_{t}=(1-t)\mu+t\nu,t\in[0,1]\\}.$

This set is known as contamination neighbourhood in robust statistics [26],
although it is not a neighbourhood in the sense of the total variation or the
weak topology. For some starting distribution $\rho$, say that a Markov kernel
is ergodic uniformly in $\mathcal{N}(\mu,\nu)$ if
$\sup_{t\in[0,1]}|P^{k}_{\mu_{t}}(\rho,f)-\mu_{t}(f)|\rightarrow 0$ as
$k\to\infty$. We note that this is a definition of ergodicity uniform over a
collection of invariant distributions and is quite distinct from the notion of
uniform ergodicity of an individual Markov kernel.

######  Proposition 2.3.

For all starting distributions $\rho\in\mathcal{D}_{\mu,\lambda}(P,f)$ for
which the Markov kernel $P$ is ergodic uniformly in $\mathcal{N}(\mu,\nu)$,

$\lim_{k\rightarrow\infty}\partial_{\pi}P_{\mu}^{k}(\rho,f)[\nu-\mu]=[\nu-\mu](f).$

###### Proof.

We compute directly

$\displaystyle\lim_{k\rightarrow\infty}\partial_{\pi}P_{\mu}^{k}(\rho,f)[\nu-\mu]$
$\displaystyle=\lim_{k\rightarrow\infty}\lim_{t\rightarrow
0}\frac{P^{k}_{\mu+t(\nu-\mu)}(\rho,f)-P_{\mu}^{k}(\rho,f)}{t}$
$\displaystyle=\lim_{t\rightarrow
0}\lim_{k\rightarrow\infty}\frac{P^{k}_{\mu+t(\nu-\mu)}(\rho,f)-P_{\mu}^{k}(\rho,f)}{t}$
$\displaystyle=\lim_{t\rightarrow
0}\frac{(\mu+t(\nu-\mu))(f)-\mu(f)}{t}=[\nu-\mu](f),$

where the limit exchange if justified by the uniformity across the
neighbourhood. ∎

Hence, informally, its density in the limit is given by
$\lim_{k}\partial_{\pi}P_{\mu}^{k}(\rho,f)(y)=f(y)-\mu(f)$. It is interesting
to point out another connection between derivatives in the invariant
distributions and ergodicity. $\partial_{\pi}P_{\mu}(\mu,f)$ is understood as
the infinitesimal variation of the transition probability $P_{\mu}(X,f)$ when
the invariant measure is perturbed with a 0–mass measure, the starting point
$X$ follows the (non-perturbed) original distribution $\mu$. The density of
the derivative takes a very natural expression in this case that does not
require further computations. Denote $\mu_{t}\mathrel{\mathop{\mathchar
58\relax}}=(1-t)\mu+t\nu$. Write

$P_{\mu_{t}}(\mu_{t},f)=\mu_{t}(f).$

Differentiating this expression w.r.t. $t$ in $t=0$ one obtains, provided
$\frac{d}{dt}P_{\mu_{t}}(\mu,f)$ exists at $t=0$,

$\frac{d}{dt}P_{\mu_{t}}(\mu,f)\Bigg{|}_{t=0}+P_{\mu_{t}}(\chi,f)\Bigg{|}_{t=0}+t\frac{d}{dt}P_{\mu_{t}}(\chi,f)\Bigg{|}_{t=0}=\chi(f)$

Therefore, $\frac{d}{dt}P_{\mu_{t}}(\mu,f)\big{|}_{t=0}=\chi(f-P_{\mu}f)$,
which via (3) and (5) imply

$\partial_{\pi}P_{\mu}(\mu,f)(y)=f(y)-P_{\mu}(y,f).$ (7)

This relationship can also be heuristically proved using our interpretation of
derivative in the invariant measure at a point $y$ as the variation in
conditional expectation caused by a point mass $\delta_{y}$. We have then, up
to constants,

$\partial_{\pi}P_{\mu}(\mu,f)(y)=\lim_{t\rightarrow
0}\frac{P_{\mu+t(\delta_{y}-\mu)}(\mu,f)-\mu(f)}{t},$

but $P_{\mu_{t}}(\mu,f)=\mu_{t}-tP_{\mu_{t}}(y,f)+tP_{\mu_{t}}(\mu,f)$ so that
$P_{\mu_{t}}(\mu,f)=(\mu_{t}-tP_{\mu_{t}}(y,f))/(1-t)$. Hence, the right hand
side of the expression above becomes

$\displaystyle\lim_{t\rightarrow
0}\frac{\mu_{t}(f)-tP_{\mu_{t}}(y,f)-(1-t)\mu(f)}{(1-t)t}=\lim_{t\rightarrow
0}\frac{f(y)-P_{\mu}f(y)}{1-t}=f(y)-P_{\mu}(y,f).$

This points out to an interesting connection with discrete-time generators and
Foster-Lyapunov type arguments. One way to exploit this identity is simply by
restating classical Markov Chains regularity conditions, very often expressed
and verified in terms of drifts. The result below is a (partial) restatement
of [35, Theorem 13.0.1].

######  Theorem 2.1 (Ergodic Theorem with kernel derivatives).

Suppose that $\\{X_{n}\\}_{n\in\mathbb{N}}$ is an aperiodic, $\mu$-irreducible
Markov Chain with transition probabilities $P_{\mu}$ and invariant
distribution $\mu$. If there exists some petite set $C$, some $b<\infty$ and a
non-negative finite function $f$ bounded on $C$ such that

$-\partial_{\pi}P_{\mu}(\mu,f)(x)\leq-1+b1_{C}(x),\quad x\in\mathsf{X}$

whenever such kernel derivative exists, then for all $x\in\mathsf{X}$, as
$k\rightarrow\infty$,

$\mathinner{\\!\left\lVert P_{\mu}^{k}(x,\cdot)-\mu\right\rVert}_{\rm
tv}\rightarrow 0.$

Many other regularity conditions can be expressed in terms of drift
conditions, and therefore in terms of $\partial_{\pi}P_{\mu}(\mu,f)$. The main
applications of kernel derivatives in this work will be however in the context
of comparing Markov chains with different invariant distributions within the
same family, and in particular in what we will refer to as mean value
inequalities. First, for illustration, we compute the derivative in the
invariant distribution for Markov kernels in the Hastings and Gibbs families
of Examples 2.1 and 2.2 for $V=1$. The next example also illustrates why we
defined $\partial_{\pi}P_{\mu}(x,\cdot)$ only as a weak limit.

######  Example 2.3 (Derivatives of Hastings kernels).

Consider the Hastings family of Example 2.1 with $x\mapsto g(x)$ is twice
differentiable, with $g^{\prime}$ and $g^{\prime\prime}$ bounded. This class
of kernel includes, for instance, the Barker form of the acceptance
probability ($g(x)=x/(1+x)$), but not the Metropolis-Hastings form
($g(x)=\min(1,x)$). Further consider the following assumption which we discuss
after.

  1. H1

The indexed invariant distributions have upper bounded continuously
differentiable positive densities. The proposal has an upper bounded
continuously differentiable positive densities in both arguments. For all
$x\in\mathsf{X}$ there exist an $r>0$ and $L^{1}(\lambda)$ functions
$\psi_{1},\psi_{2}$ such that

$\sup_{z\in
B(x,r)}|\partial_{z}(q(z,y)g^{\prime}(r_{\mu}(z,y)))|\leq\psi_{1}(y)\textrm{
and }\sup_{z\in
B(x,r)}|\partial_{z}(q(y,z)g^{\prime}(r_{\mu}(z,y)))|\leq\psi_{2}(y).$

Let $\mathcal{W}_{H}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}d\rho/d\mu^{2}\text{ is bounded for all indexed $\mu$}\\}$.

######  Proposition 2.4.

The Hastings kernel $P_{\cdot}(\rho,\cdot)$ is differentiable in the invariant
distribution at $\mu$ for all $\rho\in\mathcal{W}_{H}$ provided only the
proposal is upper bounded. In this case, the derivative
$\partial_{\pi}P_{\mu}(\rho,\cdot)$ admits an integral representation, with
its density given for all $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$ by

$\displaystyle\partial_{\pi}P_{\mu}(\rho,f)(y)=\int(f(y)-f(z))q(y,z)$
$\displaystyle\frac{\rho(z)}{\mu(z)}g^{\prime}(r_{\mu}(z,y))\lambda(dz)$
$\displaystyle-\frac{\rho(y)}{\mu(y)^{2}}\int(f(z)-f(y))q(z,y)g^{\prime}(r_{\mu}(y,z))\mu(z)\lambda(dz).$
(8)

Furthermore, if Assumption H1 holds, $P_{\cdot}(\rho,\cdot)$ is differentiable
at $\mu$ for all $\rho$ in the weak completion of the set
$\mathcal{A}_{x}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}\mathrm{supp}(\rho)\subseteq B(x,r)\\}$. In particular,
$P_{\cdot}(x,\cdot)$ is also differentiable for all $x\in\mathsf{X}$. In this
case, $\partial_{\pi}P_{\mu}(x,\cdot)$ is given for all
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$ and
$\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$ by

$\displaystyle\partial_{\pi}P_{\mu}(x,f)[\nu-\mu]=\int(f(y)-f(x))$
$\displaystyle\frac{g^{\prime}(r_{\mu}(x,y))q(y,x)}{\mu(x)}(\nu-\mu)(y)\lambda(dy)$
$\displaystyle-\frac{(\nu-\mu)(x)}{\mu(x)^{2}}\int(f(y)-f(x))q(y,x)g^{\prime}(r_{\mu}(x,y))\mu(y)\lambda(dy).$
(9)

###### Proof.

If we can interchange differentiation and integration, one has, with
$\chi\mathrel{\mathop{\mathchar 58\relax}}=\nu-\mu$,

$\displaystyle\frac{d}{dt}P_{\mu+t(\nu-\mu)}(\rho,f)\bigg{|}_{t=0}$
$\displaystyle=\int\int\rho(du)f(w)Q(u,dw)g^{\prime}(r_{\mu}(u,w))\frac{d}{dt}r_{\mu_{t}}(u,w)\bigg{|}_{t=0}$
$\displaystyle+\int\rho(du)f(u)\left(1-\int
Q(u,dw)g^{\prime}(r_{\mu}(u,w)\frac{d}{dt}r_{\mu_{t}}(u,w)\bigg{|}_{t=0}\right)$
$\displaystyle=\int\int(f(w)-f(u))\frac{q(w,u)g^{\prime}(r_{\mu}(u,w))}{\mu(u)}\rho(u)\chi(w)\lambda(du)\lambda(dw)$
$\displaystyle-\int\int(f(w)-f(u))\frac{q(w,u)g^{\prime}(r_{\mu}(u,w))}{\mu(u)^{2}}\mu(w)\rho(u)\chi(u)\lambda(du)\lambda(dw)$
$\displaystyle=\int\left[\int(f(w)-f(u))\frac{q(w,u)g^{\prime}(r_{\mu}(u,w))}{\mu(u)}\rho(u)\lambda(du)\right]\chi(dw)$
$\displaystyle-\int\left[\int(f(w)-f(u))\frac{q(w,u)g^{\prime}(r_{\mu}(u,w))\mu(w)}{\mu(u)^{2}}\lambda(dw)\right]\rho(u)\chi(du).$

Hence, using the expressions above and (3) one identifies (2.4). Integrating
the latter w.r.t. $\mu$ shows that (5) is also satisfied. Section A.2 shows
that the the limit exchange performed is justified under our assumptions. Now
consider $\mathcal{A}_{x}$. In Section A.2 we show that
$\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ is uniformly continuous on
$\mathcal{A}_{x}$ for all $\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$. We can
then apply Proposition 2.1 to prove the differentiability of
$P_{\cdot}(\rho,\cdot)$ for all $\rho\in\tilde{\mathcal{A}}_{x}$. Since
clearly $\delta_{x}\in\tilde{\mathcal{A}}_{x}$, this also proves the
differentiability of $P_{\cdot}(x,\cdot)$ and the expression (2.4) follows
from the direct computation
$\partial_{\pi}P_{\mu}(x,f)[\nu-\mu]=\lim_{j}\partial_{\pi}P_{\mu}(\rho_{j,x},f)[\nu-\mu]$
for all $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$, where
$\rho_{j,x}\Rightarrow\delta_{x}$. ∎

Let us notice that the operator $\partial_{\pi}P_{\mu}(x,f)$ has no integral
representation. The boundedness of $\rho/\mu^{2}$ is a warm-start type
condition. If $\rho$ has lighter tails than $\mu^{2}$, it will hold. In
particular, if $\rho$ is compactly supported, $P_{\cdot}(\rho,\cdot)$ is
differentiable at all $\mu$. On the other hand, if $\rho$ is heavy tailed,
$P_{\cdot}(\rho,\cdot)$ will seldom be differentiable. The assumptions in
Assumption H1 are rather weak and often verified in practice. The requirement
that $|\partial_{z}(q(y,z)g^{\prime}(r_{\mu}(z,y)))|$ is uniformly bounded by
a $L^{1}(\lambda)$ function on $z\in B(x,r)$ is a requirement on the
regularity of the proposal and the balancing function around the point
$x\in\mathsf{X}$ where we want to show $P_{\cdot}(x,\cdot)$ is differentiable
at $\mu$, and it is very often satisfied. For instance, for the Gaussian
Random Walk we have

$\displaystyle|\partial_{z}(q(y,z)g^{\prime}(r_{\mu}(z,y)))|$
$\displaystyle\propto|y-z|q(y,z)g^{\prime}(r_{\mu}(z,y))+q(y,z)g^{\prime\prime}(r_{\mu}(z,y))\mu(y)\partial_{z}\mu(z)/\mu(z)^{2}$
$\displaystyle\leq
q(y,z)(|y|g^{\prime}(r_{\mu}(z,y))+|z|g^{\prime}(r_{\mu}(z,y))+g^{\prime\prime}(r_{\mu}(z,y))\mu(y)\partial_{z}\mu(z)/\mu(z)^{2})$
$\displaystyle\leq(|y|+|r|+\mu(y)c)\sup_{z\in B(x,r)}q(z,y)$

where $c\mathrel{\mathop{\mathchar 58\relax}}=\sup_{z\in
B(x,r)}\partial_{z}\mu(z)/\mu(z)^{2}<\infty$ due our positivity and continuous
differentiability of the target assumption, and where we used
$g^{\prime},g^{\prime\prime}\leq 1$. The other domination condition on
$|\partial_{z}(q(z,y)g^{\prime}(r_{\mu}(z,y)))|$ –which is not used here but
later to prove a Feller-type property– is equivalent to the former in the
Random Walk case. It is possible to find kernel derivatives with other
assumptions on the starting distributions, on the invariant distributions, the
proposal, the balancing function, and for general $V$ by adapting the
arguments used above and in the relevant appendixes. For instance, for an
unbounded $V$ one would additionally require that $\mu(V)<\infty$ for all
$\mu$ indexed by the family to perform the limit exchange justified in Section
A.2. This naturally (and notationally) suggests the use of a $V$ that is a
suitable Lypunov function for the different distributions indexed by the
family—see Section 3. The requirement that $g$ is differentiable however
cannot be immediately relaxed. Although the result above then does not
guarantee differentiability of Metropolis-Hastings kernels, we will be able to
obtain results for the Metropolis choice indirectly later.

In the example below, a probability distribution with a numerical subscript
denotes the marginal in the indicated coordinate of the underlying probability
distribution, we write $y=(y_{1},y_{2})$ for a point $y\in\mathsf{X}^{2}$,
$\lambda^{2}$ for $\lambda\otimes\lambda$ and a single integral sign for
multiple integrals when no confusion is possible.

######  Example 2.4 (Derivatives of Gibbs kernels).

Consider the MCMC kernels of Example 2.2 with $P_{1|2}$ and $P_{2|1}$
admitting a common dominating measure with $\mu_{1}$ and $\mu_{2}$. Further
consider the following assumption.

  1. G1

The indexed invariant distributions have upper bounded continuously
differentiable and positive densities. The full conditionals are bounded in
the starting point and for all $x\in\mathsf{X}$ they satisfy $\sup_{z\in
B(x,r)}|\partial_{z}P_{1|2}(z,y)|\leq\psi(y)$ for some function $\psi\in
L^{1}(\lambda)$.

Let $\mathcal{W}_{G}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}d\rho_{2}/d\mu_{2}\text{ is bounded for all indexed $\mu$}\\}$.

######  Proposition 2.5.

The Gibbs kernel $P_{\cdot}(\rho,\cdot)$ is differentiable in the invariant
distribution at $\mu$ for all $\rho\in\mathcal{W}_{G}$. In this case, the
derivative $\partial_{\pi}P_{\mu}(\rho,\cdot)$ admits an integral
representation, with its density given for all
$f\in\mathbf{C}_{V}^{1}(\mathsf{X}^{2})$ by

$\displaystyle\partial_{\pi}P_{\mu}(\rho,f)(y)$ $\displaystyle=\int
f(y_{1},w_{2})\frac{\rho(y_{2})}{\mu_{2}(y_{2})}P_{2|1}(y_{1},dw_{2})-\int
f(w_{1},w_{2})\frac{\rho(y_{2})}{\mu_{2}(y_{2})}P_{1|2}(y_{2},dw_{1})P_{2|1}(w_{1},dw_{2})$
$\displaystyle+\int
f(y_{1},y_{2})\frac{\rho(dw_{2})}{\mu_{1}(y_{1})}P_{1|2}(w_{2},y_{1})-\int
f(y_{1},w_{2})\frac{\rho(du_{2})}{\mu_{1}(y_{1})}P_{1|2}(u_{2},y_{1})P_{2|1}(y_{1},dw_{2}).$
(10)

Furthermore, if Assumption G1 holds, $P_{\cdot}(\rho,\cdot)$ is differentiable
at $\mu$ for all $\rho$ in the weak completion of the set
$\mathcal{A}_{x}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda^{2}}(\mathsf{X}^{2})\mathrel{\mathop{\mathchar
58\relax}}\mathrm{supp}(\rho)\subseteq B(x,r)\\}$. In particular,
$P_{\cdot}(x,\cdot)$ is also differentiable for all $x\in\mathsf{X}^{2}$. In
this case, $\partial_{\pi}P_{\mu}(x,\cdot)$ is given for all
$f\in\mathbf{C}_{V}^{1}(\mathsf{X}^{2})$ and
$\nu\in\mathcal{P}_{\lambda^{2}}(\mathsf{X}^{2})$ by

$\displaystyle\partial_{\pi}P_{\mu}(x,f)[\nu-\mu]=$
$\displaystyle=\int\bigg{(}\int
f(y_{1},w_{2})\frac{P_{2|1}(y_{1},dw_{2})}{\mu_{2}(x_{2})}-\int
f(w_{1},w_{2})\frac{P_{1|2}(x_{2},dw_{1})P_{2|1}(w_{1},dw_{2})}{\mu_{2}(x_{2})}\bigg{)}(\nu-\mu)(y_{1},x_{2})\lambda(dy_{1})$
$\displaystyle+\int\bigg{(}f(y_{1},y_{2})\frac{P_{1|2}(x_{2},y_{1})}{\mu_{1}(y_{1})}-\int
f(y_{1},w_{2})\frac{P_{1|2}(x_{2},y_{1})P_{2|1}(y_{1},dw_{2})}{\mu_{1}(y_{1})}\bigg{)}(\nu-\mu)(y)\lambda^{2}(dy).$
(11)

###### Proof.

This is similar the proof of Proposition 2.4. First we notice that for the
deterministic scan we can just write the full conditionals in terms of $\mu$
as $P_{1|2}(x^{\prime},y)=\mu(y,x^{\prime})/\int\mu(z,x^{\prime})\lambda(dz)$
and similarly for $P_{2|1}$, hence

$P_{\mu}((x_{1},x_{2}),f)=\int\int
f(w_{1},w_{2})\frac{\mu(w_{1},x_{2})}{\int\mu(z,x_{2})\lambda(dz)}\frac{\mu(w_{1},w_{2})}{\int\mu(w_{1},z)\lambda(dz)}\lambda^{2}(dw).$

Then, by exploiting the fact that the transition probabilities do not depend
on the first coordinate of the starting point we compute

$\displaystyle\frac{d}{dt}P_{\mu+t(\nu-\mu)}(\rho,f)\bigg{|}_{t=0}$
$\displaystyle=\int\int\chi(dw_{1},du_{2})\int
f(w_{1},w_{2})\frac{\rho_{2}(u_{2})}{\mu_{2}(u_{2})}P_{2|1}(w_{1},dw_{2})$
$\displaystyle-\int\int\chi(dz,du_{2})\int\int
f(w_{1},w_{2})\frac{\rho_{2}(u_{2})}{\mu_{2}(u_{2})}P_{1|2}(u_{2},dw_{1})P_{2|1}(w_{1},dw_{2})$
$\displaystyle+\int\int\chi(dw_{1},dw_{2})\int
f(w_{1},w_{2})\frac{\rho_{2}(du_{2})}{\mu_{1}(w_{1})}P_{1|2}(u_{2},dw_{1})$
$\displaystyle-\int\int\chi(dw_{1},dz)\int\int
f(w_{1},w_{2})\frac{\rho_{2}(du_{2})}{\mu_{1}(w_{1})}P_{1|2}(u_{2},dw_{1})P_{2|1}(w_{1},dw_{2}).$

Using the expression above and (3) one identifies (2.5). Integrating the
latter w.r.t. $\mu$ shows that (5) is also satisfied. The details on the limit
exchange are in Section A.2. To show differentiability for all starting
distribution in the weak completion of $\mathcal{A}_{x}$ we show that
$\rho\mapsto\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ is uniformly continuous on
$\mathcal{A}_{x}$ for all $\nu\in\mathcal{P}_{\lambda^{2}}(\mathsf{X}^{2})$.
This is similar to the proof of Proposition 2.4 \- the details are in Section
A.2. ∎

Again, the boundedness of $d\rho_{2}/d\mu_{2}$ is a warm-start type condition,
which we note is in general weaker than the warm-start required to
differentiate Hastings kernels. We again note that the assumption Assumption
G1 is rather weak, and it is somehow the analogue of the domination condition
required in Assumption H1 discussed above. Let us notice that also here the
operator $\partial_{\pi}P_{\mu}(x,f)$ has no integral representation.

Using the fact that the balancing function $g$ has to satisfy
$g(x)=xg^{\prime}(x)+g^{\prime}(1/x)$, it is possible to check that when
$\rho=\mu$, the derivative in the invariant measure of the Hastings kernels at
$y\in\mathsf{X}$ becomes (minus) the generator of the Markov chain, and the
same is true for Gibbs kernels derivatives, as expected.

###  2.3 FTC Formula and bounded derivatives

We now state a formula that, under a weak-Feller type condition on which we
comment below, allow us to compare Markov Chains with different invariant
distributions belonging to the same Markov family in terms of the derivative
in the invariant distribution. This is a Fundamental Theorem of Calculus-like
formula, whose analogue appears in Robust Statistics [26, Chapter 2] and Mean
Field Games [12].

  1. A1

The Markov kernels family $\\{P_{\star}\\}$ satisfies a Feller-type condition:
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$ implies
$P_{\mu}f\in\mathbf{C}^{1}_{1}(\mathsf{X})$ for all
$P_{\mu}\in\\{P_{\star}\\}$.

######  Theorem 2.2 (Fundamental Theorem of MCMC Calculus Formula).

For all $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ for which
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$, i.e. $\rho\in\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t},\lambda}(P)$,

$P_{\mu}(\rho,f)-P_{\nu}(\rho,f)=\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]dt.$
(12)

for all $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$.

If Assumption A1 holds and $\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]$ is
bounded in $t$, (12) is true also for all
$\rho\in\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t}}(P)$.

Furthermore, if $\partial_{\pi}P_{\mu_{t}}(\rho,f)$ admits a continuously
differentiable density and $\nu$ can be expressed via some pushforward $T$
from $\mu$ in that $\nu=T_{*}\mu$ we also have

$\displaystyle P_{\mu}(\rho,f)-P_{\nu}(\rho,f)$
$\displaystyle=\int_{0}^{1}\int\int^{y}_{T(y)}D_{\pi}P_{\mu_{t}}(\rho,f)(s)dsd\mu(y)dt$
$\displaystyle=\int_{0}^{1}\int(T(y)-y)\int_{0}^{1}D_{\pi}P_{\mu_{t}}(\rho,f)(s(T(y)-y)+y)dsd\mu(y)dt,$
(13)

where $D_{\pi}P_{\mu}(\rho,f)(y)\mathrel{\mathop{\mathchar
58\relax}}=(d/dy)\partial_{\pi}P_{\mu}(\rho,f)(y)$.

###### Proof.

Let
$(\rho,f)\in\mathcal{P}_{\lambda}(\mathsf{X})\times\mathbf{C}^{1}_{V}(\mathsf{X})$.
Write $\mu_{t}=(1-t)\mu+t\nu$, so that $\mu_{1}=\nu$ and $\mu_{0}=\mu$. Then,

$P_{\mu}(\rho,f)-P_{\nu}(\rho,f)=\int_{0}^{1}\frac{d}{dt}P_{\mu_{t}}(\rho,f)dt=\int_{0}^{1}\lim_{s\rightarrow
0}\frac{P_{\mu_{t+s}}(\rho,f)-P_{\mu_{t}}(\rho,f)}{s}dt$

Now, since for all fixed $t$,
$\mu_{t+s}=\mu_{t}+s(\mu_{1}-\mu_{t})/(1-t)=\mu_{t}+s((\mu_{1}-t\mu_{t})/(1-t)-\mu_{t})$,
and then using (3) with
$(\mu_{1}-\mu_{t})/(1-t)\in\mathcal{M}_{\lambda,0}(\mathsf{X})$ being a 0–mass
perturbation one can write under our hypotheses that for $t\in[0,1)$

$\displaystyle
P_{\mu}(\rho,f)-P_{\nu}(\mu,f)=\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)\left[\frac{\mu_{1}-\mu_{t}}{1-t}\right]dt=\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]dt,$

with last equality following because
$\mu_{1}-\mu_{t}=\nu-\mu_{t}=(1-t)(\nu-\mu)$. This proves the claim for all
$\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ for which the differentiability
requirement is met. Now assume Assumption A1 and consider a
$\rho\in\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t}}(P)$ not necessarily in
$\mathcal{P}_{\lambda}(\mathsf{X})$. By definition, $\rho$ is in the weak
completion $\tilde{\mathcal{A}}$ of some set
$\mathcal{A}\subset\mathcal{P}_{\lambda}(\mathsf{X})$ on which
$\rho\mapsto\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]$ is uniformly
continuous for all $t\in[0,1]$. Considering a sequence
$\rho_{j}\in\mathcal{A}\Rightarrow\rho\in\tilde{\mathcal{A}}$ under Assumption
A1 we compute

$\displaystyle P_{\mu}(\rho,f)-P_{\nu}(\rho,f)$
$\displaystyle=\lim_{j\rightarrow\infty}P_{\mu}(\rho_{j},f)-P_{\nu}(\rho_{j},f)=\lim_{j\rightarrow\infty}\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho_{j},f)[\nu-\mu]dt$
$\displaystyle=\mathrel{\mathop{\mathchar
58\relax}}\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]dt,$ (14)

where the limit exchange follows from the assumed boundedness of
$t\mapsto\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]$ via dominated
convergence. To prove (2.2), use (12) with $\mu_{t}\mathrel{\mathop{\mathchar
58\relax}}=(1-t)\mu+tT_{*}\mu$ to obtain

$\displaystyle P_{\mu}(\rho,f)-P_{T_{*}\mu}(\rho,f)$
$\displaystyle=\int_{0}^{1}\int\partial_{\pi}P_{\mu_{t}}(\rho,f)(y)d(T_{*}\mu-\mu)(y)dt$
$\displaystyle=\int_{0}^{1}\int\left[\partial_{\pi}P_{\mu_{t}}(\rho,f)(T(y))-\partial_{\pi}P_{\mu_{t}}(\rho,f)(y)\right]d\mu(y)dt.$

Since $y\mapsto\partial_{\pi}P_{\mu_{t}}(\rho,f)(y)$ is continuously
differentiable by assumption, an application of the Fundamental Theorem of
Calculus completes the proof. ∎

######  Remark 2.1.

We have seen in Examples 2.3 and 2.6 that for Hastings and Gibbs type kernels
in fact, under regularity conditions, such
$\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t}}(P)$ contains at least the set
$\\{\delta_{x}\\}_{x\in\mathsf{X}}$.

######  Remark 2.2.

When $V$ is bounded, Assumption A1 is mild and satisfied by many MCMC kernel
used in practice, including the Hastings and Gibbs families under assumption
Assumptions H1 and G1. For instance, for the Hastings chain, if
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$ then $Pf$ is clearly bounded, and to show
it is also continuously differentiable in all $x\in\mathsf{X}$, we can show
that each $x$ is in a neighbourhood $B(x,r)$ in which $Pf$ is continuously
differentiable. Under our assumptions $q(x,y)g(r_{\mu}(x,y))$ is continuously
differentiable and by the (first) domination condition we can conclude that
$\int f(y)q(x,y)g(r_{\mu}(x,y))\lambda(dy)$ and $\int
q(x,y)g(r_{\mu}(x,y))\lambda(dy)$ (and so $Pf$) are too at $x$ by e.g. [29,
Theorem 6.28].

When $V$ is not bounded, $Pf$ might not be bounded. Thus to obtain (12) for
$\rho\in\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t}}(P)$ not necessarily in
$\mathcal{P}_{\lambda}(\mathsf{X})$, we can instead require that for
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$, $Pf$ is continuously differentiable and
it satisfies a suitable uniform integrability condition. Call $\mathcal{A}$
the subset of $\mathcal{P}_{\lambda}(\mathsf{X})$ that has $\rho$ in its weak
completion, and consider a sequence $\rho_{j}\in\mathcal{A}\Rightarrow\rho$.
If $\sup_{j\geq 0}\int|Pf(y)|^{1+\epsilon}\rho_{j}(dy)<\infty$ and
$\sup_{j\geq 0}\int|P_{\nu}f(y)|^{1+\epsilon}\rho_{j}(dy)<\infty$ for some
$\epsilon>0$ for all such sequences $\\{\rho_{j}\\}_{j\in\mathbb{N}}$, we
would still obtain (2.3) (e.g. [10, Section 3.5]). For instance, using the
preceding remark, we have seen that
$\delta_{x}\in\bigcap_{t=0}^{1}\mathcal{D}_{\mu_{t}}(P)$, and that
$\delta_{x}$ is the weak completion of
$\mathcal{A}_{x}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}\mathrm{supp}(\rho)\subseteq B(x,r)\\}$. Clearly for any sequence
$\rho_{j}$ in $\mathcal{A}_{x}$, for $\sup_{j\geq
0}\int|P_{\mu}f(y)|^{1+\epsilon}\rho_{j}(dy)<\infty$ to hold it is sufficient
that $P_{\mu}f$ is bounded in the compact $B(x,r)$, which is very often the
case for Hastings and Gibbs kernels. In particular, the Hastings and Gibbs
families under assumption Assumptions H1 and G1 satisfy this property.

######  Remark 2.3.

The assumption of boundedness of
$t\mapsto\partial_{\pi}P_{\mu_{t}}(\rho,f)[\nu-\mu]$ is simply verified simply
whenever $\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]$ and
$\partial_{\pi}P_{\nu}(\rho,f)[\nu-\mu]$ exist for our Hastings and Gibbs
families.

We put together the last three Remark for reference.

######  Lemma 2.1.

For the Hastings and Gibbs families (12) is true for all
$\rho\in\mathcal{W}_{H}$ and $\rho\in\mathcal{W}_{G}$, respectively, and if
Assumptions H1 and G1 hold, also for all
$\rho\in\\{\delta_{x}\\}_{x\in\mathsf{X}}$.

######  Remark 2.4.

The quantity $D_{\pi}P_{\mu}(\rho,f)$ can be related to rigorous notions of
derivatives in the Wasserstein geometry studied in [2]. It describes
variations of the transition probabilities when $\mu$ is perturbed in the
direction $\nu$ along the curves that are not simple interpolations like
$\mu_{t}$ but rather transport maps. In fact, one can substitute $T$ with
$\textrm{Id}-hT$ in (2.2) to obtain

$\displaystyle P_{\mu}(\rho,f)-P_{T_{*}\mu}(\rho,f)$
$\displaystyle=h\int_{0}^{1}\int
T(y)\int_{0}^{1}D_{\pi}P_{\mu_{t}}(\rho,f)(sh+y)dsd\mu(y)dt.$

Dividing by $h$ and letting $h\rightarrow 0$ we get

$\lim_{h\rightarrow
0}\frac{P_{(\textrm{Id}-hT)_{*}\mu}(\rho,f)-P_{\mu}(\rho,f)}{h}=\int
D_{\pi}P_{\mu}(\rho,f)(y)T(y)d\mu(y).$

We will employ Theorem 2.2 mainly as a way to obtain mean value type
inequalities in the next section. However, formulæ such as (12) or (2.2) could
be used in general to obtain a possibly hard to guess expression for the
difference in expectations given by two Markov kernels with different
invariant distributions within the same family. We will often think of one of
them as being an approximation of the other. In this context, we think of $T$
in (2.2) as a map that makes the distribution $\mu$ easier to work with. For
instance, for diffeomorphisms $T_{1},...,T_{j}$, one can let
$T=T_{1}\circ....\circ T_{j}$ obtaining a so-called normalizing flow, that can
be used to smooth out complicated distributions when sampling via MCMC—see
[21, 36] Notice that with $\rho=\nu$ one also obtains

$P_{\mu}(\nu,f)-\nu(f)=\int_{0}^{1}\int\partial_{\pi}P_{\mu_{t}}(\nu,f)(y)d(\nu-\mu)(y)dt;$

an expression for the difference in expectation with respect to a Markov
kernel applied to an initial distribution to that with respect to the
distribution itself.

###  2.4 Bounded kernel derivatives and Mean-Value inequalities

We want to argue that if the derivative in the invariant distribution at $\mu$
towards $\nu$ is bounded in some sense, then the Markov Chains associated with
kernels $P_{\mu}$ and $P_{\nu}$ move similarly whenever $\mu$ and $\nu$ are
close. We define the concept of bounded derivative in the invariant
distribution accordingly. We aim to provide a statement similar to the fact
that on $\mathbb{R}$ a differentiable function has a bounded derivative if and
only if it is Lipschitz.

######  Definition 2.6.

We say that a differentiable Markov kernel $P_{\cdot}(\rho,\cdot)$ has a
bounded derivative at $\mu$ towards $\nu$ if there exist constants
$M_{1,\rho},M_{2,\rho}<\infty$ such that

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{V}\leq
M_{1,\rho}\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}+M_{2,\rho}\rho(|\mu-\nu|).$
(15)

Noting that $d(\mu,\nu)=||\mu-\nu||_{V}+\rho(|\mu-\nu|)$ is itself a metric,
this could be written as a standard statement of Lipschitz continuity with
respect to that distance, with constant given by the larger of $M_{1,\rho}$
and $M_{2,\rho}$. However, the form we have here allow us to separate the role
of two separate contributions and we believe that this refinement can be
informative. With this in mind, we will sometimes refer to
$M_{1,\rho},M_{2,\rho}$ as Lipschitz constants, and to inequalities of the
form (15) a mean value inequalities. The next Propositions show that
Definition 2.6 work as intended: we will see that if $P_{\cdot}(\rho,\cdot)$
is differentiable in $\mu_{t}=(1-t)\mu+t\nu$ for all $t\in[0,1]$ and a
boundedness condition on the derivative holds, then $P_{\cdot}(\rho,\cdot)$
will have a bounded derivative in the invariant distribution at $\mu$ towards
$\nu$. Of course the boundedness depend on $V$, but we often silence this
dependence because it is implicit in the context. When
$\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$, this Definition 2.6 is equivalent
to the existence of a constant $M_{\rho}<\infty$ such that

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{V}\leq
M_{\rho}\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}.$ (16)

i.e. to the operator $P_{\cdot}(\rho,\cdot)$ from $\mathcal{P}(\mathsf{X})$
(via the invariant distribution) to $\mathcal{P}(\mathsf{X})$ (the
corresponding transition probabilities) being Lipschitz continuous w.r.t.
$\mathinner{\\!\left\lVert\cdot\right\rVert}_{V}$. In fact, obviously if (16)
is true then (15) holds with $M_{2,\rho}\mathrel{\mathop{\mathchar
58\relax}}=0$, and on the other hand when
$\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ we can bound
$M_{2,\rho}\rho(|\mu-\nu|)\leq
M_{2,\rho}\sup(\rho/V)\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}$, and
(16) holds true with $M_{\rho}\mathrel{\mathop{\mathchar
58\relax}}=M_{1,\rho}+M_{2,\rho}\sup(\rho/V)$. If $\rho=\delta_{x}$, (15)
becomes

$\mathinner{\\!\left\lVert
P_{\mu}(x,\cdot)-P_{\nu}(x,\cdot)\right\rVert}_{V}\leq
M_{1,x}\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}+M_{2,x}|\mu(x)-\nu(x)|.$
(17)

This express the fact that as for many kernels employed in MCMC settings in
particular, $P_{\cdot}(x,\cdot)$ typically depends on the values of the
density of the invariant distribution at $x\in\mathsf{X}$, one cannot expect
$P_{\mu}(x,\cdot)$ to be close to $P_{\nu}(x,\cdot)$ unless $\mu(x)$ is close
to $\nu(x)$, since the closedness of $\mu$ to $\nu$ in $V$-distance does not
imply that their densities functions at single points are close, at least
without further assumptions. Sometimes, like in the Gibbs case,
$P_{\cdot}(x,\cdot)$ depends on the values of the invariant at some coordinate
of the vector $x$ only. In this situation, if $\mathcal{J}$ is an index set,
$x_{\mathcal{J}}$ denote the element of the vector $x$ indicated by
$\mathcal{J}$ and a sub-scripted probability measures indicate the marginal in
the indicated coordinate, a more sensible definition of bounded derivative of
$P_{\cdot}(x,\cdot)$ would be the existence of $M_{1,x},M_{2,x}<\infty$ such
that

$\mathinner{\\!\left\lVert
P_{\mu}(x,\cdot)-P_{\nu}(x,\cdot)\right\rVert}_{V}\leq
M_{1,x}\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}+M_{2,x}|\mu_{\mathcal{J}}(x_{\mathcal{J}})-\nu_{\mathcal{J}}(x_{\mathcal{J}})|.$

where $dx_{\mathcal{J}}$ indicates that we integrate out all the coordinates
in some index set $\mathcal{J}$. The case $\mathcal{J}=\emptyset$ corresponds
to (17). This relaxed definition, although useful in certain contexts, is
slightly cumbersome so we opted for (17) to illustrate concepts
parsimoniously.

Notice that if a Markov kernel has a bounded derivative in the invariant
distribution at $\mu$ towards $\nu$ and $\mu$ is close to $\nu$, the Markov
Chains following $P_{\mu}(x,\cdot)$ and $P_{\nu}(x,\cdot)$ never move too
differently starting from $x$, in that their $V$-distance is small. We can
similarly consider other integral probability metrics and obtain related
inequalities. Here we focused on the $V$-norm due its popularity within the
MCMC literature arising from its close connection with Lyapunov functions for
ergodicity [38, 35]. In Section 3 we exploit these connections. We now
introduce a stronger form of boundedness.

######  Definition 2.7.

We say that a Markov kernel $P_{\cdot}(\rho,\cdot)$ has a
$\mathcal{Q}$-uniformly bounded derivative at $\mu$ towards $\nu$ if there
exist constants $M_{1},M_{2}<\infty$ such that for all $\rho\in\mathcal{Q}$:

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{V}\leq
M_{1}\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}+M_{2}\rho(|\mu-\nu|).$

If $\mathcal{Q}=\\{\delta_{x}\\}_{x\in\mathsf{X}}$ the chains move alike
uniformly in the space if their invariant distributions are close at all
points. Notice that a Markov kernel has an $\mathcal{Q}$-uniformly bounded
derivative at $\mu$ towards $\nu$ if it has bounded derivative and the
associated Lipschitz constants can be bounded uniformly over
$\rho\in\mathcal{Q}$. See at the end of this section for such an example where
$\mathcal{Q}$ is the set of warm-start distributions. Finding conditions for
$P_{\cdot}(\rho,\cdot)$ to have a bounded derivative in the invariant
distribution when $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ is rather
immediate from Theorem 2.2.

######  Proposition 2.6.

For all $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ for which the Markov kernel
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$ with its derivative admitting a density, and

$M_{\rho}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{f\in\mathbf{C}^{1}_{V}(\mathsf{X})}\left|\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)(\cdot)dt\right|_{V}<\infty,$

$P_{\cdot}(\rho,\cdot)$ has a bounded derivative at $\mu$ towards $\nu$ with
Lipschitz constant $M_{\rho}$, i.e.

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{V}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}M_{\rho}$

###### Proof.

For all $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$ obeying the
differentiability requirement and $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$, from
(12) we obtain

$\displaystyle|P_{\mu}(\rho,f)-P_{\nu}(\rho,f)|$
$\displaystyle=\left|\int\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)(y)dtd(\nu-\mu)(y)\right|.$

However, for any $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$, we have

$\left|\int\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)(y)dtd(\nu-\mu)(y)\right|\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}\left|\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(\rho,f)(\cdot)dt\right|_{V},$

and the claim follows by Lemma A.2 upon taking the supremum over functions in
$\mathbf{C}^{1}_{V}(\mathsf{X})$. ∎

In other words, the mapping $P_{\cdot}(\rho,\cdot)\mathrel{\mathop{\mathchar
58\relax}}\mu\in(\mathcal{P}(\mathsf{X}),\mathinner{\\!\left\lVert\cdot\right\rVert}_{V})\mapsto
P_{\mu}(\rho,\cdot)\in(\mathcal{P}(\mathsf{X}),\mathinner{\\!\left\lVert\cdot\right\rVert}_{V})$
is a Lipschitz continuous function of its invariant distribution with
Lipschitz constant $M_{\rho}$.

Proposition 2.6 provides a condition for a Markov kernel to have bounded
derivative when $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$. Proving
boundedness for more general $\rho$ and obtaining mean value inequalities is
harder, and there is not in general a direct analogue to Proposition 2.6 since
in this case $\partial_{\pi}P_{\mu}(\rho,\cdot)$ is only defined weakly, and
one has to retrieve Mean-Value inequalities on a case to case basis. In the
next example we illustrate this point for $\rho=\delta_{x}$ and we study when
the kernel derivatives of the Hastings and Gibbs type kernels are bounded for
$V=1$.

######  Example 2.5 (Bounded derivatives and Mean Value inequalities for
Hastings kernels).

######  Proposition 2.7.

Let $\\{P_{\star}\\}$ be a Hastings family.

  1. 1.

Let $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$. If the Markov kernel
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$, and $M_{\rho}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{t,\rho}dt<\infty$ with

$D_{t,\rho}\mathrel{\mathop{\mathchar
58\relax}}=2\sup_{y}\left|\int\frac{\rho(z)}{\mu_{t}(z)}q(y,z)g^{\prime}(r_{\mu_{t}}(z,y))\lambda(dz)+\frac{\rho(y)}{\mu_{t}(y)^{2}}\int{\mu_{t}}(z)q(z,y)g^{\prime}(r_{\mu_{t}}(y,z))\lambda(dz)\right|,$
(18)

then $P_{\cdot}(\rho,\cdot)$ has a bounded derivative at $\mu$ towards $\nu$
with Lipschitz constant $M_{\rho}$ and we have the mean value inequality

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{t,\rho}dt.$ (19)

  2. 2.

If Assumption A1 holds, the Markov kernel $P_{\cdot}(x,\cdot)$ is
differentiable at $\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$
for all $t\in[0,1]$, and $M_{1,x}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{1,t,x}dt<\infty,M_{2,x}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{2,t,x}dt<\infty$ with

$\displaystyle D_{1,t,x}\mathrel{\mathop{\mathchar
58\relax}}=2\sup_{y}\left|\frac{g^{\prime}(r_{\mu_{t}}(x,y))q(y,x)}{\mu_{t}(x)}\right|,\quad\text{and}\quad
D_{2,t,x}\mathrel{\mathop{\mathchar
58\relax}}=2\int\frac{\mu_{t}(z)}{\mu_{t}(x)^{2}}q(z,x)g^{\prime}(r_{\mu_{t}}(x,z))\lambda(dz),$
(20)

then $P_{\cdot}(x,\cdot)$ has a bounded derivative at $\mu$ towards $\nu$ with
Lipschitz constants $M_{1,x}.M_{2,x}$ and we have the mean value inequality

$\mathinner{\\!\left\lVert P_{\mu}(x,\cdot)-P_{\nu}(x,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{1,t,x}dt+|\mu(x)-\nu(x)|\int_{0}^{1}D_{2,t,x}dt.$ (21)

Furthermore, if $\mathcal{Q}$ is a subset of $\mathcal{P}(\mathsf{X})$ such
that $M_{\rho}$ can be bounded uniformly in $\rho\in\mathcal{Q}$, or
$\mathcal{Q}=\\{\delta_{x}\mathrel{\mathop{\mathchar
58\relax}}x\in\mathfrak{X}\\}$ and $M_{1,x},M_{2,x}$ can be bounded uniformly
in $x\in\mathfrak{X}$, then $P_{\cdot}(\rho,\cdot)$ has a
$\mathcal{Q}$-uniformly bounded derivative at $\mu$ towards $\nu$.

###### Proof.

The expression for $D_{t,\rho}$ and (19) are immediate from Propositions 2.6
and 2.4 and the fact that if $f\in\mathbf{C}^{1}_{V}(\mathsf{X})$,
$|f(y)-f(z)|\leq 2$ when $V=1$. To prove the inequality (21), notice that
under our assumptions we can use Theorem 2.2 and then Proposition 2.4 to write

$\displaystyle\left|P_{\mu}(x,f)-P_{\nu}(x,f)\right|$
$\displaystyle=\left|\int_{0}^{1}\partial_{\pi}P_{\mu_{t}}(x,f)[\nu-\mu]dt\right|\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}\int_{0}^{1}D_{1,f,t,x}dt+|\mu(x)-\nu(x)|\int_{0}^{1}D_{2,f,t,x}dt,$

with

$\displaystyle D_{1,f,t,x}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{y}\left|{(f(y)-f(x))\frac{g^{\prime}(r_{\mu_{t}}(x,y))q(y,x)}{\mu_{t}(x)}}\right|\leq
2\sup_{y}\left|{\frac{g^{\prime}(r_{\mu_{t}}(x,y))q(y,x)}{\mu_{t}(x)}}\right|=\mathrel{\mathop{\mathchar
58\relax}}D_{1,t,x},$ $\displaystyle D_{2,f,t,x}\mathrel{\mathop{\mathchar
58\relax}}=\int(f(z)-f(x))\frac{\mu_{t}(z)}{\mu_{t}(x)^{2}}q(z,x)g^{\prime}(r_{\mu_{t}}(x,z))\lambda(dz)\leq
2\int\frac{\mu_{t}(z)}{\mu_{t}(x)^{2}}q(z,x)g^{\prime}(r_{\mu_{t}}(x,z))\lambda(dz)=\mathrel{\mathop{\mathchar
58\relax}}D_{2,t,x}.$

Taking the supremum over functions in $\mathbf{C}^{1}_{V}(\mathsf{X})$ and
using Lemma A.2 one obtains (21). ∎

Putting together Propositions 2.4, 2.7 and 2.1 yields the following.

######  Corollary 2.1.

Let $\rho\in\mathcal{W}_{H}$. For all indexed $\mu,\nu$, the Hastings kernel
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$ and $M_{\rho}<\infty$, where $M_{\rho}$ is given in (18).
Therefore, $P_{\cdot}(\rho,\cdot)$ has a bounded derivative in the invariant
distribution at $\mu$ towards $\nu$, and the mean value inequality (19) holds.

######  Corollary 2.2.

Assume Assumption H1. For all indexed $\mu,\nu$, the Hastings kernel
$P_{\cdot}(x,\cdot)$ is differentiable at $\mu_{t}\mathrel{\mathop{\mathchar
58\relax}}=(1-t)\mu+t\nu$ for all $t\in[0,1]$ and $M_{1,x},M_{2,x}<\infty$,
where $M_{1,x},M_{2,x}$ are given in (20). Therefore, $P_{\cdot}(\rho,\cdot)$
has a bounded derivative in the invariant distribution at $\mu$ towards $\nu$,
and the mean value inequality (21) holds.

Although Proposition 2.4 does not guarantee the differentiability of
Metropolis-Hastings kernels in the invariant distribution, we can still obtain
Lipschitz inequalities for such kernels indirectly by looking at Metropolis-
Hastings kernels as limit of a sequence of differentiable ones. The function
$g_{j}(x)\mathrel{\mathop{\mathchar
58\relax}}=(x+\dots+x^{j})/(1+x+\dots+x^{j})$ is a proper balancing function,
it yields a differentiable Markov family, and it satisfies
$g_{j}(x)\rightarrow\min(1,x)=\mathrel{\mathop{\mathchar 58\relax}}g(x)$ for
all $x>0$ [1]. Let $\\{P_{\star}\\}$ be now a Metropolis-Hastings family, with
the same restrictions on the indexed invariants and $q$ as above.

######  Proposition 2.8.

For all $\rho\in\mathcal{W}_{H}$ the Lipschitz inequality (19) holds with

$D_{t,\rho}\mathrel{\mathop{\mathchar
58\relax}}=2\sup_{y}\left|\int\frac{\rho(z)}{\mu_{t}(z)}q(y,z)\lambda(dz)+\frac{\rho(y)}{\mu_{t}(y)^{2}}\int{\mu_{t}}(z)q(z,y)\lambda(dz)\right|.$
(22)

For all $x\in\mathsf{X}$ the Lipschitz inequality (21) holds with

$D_{1,t,x}\mathrel{\mathop{\mathchar
58\relax}}=2\sup_{y}\left|\frac{q(y,x)}{\mu_{t}(x)}\right|\quad\text{and}\quad
D_{2,t,x}\mathrel{\mathop{\mathchar
58\relax}}=2\int\frac{\mu_{t}(z)}{\mu_{t}(x)^{2}}q(z,x)1_{\\{z\mathrel{\mathop{\mathchar
58\relax}}r_{\mu_{t}}(x,z)\leq 1\\}}(z)\lambda(dz).$ (23)

###### Proof.

Let $P_{\cdot,j}$ be the differentiable Hastings kernel employing the
balancing function $g_{j}$. For $\rho\in\mathcal{W}_{2,H}$ proceeding as in
Propositions 2.6 and 2.7 we obtain
$|P_{\mu,j}(\rho,f)-P_{\nu,j}(\rho,f)|\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{t,\rho,j}dt$, where $D_{t,\rho,j}$ is as in (18) with
balancing function $g_{j}$. Noting then that $\sup_{j}g_{j}\leq 1$ we can take
the limit $j\rightarrow\infty$ both sides. At the left hand side we obtain
$|P_{\mu}(\rho,f)-P_{\nu}(\rho,f)|$ via bounded convergence. At the right hand
side we can use $\sup_{j}|g^{\prime}_{j}|\leq 1$ to bound $D_{t,\rho,j}\leq
D_{t,\rho}$ and prove the first claim upon taking the supremum across
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$. The second claim is proved very
similarly by following the second part of Proposition 2.7 and using $g_{j}$ as
above, however, upon taking the limit $j\rightarrow\infty$ at the left hand
side we also use the fact that $g^{\prime}_{j}(x)\rightarrow 1_{\\{x\leq
1\\}}(x)$ and the bounded convergence theorem to obtain the displayed
Lipschitz constants. ∎

Roughly speaking, we have shown that we can ensure that if $\mu$ and $\nu$ are
close, two Hastings chain $P_{\mu}$ and $P_{\nu}$ move similarly with some
proper choice of the initial distribution, the proposal distribution and the
balancing function. Proposition 2.7 also allows to easily find conditions for
$\mathcal{Q}$-uniformly bounded derivatives. If we let
$\mathcal{Q}_{H}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}d\rho/d\mu^{2},d\rho/d\nu^{2}\leq C\\}$ for some finite $C$, then of
course $d\rho/d\mu_{t}^{2}\leq C$ for all $t\in[0,1]$ and it is easy to see
that we can bound $D_{t,\rho}$ uniformly in $\rho\in\mathcal{Q}_{H}$. This
means that we can get two Hastings chain $P_{\mu}$ and $P_{\nu}$ to move
similarly, uniformly in the starting distribution, provided that a warm-start
condition holds, i.e. that they are not initialized too far into the tails of
their invariant distributions. On the other hand, if we start our Markov
chains from a point $x\in\mathsf{X}$, to get $P_{\mu}$ and $P_{\nu}$ to move
alike uniformly in the starting point $x\in\mathsf{X}$ seems to be much harder
on non-compact spaces, and conditions such as
$\sup_{x}q(y,x)/\mu(x)^{2},\sup_{x}q(y,x)/\mu(x)^{2}<\infty$ seem to be
required.

######  Example 2.6 (Bounded derivatives and Mean Value inequalities for Gibbs
kernels).

######  Proposition 2.9.

Let $\\{P_{\star}\\}$ be a deterministic scan Gibbs family.

  1. 1.

Let $\rho\in\mathcal{P}_{\lambda}(\mathsf{X})$. If the Markov kernel
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$, and it holds that $M_{\rho}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{t,\rho}dt<\infty$ with

$\displaystyle D_{\rho,t}\mathrel{\mathop{\mathchar 58\relax}}=\sup_{y}$
$\displaystyle\bigg{(}\int\frac{\rho_{2}(y_{2})}{\mu_{2,t}(y_{2})}P_{2|1,t}(y_{1},dw_{2})+\int\frac{\rho_{2}(y_{2})}{\mu_{2,t}(y_{2})}P_{1|2,t}(y_{2},dw_{1})P_{2|1,t}(w_{1},dw_{2}).$
$\displaystyle+\int\frac{\rho_{2}(du_{2})}{\mu_{1,t}(y_{1})}P_{1|2,t}(u_{2},y_{1})+\int\frac{\rho_{2}(du_{2})}{\mu_{1,t}(y_{1})}P_{1|2,t}(u_{2},y_{1})P_{2|1,t}(y_{1},dw_{2})\bigg{)}$
(24)

then $P_{\cdot}(\rho,\cdot)$ has a bounded derivative at $\mu$ towards $\nu$
with Lipschitz constant $M_{\rho}$ and we have the mean value inequality

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{\rho,t}dt.$ (25)

  2. 2.

If Assumption A1 holds, the Markov kernel $P_{\cdot}(x,\cdot)$ is
differentiable at $\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$
for all $t\in[0,1]$, and it holds that $M_{1,x}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{1,t,x}dt<\infty$ and
$M_{2,x}\mathrel{\mathop{\mathchar
58\relax}}=\int_{0}^{1}D_{2,t,x,z}dt<\infty$ with

$D_{1,t,x}\mathrel{\mathop{\mathchar
58\relax}}=4\sup_{y}\bigg{(}\frac{P_{1|2,t}(x_{2},y_{1})}{\mu_{1,t}(y_{1})}\bigg{)},$
(26) $D_{2,t,x}\mathrel{\mathop{\mathchar
58\relax}}=2\bigg{(}\frac{1}{\mu_{2,t}(x_{2})}+\int\frac{P_{1|2,t}(x_{2},dw_{1})P_{2|1,t}(w_{1},dw_{2})}{\mu_{2,t}(x_{2})}\bigg{)},$
(27)

then, $P_{\cdot}(x,\cdot)$ has a bounded derivative in the invariant
distribution at $\mu$ towards $\nu$ with Lipschitz constants
$M_{1,x},M_{2,x,z}$ and we have the mean value inequality

$\mathinner{\\!\left\lVert P_{\mu}(x,\cdot)-P_{\nu}(x,\cdot)\right\rVert}_{\rm
tv}\leq\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm
tv}\int_{0}^{1}D_{1,t,x}dt+|\mu_{2}(x_{2})-\nu_{2}(x_{2})|\int_{0}^{1}D_{2,t,x}dt$
(28)

Furthermore, if $\mathcal{Q}$ is a subset of $\mathcal{P}(\mathsf{X})$ such
that $M_{\rho}$ can be bounded uniformly in $\rho\in\mathcal{Q}$, or
$\mathcal{Q}=\\{\delta_{x}\mathrel{\mathop{\mathchar
58\relax}}x\in\mathfrak{X}\\}$ and $M_{1,x},M_{2,x}$ can be bounded uniformly
in $x\in\mathfrak{X}$, then $P_{\cdot}(\rho,\cdot)$ has a
$\mathcal{Q}$-uniformly bounded derivative at $\mu$ towards $\nu$.

###### Proof.

This follows by basically the same arguments used in Proposition 2.7 by using
Proposition 2.5 in place of Proposition 2.4. ∎

Combining Propositions 2.5, 2.9 and 2.1 yields the following. The claim on the
finiteness of the Lipschitz constants follows from Bayes’ formula.

######  Corollary 2.3.

Let $\rho\in\mathcal{W}_{G}$. For all indexed $\mu,\nu$, the Gibbs kernel
$P_{\cdot}(\rho,\cdot)$ is differentiable at
$\mu_{t}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\nu$ for all
$t\in[0,1]$ and $\int_{0}^{1}D_{t,\rho}dt<\infty$, where $D_{t,\rho}$ is given
in (1). Therefore, $P_{\cdot}(\rho,\cdot)$ has a bounded derivative in the
invariant distribution at $\mu$ towards $\nu$, and the mean value inequality
(25) holds.

Similarly to the Hastings case, we can also envisage conditions to bound the
Lipschitz constants uniformly in the starting distributions. In fact,
recently, [5, Proposition 2.4] derived the inequality

$\mathinner{\\!\left\lVert
P_{\mu}(\rho,\cdot)-P_{\nu}(\rho,\cdot)\right\rVert}_{\rm tv}\leq
2KM\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{\rm tv}$ (29)

for the deterministic scan Gibbs kernel, where $K$ represents the number of
stages, for $\rho$ having a density and satisfying the warm-start conditions
$d\rho_{2}/d\mu_{2}\leq M$, $d\rho_{2}/d\nu_{2}\leq M$ for some $M>0$. In
fact, we can verify using Bayes formula that for all initial distributions
with warm-start $\rho\in\mathcal{Q}_{G}\mathrel{\mathop{\mathchar
58\relax}}=\\{\rho\in\mathcal{P}_{\lambda}(\mathsf{X})\mathrel{\mathop{\mathchar
58\relax}}d\rho_{2}/d\mu_{2},d\rho_{2}/d\nu_{2}\leq M\\}$ we have
$M_{\rho}<\infty$, with $M_{\rho}$ given in Proposition 2.9 above, and that in
particular $\sup_{\rho\in\mathcal{W}}M_{\rho}\leq 4M$. That is, by Proposition
2.9, the deterministic Gibbs kernel has a $\mathcal{Q}_{G}$-uniformly bounded
derivative at $\mu$ towards $\nu$ and the mean value inequality (29) holds,
providing an alternative proof of the result in [5] in the case $K=2$ studied
here (and the argument could be extended to the general case at the expense of
introducing some slightly cumbersome notation). As noted in [5], under warm-
start we do not have to require any other regularity from the full
conditionals $P_{1|2},P_{2|1}$ to obtain this mean value inequality. If we
also require some extra regularity we can also obtain the following.

######  Corollary 2.4.

Assume Assumption G1. For all indexed $\mu,\nu$, the Gibbs kernel
$P_{\cdot}(x,\cdot)$ is differentiable at $\mu_{t}\mathrel{\mathop{\mathchar
58\relax}}=(1-t)\mu+t\nu$ for all $t\in[0,1]$ and
$\int_{0}^{1}D_{1,t,x}dt,\int_{0}^{1}D_{2,t,x}dt<\infty$, where
$D_{1,t,\rho},D_{2,t,\rho}$ are given in (26) and (27). Therefore,
$P_{\cdot}(\rho,\cdot)$ has a bounded derivative in the invariant distribution
at $\mu$ towards $\nu$, and the mean value inequality (21) holds.

As in the Hastings case, requiring uniformity in the starting point will
typically restrict the results applicability to compact spaces.

####  2.4.1 Fluctuations of Markov kernels

One can use the kernel derivatives defined to infer weak laws for Markov
kernels using random invariant distributions without much trouble. This result
is potentially useful to design efficient MCMC algorithms when using
approximations instead of an invariant distribution of interest. In the
preceding section, we argued that one can ensure that the approximated chain
move similarly to the limiting one by choosing a Markov kernel with a bounded
derivative. An alternative is to minimize fluctuations of the approximated
kernel around the limiting one. These fluctuations depend directly on the
derivative in the invariant distribution.

######  Proposition 2.10.

Let $\mathcal{G}(\mathsf{X})$ be some function class. Let $P_{\cdot}(\rho,f)$
be a Markov kernel differentiable in $\mu$, with
$\partial_{\pi}P_{\mu}(\rho,f)$ admitting a density. Suppose that
$\\{\mu_{n}\\}_{n\in\mathbb{N}}\in\mathcal{P}(\mathsf{X})$ are random measures
w.r.t. $\mathbb{P}$ and suppose that the random field
$\\{\sqrt{n}(\mu_{n}-\mu)(f);f\in\mathcal{G}(\mathsf{X})\\}$ converges in law
to a Gaussian random field $\\{N(f);f\in\mathcal{G}(\mathsf{X})\\}$ specified
by $\mathbb{E}(N(f))=m(f)$ and $\mathbb{E}(N(f)N(g))=v(f,g)$. Then, if
$\partial_{\pi}P_{\mu}(\rho,f)\in\mathcal{G}(\mathsf{X})$,

$\sqrt{n}(P_{\mu_{n}}(\rho,f)-P_{\mu}(\rho,f))\Rightarrow
N\left(\partial_{\pi}P_{\mu}(\rho,f)\right).$ (30)

I.e. the random field
$\\{\sqrt{n}(P_{\mu_{n}}(\rho,f)-P_{\mu}(\rho,f)),f\in\mathcal{G}(\mathsf{X})\\}$
converges in law to a Gaussian random field
$\\{N^{\prime}(f);f\in\mathcal{G}(\mathsf{X})\\}$ specified by
$\mathbb{E}(N^{\prime}(f))=m\left(\partial_{\pi}P_{\mu}(\rho,f)\right)$ and
$\mathbb{E}(N^{\prime}(f)N^{\prime}(g))=v\left(\partial_{\pi}P_{\mu}(\rho,f),\partial_{\pi}P_{\mu}(\rho,g)\right)$.

###### Proof.

Denoting $\mu_{t,n}\mathrel{\mathop{\mathchar 58\relax}}=(1-t)\mu+t\mu_{n}$,
we have by definition

$|P_{\mu_{t,n}}(\rho,f)-P_{\mu}(\rho,f)-\partial_{\pi}P_{\mu}(\rho,f)[\mu-\mu_{t,n}]|=o(t)$

as $t\rightarrow 0$. Now, whenever $\partial_{\pi}P_{\mu}(\rho,f)$ admits a
density such that
$\partial_{\pi}P_{\mu}(\rho,f)(\cdot)\in\mathcal{G}(\mathsf{X})$ one has

$\sqrt{n}\partial_{\pi}P_{\mu}(\rho,f)[\mu_{n}-\mu]=\sqrt{n}\left(\mu_{n}-\mu\right)\left(\partial_{\pi}P_{\mu}(\rho,f)\right)\Rightarrow
N\left(\partial_{\pi}P_{\mu}(\rho,f)\right),$

and the claim follows. ∎

##  3 Applications to Monte Carlo

We now demonstrate the applications of the tools developed in the previous
section to Monte Carlo Methods. The tools we developed allow an easy
comparison between Markov Chains of the same family with different invariant
distributions. Usually we think of one of these distributions as an
approximation of the other. Therefore, other than being of theoretical
interest, this framework is naturally appealing to study the use of
approximations in Markov Chain Monte Carlo. In this context, we compare a
Markov Chain targeting a limiting distribution of interest, $\mu$, with a
Markov Chain targeting an approximation thereof. Using an MCMC kernel with an
approximation is common and can occur in a number of contexts. For instance,
when $\mu$ is intractable, or when $\mu$ is tractable, but rather inefficient
to target directly, so one targets an approximation instead. For instance, (i)
Griddy Gibbs Sampling [37] proposes to use “griddy” approximations of the full
conditionals when sampling from the latter is not possible; (ii) [36] proposes
to use Normalizing Flows to smooth away distributions that are complicated to
sample from via MCMC—see also [21] for an application; (iii) [31, 32] employ a
stochastic collocation approach to approximate complicate target distribution
to target via Metropolis-Hastings. These approximations could be evolved or
not as the Markov Chain runs, or the output of the resulting MCMC can be used
to approximate the invariant distribution of another MCMC, giving rise to the
framework for Sequential MCMC and Interacting MCMC we study in Sections 3.1.1
and 3.1.2. In these two settings belong (iv) Sequential Particle Filters [9,
23, 41, 30] and Example 3.1, based on running a sequence of MCMC algorithms,
each with an approximate invariant distribution obtained with another MCMC
output; and (v) Interacting Particle Filters [4, 6, 11, 15, 19] and Example
3.2 where we run an inhomogeneous Markov Chain of which invariant distribution
evolves, perhaps depending on another Markov Chain running on another level.
Another natural context would be the Uncertainty Quantification literature,
where the ideal distribution $\mu$ to target as a distribution over a function
space, and one instead targets $\mu_{n}$ being measures over discretisations.

Let us denote with $\nu$ an approximation of $\mu$. It might be of interest to
ensure that the Markov chains $P_{\mu}$ and $P_{\nu}$ move similarly. We have
seen that this can be ensured when the derivative in the invariant
distribution at $\mu$ towards $\nu$ is bounded. Also, it might be of interest
to study the rate of convergence of $P_{\mu}$ to $P_{\nu}$, and this can be
done via the Mean-Value inequalities of Section 2.4. If $\nu$ is random,
perhaps is also of interest to minimize the fluctuations of the kernel
$P_{\nu}$ around $P_{\mu}$—see Proposition 2.10. For Hastings type kernels,
these strategies can be for instance implemented by choosing the initial
distribution, the proposal $q$ and the balancing function $g$ accordingly, see
Example 2.5.

As an illustration of why it might be of interest to ensure that $P_{\mu}$ and
$P_{\nu}$ move similarly, we show in the next section that (under suitable
regularity conditions) this ensures that estimators associated with the two
associated Markov chains achieve similar asymptotic variances, up to an
additional variability due to the fluctuations of $\nu$ around $\mu$.

###  3.1 Efficiency of MCMC with approximations

In this section we combine MCMC Calculus tools with results from [19] and [20]
to study the efficiency of Markov chains employing approximations in place of
a limiting distribution of interest. Let $\\{P_{\star}\\}$ be a Markov Family.
Consider a “limiting” Markov chain $\\{X_{k}\\}_{k\in\mathbb{N}}$ with
transitions $X_{k+1}|X_{k}=x_{k}\sim P_{\mu}(x_{k},\cdot)$, targeting a
distribution $\mu$ of interest, that might be intractable or inefficient to
target directly. We consider two approaches to approximate
$\\{X_{k}\\}_{k\in\mathbb{N}}$. In the first we consider a situation in which
one has access to a sequence $\\{\mu_{n}\\}$ of increasingly good
approximations of $\mu$ and study the convergence of a sequence of
approximating chains which make use of this sequence as its invariant
measures; that is, it comprises a triangular array of Markov chains
$\\{Y_{n,k}\\}_{k\leq n}$, where for each $k\leq n$,
$Y_{n,k+1}|Y_{n,k}=y_{n,k}\sim P_{\mu_{n}}(y_{n,k},\cdot)$. Since in our
examples below $\mu_{n}$ comes from a previously run chain, we refer to this
scheme as Sequential MCMC (sMCMC). In this framework belong [9, 23, 41, 30]
among others. The second approach to approximate
$\\{X_{k}\\}_{k\in\mathbb{N}}$ is to consider an (inhomogeneous) Markov chain
$\\{Z_{k}\\}_{k\in\mathbb{N}}$ targeting at each $k$ a distribution $\mu_{k}$
that is refined at each step and that is getting closer to $\mu$ i.e. with
transitions $Z_{k+1}|Z_{k}=z_{k}\sim P_{\mu_{k}}(z_{k},\cdot)$. We refer to
this scheme as Interacting MCMC (iMCMC). In this framework belong [4, 6, 11,
15, 19] among others. We are interested in studying the fluctuations of
$n^{-1/2}\sum_{i=1}^{n}f(Y_{n,i})$ and $n^{-1/2}\sum_{i=1}^{n}f(Z_{i})$ around
$\mu(f)$ for some test functions $f$ to be specified. Studying these
fluctuations desirable as it provides information on the properties of sampled
values viewed as estimators of expectations w.r.t. $\mu$ and characterizes the
additional variability of estimators arising from using Markov kernels
targeting (random) approximations of distributions rather than the
distributions themselves. Fluctuations for these algorithms have already been
studied in some of the papers cited above, but we express the results somehow
naturally in terms of boundedness of the derivatives in the invariant
distributions and the quality of the approximation scheme
$\mu_{n}\rightarrow\mu$, and in some cases we improve on existing results.

For both sMCMC and iMCMC, we assume that
$\mu_{n}\in\mathcal{P}_{\lambda}(\mathsf{X})$ for each $n\in\mathbb{N}$, and
we employ the following standard (if strong) assumptions.

  1. B1

    1. (a)

For all $n\geq 1$, $P_{\mu_{n}}$ are $\mu_{n}$-irreducible, aperiodic Markov
kernels. Furthermore, there exists a function $V\mathrel{\mathop{\mathchar
58\relax}}\mathsf{X}\mapsto[1,\infty)$ and constants $b<\infty$,
$\lambda\in(0,1)$ such that for all $n\geq 1$:

$P_{\mu_{n}}V\leq\lambda V(x)+b1_{C}(x),$

where $C\mathrel{\mathop{\mathchar 58\relax}}=\\{x\mathrel{\mathop{\mathchar
58\relax}}V(x)\leq d\\}$ for some $d\geq b/(2(1-\lambda))-1$.

    2. (b)

There exist an integer $j\geq 1$, a positive constant $\kappa_{n}$ with
$\inf_{n}\kappa_{n}>0$ and a probability measure $\upsilon_{n}$ such that for
all $x\in C$, $P^{j}_{\mu_{n}}(x,A)\geq\kappa_{n}\upsilon_{n}(A)$ for all
$A\in\mathcal{B}(\mathsf{X})$.

  2. B2

There exist an integer $j>1$ such that $\sup_{n}\mu_{n}(V^{j})<\infty$,
$\sup_{n}\mathbb{E}(V^{j}(Z_{n}))<\infty$ (for $\\{Z_{k}\\}_{k\in\mathbb{N}}$)
and $\sup_{n,k}\mathbb{E}(V^{j}(Y_{n,k}))<\infty$ (for $\\{Y_{n,k}\\}_{k\leq
n}$).

Assumption B1 is an uniform (in the sequence of invariant distributions
$\\{\mu_{n}\\}_{n\in\mathbb{N}}$) geometric drift and minorization assumption,
similar to the conditions considered in [3] and in the adaptive MCMC
literature (e.g. [19, 20]). For the algorithms under examination, we can in
fact just look at the invariant distributions as an adaptation parameter
living in the infinite dimensional space $\mathcal{P}(\mathsf{X})$. Using the
techniques in [19, 20] it is also possible to let $(\lambda,b)$ depend on $n$
in some judicious way, but we require their uniformity w.r.t. $n$ to allow the
arguments which follow to focus upon the use of MCMC Calculus tools rather
than technical details. Verifying Assumption B1 requires that $\mu_{n}$ does
not behave too differently with $n$. By way of an illustration, to verify the
minorization condition Assumption B1b, following [33, Lemma 1.2] one has
$P_{\mu_{n}}(x,A)\geq(\varepsilon/b_{n})\mu_{n}(A)$, with
$\varepsilon\mathrel{\mathop{\mathchar 58\relax}}=\inf_{x,y\in B}q(x,y)$,
$b_{n}\mathrel{\mathop{\mathchar 58\relax}}=\sup_{x\in B}\mu_{n}(x)$, $B$
being any compact set with positive Lebesgue measure. Therefore, it suffices
to require that the approximation sequence satisfies $\inf_{n}\sup_{x\in
B}\mu_{n}(x)>0$, which is arguably not hard to verify in practice. If this
holds, then any compact set is small, and adapting [27, Lemma 3.5] one can
verify Assumption B1a whenever

$\sup_{n}\limsup_{|x|\rightarrow\infty}\frac{P_{\mu_{n}}V(x)}{V(x)}<1\quad\text{and}\quad\sup_{n}\sup_{x\in\mathsf{X}}\frac{P_{\mu_{n}}V(x)}{V(x)}<\infty$

Which, adapting the proof of [33, Theorem 3.2], can be verified with the
Lyapunov function $V(x)=\exp(\gamma|x|)$ for Random Walk Metropolis (and other
Random Walk Hastings kernels) if all $\mu_{n}$ are uniformly log-concave in
the tails i.e. when for all $n\geq 1$ there exist a $\gamma>0$ and $z>0$ such
that

$\log(\mu_{n}(x))-\log(\mu_{n}(y))\geq\gamma(y-x)\quad\text{for }y\geq x\geq
z$ (31) $\log(\mu_{n}(x))-\log(\mu_{n}(y))\geq\gamma(x-y)\quad\text{for }y\leq
x\leq-z.$ (32)

See Example 3.1 later for a concrete setting where we verify this. In the case
where $P_{\mu_{n}}$ is a Hastings Independence sampler $Q(x,dy)=Q(dy)$ and the
proposal has heavier tail than any distribution in the approximation sequence
in that $\inf_{n}dQ/d\mu_{n}(y)\geq\beta$ for some $\beta>0$, then the whole
state space $\mathsf{X}$ is small for any $P_{\mu_{n}}$ simultaneously, and
the drift condition will hold with a bounded $V$. Assumption B2 is a growth
condition which can actually always be verified with some drift function if
Assumption B1 holds. In fact, via the drift condition Assumption B1a we have

$\mathbb{E}(V(Z_{n}))\leq\lambda\mathbb{E}(V(Z_{n-1}))+b\leq\lambda^{n}\mathbb{E}(V(Z_{0}))+b\sum^{n-1}_{i=0}\lambda^{i}$

where we just iterated the first inequality in $n$, and upon taking the
supremum in $n$ we obtain that $\sup_{n}\mathbb{E}(V(Z_{n}))<\infty$ and also
$\sup_{n}\mu_{n}(V)<\infty$ via Lemma B.1 (i.e. Assumption B2 holds with
$j=1$). On the other hand, for $j>1$, we can adapt the proof of [22,
Proposition 6.5] and define $\tilde{V}\mathrel{\mathop{\mathchar
58\relax}}=V^{1/j}$, so that
$\sup_{n}\mu_{n}(\tilde{V}^{j})=\sup_{n}\mu_{n}(V)<\infty$. By Jensen’s
inequality,

$\displaystyle P_{\mu_{n}}\tilde{V}\leq(P_{\mu_{n}}V)^{1/j}\leq(\lambda
V+b1_{C})^{1/j}\leq\tilde{\lambda}V+\tilde{b}1_{C}$

with $\tilde{\lambda}\mathrel{\mathop{\mathchar 58\relax}}=\lambda^{1/j}$ and
$\tilde{b}\mathrel{\mathop{\mathchar 58\relax}}=b^{1/j}$. Hence, $\tilde{V}$
also satisfies Assumption B1 and arguing as above we may verify
$\sup_{n}\mathbb{E}(V^{j}(Z_{n}))<\infty$ and $\sup_{n}\mu_{n}(V^{j})<\infty$.
For $\\{Y_{n,k}\\}_{k\leq n}$ it is similar.

####  3.1.1 Sequential MCMC

For the Sequential MCMC sampling scheme $\\{Y_{n,k}\\}_{k\leq n}$ we employ
the following assumptions. Let $V$ satisfy Assumption B1.

  1. C1

$\mu_{n}(x)\rightarrow\mu(x)$ $\mathbb{P}$-a.s. for all $x\in\mathsf{X}$.

  2. C2

The Markov kernel $P_{\cdot}(x,\cdot)$ is differentiable in the invariant
distribution at $\mu$, and has a $V$-bounded derivative at $\mu$ towards every
$\mu_{n}$.

  3. C3

As $n\rightarrow 0$, for all $f$ in some functions class
$\mathcal{G}(\mathsf{X})$ and for some variance functional $v$,

$n^{-1/2}[\mu_{n}-\mu](f)\Rightarrow N(0,v(f)).$

Assumption C1 is a requirement on the nature of the approximation scheme,
which has to occur pointwise. Assumption C2 will ensure that the Markov Chains
using $\mu$ and $\mu_{n}$ will in fact not move too differently when
Assumption C1 holds. In fact, it is sufficient that a mean value inequality
(17) holds, and by Proposition 2.8 also the Metropolis-Hastings kernels
satisfy that under the boundedness conditions stated therein. Assumption C3 is
a mild assumption that says that if the employed approximation is random
w.r.t. some $\mathbb{P}$, it also has a limiting Gaussian fluctuations around
$\mu$, and it will be fulfilled by most approximation schemes used in
practice.

Let $\sigma^{2}$ denote the asymptotic variance achieved by
$\\{X_{k}\\}_{k\in\mathbb{N}}$.

######  Theorem 3.1.

Assume Assumptions A1, B1, C1 and C2. For all
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$,

$n^{-1/2}\sum_{i=0}^{n}f(Y_{n,i})-\mu_{n}(f)\Rightarrow N(0,\sigma^{2}(f))$
(33)

and if Assumption C3 holds too, for
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})\cap\mathcal{G}(\mathsf{X})$,

$n^{-1/2}\sum_{i=0}^{n}f(Y_{n,i})-\mu(f)\Rightarrow
N(0,\sigma^{2}(f)+v^{2}(f)).$ (34)

Theorem 3.1 tells us in fact $\\{Y_{n,k}\\}_{k\leq n}$ possess a limiting
Normal law around $\mu$ as $n\rightarrow\infty$, with the asymptotic variance
equal to the asymptotic variance of an ideal MCMC scheme targeting $\mu$
_plus_ the variability due of the fluctuations of $\mu_{n}$.

######  Example 3.1 (Sequential MCMC for Feynman-Kac flow).

[9, 23, 41, 30] among others consider the following algorithm, recently
theoretically analyzed by [18]. Let $\\{G^{(p)}\\}_{p\in\mathbb{N}}$ be a
sequence of non-negative functions, and $\\{M^{(p)}\\}_{p\in\mathbb{N}}$ be a
sequence of Markov kernel, and $\eta^{(1)}$ an initial distribution.

Algorithm 1 sMCMC for Feynman-Kac flow

For $p=1$,

  1. 1.

Simulate $Y^{(1)}_{i+1}\sim P_{\eta^{(1)}}(Y^{(1)}_{i},\cdot)$ for
$i=0,\dots,n$.

Set $\eta^{(1)}_{n}\mathrel{\mathop{\mathchar
58\relax}}=n^{-1}\sum_{i=0}^{n}\delta_{Y^{(1)}_{i}}$.
For $p\geq 2$,

  1. 1.

Simulate $Y^{(p)}_{n,i+1}\sim P_{\Phi(\eta^{(p-1)}_{n})}(Y^{(p)}_{n,i},\cdot)$
for $i=0,\dots,n$.

Set $\eta^{(p)}_{n}\mathrel{\mathop{\mathchar
58\relax}}=n^{-1}\sum_{i=0}^{n}\delta_{Y^{(p)}_{n,i}}$.

In the algorithm above, at each level $p$, the random variable $Y^{(p)}_{0}$
is sampled according to some initial distribution possibly depending on $p$.
Here, $\Phi(\eta^{(p)})(dx)\mathrel{\mathop{\mathchar
58\relax}}=\int\eta(dy)G^{(p)}(y)M^{(p)}(y,dx)/\eta(G^{(p)})$ is the so-called
Boltzmann-Gibbs transformation associated to the Feynman-Kac model
$\\{G^{(p)},M^{(p)}\\}_{p\in\mathbb{N}}$.

This is very flexible class of models, used perhaps most popularly in the
filtering context within state space models, where one has an underlying
unobserved Markovian state space process with some transition kernels
$m^{(p)}$ at time $p$, and an observable process having likelihood $g^{(p)}$
at $p$. $\\{G^{(p)},M^{(p)}\\}_{p\in\mathbb{N}}$ can be identified with
different relevant quantities related to $m^{(p)}$ and $g^{(p)}$, giving rise
to different filters. The classic but usually inefficient choice
$G^{(p)}=g^{(p)}$ and $M^{(p)}=m^{(p)}$ for all $p$ yields the Bootstrap
particle filter, see [14, 13]. Sampling from $\Phi(\eta^{(p)})$ with a
particle filter amounts to being able to evaluate pointwise $G$ and sample
i.i.d. from $M$. When one tries to implement more sophisticated filters, this
might not be possible. In such case, a natural choice is to try to target
$\Phi(\eta^{(p)})$ with a MCMC algorithm, giving rise to the algorithm above.
By targeting otherwise non implementable filters, this class of algorithms can
outperform standard particle filters in some settings—see [18], which gives
the only CLT for $\sqrt{n}[\eta^{(p)}_{n}-\eta^{(p)}](f)$ of which we are
aware. This CLT holds under conditions that are both restrictive and difficult
to verify, and that have only been shown to hold for independence samplers in
finite spaces. We can extend their results using our theory. We prove below a
CLT for bounded test functions for ease of exposition, but one can do much
better using the theorems above. We consider the following very weak
assumption regarding the Feynman-Kac flow.

  1. FK1

$G^{(p)}$ is positive and $M^{(p)}(x,\cdot)$ has a bounded density for all
$x\in\mathsf{X}$ and $p\in\mathbb{N}$.

Provided an LLN holds for the first Markov Chain
$\\{Y^{(1)}_{k}\\}_{k\in\mathbb{N}}$, for each subsequent Chain
$\\{Y^{(p)}_{n,k}\\}_{k\leq n},p>1$ we are in the setting studied for the
process $\\{Y_{n,k}\\}_{k\leq n}$ earlier.

In particular, suppose that Assumption B1 holds. If follows that the Markov
Chain $\\{Y^{(1)}_{k}\\}_{k\in\mathbb{N}},t>1$ satisfies a LLN and a CLT in
that $\eta^{(1)}_{n}(f)\rightarrow\eta^{(1)}(f)$ $\mathbb{P}$-a.s. and
$\sqrt{n}[\eta^{(1)}_{n}-\eta^{(1)}](f)\Rightarrow
N(0,\sigma_{\eta^{(1)}}(f))$ for all $f\in\mathbf{C}^{1}_{1}$. By the
decomposition

$[\Phi(\eta^{(1)}_{n})-\Phi(\eta^{(1)})](f)=[\eta^{(1)}_{n}-\eta^{(1)}](\bar{Q}^{(1)}(f-\Phi(\eta^{(1)}_{n})(f)))$
(35)

with the integral operator $\bar{Q}^{(p)}(x,f)\mathrel{\mathop{\mathchar
58\relax}}=G^{(p)}(x)M^{(p)}(x,f)/\eta^{(p)}(G^{(p)})$, under Assumption FK1
one then also has $\Phi(\eta^{(1)}_{n})(x)\rightarrow\Phi(\eta^{(1)})(x)$
$\mathbb{P}$-a.s. for all $x\in\mathsf{X}$,
$\Phi(\eta^{(1)}_{n})(x)\rightarrow\Phi(\eta^{(1)})(x)$ for all
$x\in\mathsf{X}$ $\mathbb{P}$-a.s. by separability and
$\sqrt{n}[\Phi(\eta^{(1)}_{n})-\Phi(\eta^{(1)})](f)\Rightarrow
N(0,\sigma^{2}_{\eta^{(1)}}(\bar{Q}^{(1)}(f-\Phi(\eta^{(1)})(f)))$. If $P$ has
a bounded derivative at $\Phi(\eta^{(1)})$ towards every
$\Phi(\eta^{(1)}_{n})$ then Theorem 3.1 shows

$[\eta^{(2)}_{n}-\eta^{(2)}](f)\Rightarrow
N\left(0,\sigma^{2}_{\eta^{(2)}}\left(f-\eta^{(2)}(f)\right)+\sigma^{2}_{\eta^{(1)}}\left(\bar{Q}^{(1)}(f-\eta^{(2)}(f)\right)\right).$

Repeating this argument allows us to establish the following result by
induction.

######  Theorem 3.2.

Let $p\in\mathbb{N}$ and $f\in\mathbf{C}^{1}_{1}$. Let $\\{P_{\star}\\}$ be a
Markov family such that $\Phi(\eta^{(j)}),\Phi(\eta^{(j)}_{n})$ for all $j\leq
p$ belong to its index set, and for which Assumptions A1, B1 and B2 hold. If
$P_{\cdot}$ has a bounded derivative at $\Phi(\eta^{(j)})$ towards every
$\Phi(\eta^{(j)}_{n})$ for all $j\leq p$ and if the Feynman-Kac model
$\\{G^{(p)},M^{(p)}\\}_{p\in\mathbb{N}}$ satisfies Assumption FK1 it holds

$[\eta^{(p)}_{n}-\eta^{(p)}](f)\Rightarrow
N\left(0,\sum_{j=1}^{p}\sigma^{2}_{\eta^{(j)}}\left(\bar{Q}^{(j\mathrel{\mathop{\mathchar
58\relax}}p)}(f-\eta^{(j)}(f)\right)\right).$

where we defined $\bar{Q}^{(j\mathrel{\mathop{\mathchar
58\relax}}p)}(f)\mathrel{\mathop{\mathchar
58\relax}}=[\bar{Q}^{(j+1)}\circ\cdots\circ\bar{Q}^{(p)}](f)$ for $j<p$ and
$Q^{(j\mathrel{\mathop{\mathchar 58\relax}}p)}(f)=\textrm{Id}$ for $j=p$.

For a concrete setting where this theorem is applicable, consider the
following simple example, which can be easily extended. Let $p\in\mathbb{N}$
and let $\\{P_{\star}\\}$ be the Metropolis-Hastings kernel. Consider the
State-Space model given by the latent process $W_{j+1}|W_{j}\sim
N(w_{j+1};\varphi(w_{j}),1/2)$ and the observable $S_{j+1}|W_{j+1}\sim
N(s_{j+1};w_{j+1},1/2)$, where $\varphi$ is a function bounded away from
$-\infty$ and $+\infty$, say $-\bar{\varphi}\leq\varphi(x)\leq\bar{\varphi}$
for some finite and positive $\bar{\varphi}$. State-space models provide a
very flexible way to model quantities that evolve in time, and that are widely
used in engineering, physics, quantitative finance and other fields, see e.g.
[13] for more details. Let us consider a Bootstrap interpretation of the
Feynman-Kac flow, by identifying the Markov kernels $M^{(p)}$ with $W$’s
transitions, and the potential functions $G^{(p)}$ with the likelihoods of the
observable. With this choice, it is easy to see that Assumption FK1 always
hold and that $\Phi(\eta^{(j)}),\Phi(\eta^{(j)}_{n})$ are for all $n\geq 1$,
$j\leq p$, continuously differentiable bounded above densities, and bounded
away from 0 on any compact set. Hence, by Proposition 2.8,
$P_{\cdot}(x,\cdot)$ satisfies a mean value inequality at $\Phi(\eta^{(j)})$
towards every $\Phi(\eta^{(j)}_{n})$ for all $j\leq p$. We now verify
Assumption B1 with $V(x)=\exp(\gamma|x|)$ for any $\gamma>0$ by verifying (31)
and (32) hence showing that $\Phi(\eta^{(j)}_{n})$ are for all $n,j\geq 1$
uniformly log-concave in the tails. Let $z\mathrel{\mathop{\mathchar
58\relax}}=\bar{\varphi}+\gamma/2$. If $y\geq x\geq z$, for
$x,y\in\mathsf{X}$, we compute

$\frac{\Phi(\eta^{(j)}_{n})(x)}{\Phi(\eta^{(j)}_{n})(y)}=\frac{\sum_{i=1}^{n}e^{-(s_{j}-Y^{(j)}_{i})^{2}}e^{-(x-\varphi(Y^{(j)}_{i}))^{2}}}{\sum_{i=1}^{n}e^{-(s_{j}-Y^{(j)}_{i})^{2}}e^{-(y-\varphi(Y^{(j)}_{i}))^{2}}}=e^{-x^{2}+y^{2}}\frac{\sum_{i=1}^{n}e^{-(s_{j}-Y^{(j)}_{i})^{2}+2x\varphi(Y^{(j)}_{i})-\varphi(Y^{(j)}_{i})^{2}}}{\sum_{i=1}^{n}e^{-(s_{j}-Y^{(j)}_{i})^{2}+2y\varphi(Y^{(j)}_{i})-\varphi(Y^{(j)}_{i})^{2}}}.$

Now, since
$e^{-(s_{j}-Y^{(j)}_{i})^{2}+2x\varphi(Y^{(j)}_{i})-\varphi(Y^{(j)}_{i})^{2}}/e^{-(s_{j}-Y^{(j)}_{i})^{2}+2y\varphi(Y^{(j)}_{i})-\varphi(Y^{(j)}_{i})^{2}}=e^{2\varphi(Y^{(j)}_{i})(x-y)}\geq
e^{(2z-\gamma)(x-y)}$, where the last inequality follows from
$\varphi(Y^{(j)}_{i})\leq z-\gamma/2$, we have

$\frac{\Phi(\eta^{(j)}_{n})(x)}{\Phi(\eta^{(j)}_{n})(y)}\geq
e^{-x^{2}+y^{2}}e^{(2z-\gamma)(x-y)}=e^{(y-x)(y+x-2z+\gamma)}\leq
e^{\gamma(y-x)},$

thus verifying (31). (32) follows from analogous computations when considering
the case $y\leq x\leq-z$.

####  3.1.2 Interacting MCMC

For $\\{Z_{k}\\}_{k\in\mathbb{N}}$ we strengthen the assumptions to

  1. D1

$n^{-1/2}\sum_{k=1}^{n}\sup_{x}|\mu_{k}(x)-\mu_{k-1}(x)|\rightarrow 0$ and
$n^{-1/2}\sum_{k=1}^{n}\mathinner{\\!\left\lVert\mu_{k}-\mu_{k-1}\right\rVert}_{V}\rightarrow
0$ $\mathbb{P}$-a.s.

  2. D2

The Markov kernel $P_{\cdot}(x,\cdot)$ is differentiable in the invariant
distribution at $\mu$, and has a
$(V,\\{\delta_{x}\\}_{x\in\mathsf{X}})$-uniformly bounded derivative at
$\mu_{n}$ towards $\mu_{n-1}$ for all $n\geq 1$.

  3. D3

As $n\rightarrow 0$, for all $f$ in some functions class
$\mathcal{G}(\mathsf{X})$ and for some variance functional $w$,

$n^{-1/2}\sum_{k=1}^{n}[\mu_{k}-\mu](f)\Rightarrow N(0,w(f)).$

The first condition Assumption D1 strengthen Assumption C1 requiring that the
approximation schemes is uniformly convergent on the space, and that the
convergence occurs fast-enough. We believe that the second condition of
Assumption D1 will often follow from the first, just as Assumption C1 implies
$\mathinner{\\!\left\lVert\mu_{n}-\mu\right\rVert}_{V}\rightarrow 0$
$\mathbb{P}$-a.s. (see Lemma B.3) and this is quite immediate if $\mathsf{X}$
is compact. Assumption D2 strengthens Assumption C2 to require that the
“Lipschitz constants” of the differentiable Markov kernel $P$ are bounded in
the starting point as per Definition 2.7. Assumption D3 is an asymptotic
normality assumption concerning the approximation scheme that will often hold
in the same situations as those in which Assumption C3 does—see Example 3.2.

######  Theorem 3.3.

Let $\alpha\in(0,1/2)$. If Assumptions A1, B1 and B2, as well as Assumptions
D1 and D2, hold, then for all $f\in\mathbf{B}_{V^{\alpha}}(\mathsf{X})$,

$n^{-1/2}\sum_{i=1}^{n}f(Z_{i})-\mu_{i-1}(f)\Rightarrow
N\left(0,\sigma^{2}(f)\right);$ (36)

and if Assumption D3 holds too, for
$f\in\mathbf{B}_{V^{\alpha}}(\mathsf{X})\cap\mathcal{G}(\mathsf{X})$,

$n^{-1/2}\sum_{i=1}^{n}f(Z_{i})-\mu(f)\Rightarrow
N\left(0,\sigma^{2}(f)+w^{2}(f)\right).$ (37)

Theorem 3.3 tells us that $\\{Z_{k}\\}_{k\in\mathbb{N}}$ also possess a
limiting Normal law, with asymptotic variance equal to that of an ideal MCMC
scheme targeting $\mu$ plus someadditional variability due the approximation.
This latter is often greater than the one we obtain with a Sequential MCMC
scheme, as in the Example below.

######  Example 3.2 (Interacting MCMC for Feynman-Kac flow).

[4, 6, 11, 15, 19] study the following type of algorithm.

Algorithm 2 iMCMC for Feynman-Kac flow

For $n=1,...$

  1. 1.

Simulate $Z^{(1)}_{n}\sim P_{\eta^{(1)}}(Z^{(1)}_{n-1},\cdot)$, set
$\eta^{(1)}_{n}\mathrel{\mathop{\mathchar
58\relax}}=n^{-1}\sum_{i=1}^{n}\delta_{Z^{(1)}_{i}}$

  2. 2.

Simulate $Z^{(2)}_{n}\sim P_{\Phi(\eta^{(1)}_{n})}(Z_{n-1}^{(2)},\cdot)$, set
$\eta^{(2)}_{n}\mathrel{\mathop{\mathchar
58\relax}}=n^{-1}\sum_{i=1}^{n}\delta_{Z^{(2)}_{i}}$

  3. ⋮

  4. $p$.

Simulate $Z^{(p)}_{n}\sim P_{\Phi(\eta^{(p-1)}_{n})}(Z_{n-1}^{(p)},\cdot)$,
set $\eta^{(p)}_{n}\mathrel{\mathop{\mathchar
58\relax}}=n^{-1}\sum_{i=1}^{n}\delta_{Z^{(p)}_{i}}$

At each level $p$, the random variable $Z^{(p)}_{0}$ is sampled according to
some initial distribution possibly depending on $p$. Each
$\\{Z^{(p)}_{k}\\}_{k\in\mathbb{N}},p>1$ is in the setting studied for the
process $\\{Z_{k}\\}_{k\in\mathbb{N}}$. On the top of Assumption FK1, consider

  1. FK2

$y\mapsto M(x,y)$ is continuous on $\mathsf{X}$ $\mathbb{P}$-a.s. for all
$x\in\mathsf{X}$.

Under Assumption FK1, as argued in Example 3.1, one has
$\Phi(\eta^{1}_{n})(x)\rightarrow\Phi(\eta^{1})(x)$ for all $x\in\mathsf{X}$
$\mathbb{P}$-a.s.. If $\mathsf{X}$ is compact and Assumption FK2 holds too,
the convergence can be made uniform, verifying Assumption D1. To prove that
Assumption D3 holds too, use (35) to write

$\displaystyle n^{-1/2}\sum_{k=1}^{n}$
$\displaystyle[\Phi(\eta^{(1)}_{k})-\Phi(\eta^{(1)})](f)=\sum_{k=1}^{n}\frac{n^{-1/2}}{k}\sum_{j=1}^{k}[\bar{Q}^{(1)}(f-\Phi(\eta_{k}^{(1)})(f))(Z^{(1)}_{j})-\eta^{(1)}(\bar{Q}^{(1)}(f-\Phi(\eta_{k}^{(1)})(f))]$
$\displaystyle=\int_{0}^{1}\frac{n^{-1/2}}{s}\sum_{j=1}^{sk}[\bar{Q}^{(1)}(f-\Phi(\eta_{k}^{(1)})(f))(Z^{(1)}_{j})-\eta^{(1)}(\bar{Q}^{(1)}(f-\Phi(\eta_{k}^{(1)})(f))]ds+o_{\mathbb{P}}(1)$
$\displaystyle\Rightarrow\sigma_{\eta^{(1)}}(\bar{Q}^{(1)}(f-\Phi(\eta^{(1)})(f))\int_{0}^{1}\frac{B_{s}}{s}ds,$

where in the last line we used the fact that a (functional) CLT holds for
$\\{Z^{(1)}_{n};n\geq 0\\}$, and where $B$ is a standard Brownian Motion. The
right hand side is a Gaussian random variable with variance
$w(f)\mathrel{\mathop{\mathchar
58\relax}}=2\sigma^{2}_{\eta^{(1)}}(\bar{Q}^{(1)}(f-\Phi(\eta^{(1)})(f))$.
Theorem 3.3 then applies to prove

######  Theorem 3.4.

Let $f\in\mathbf{B}_{1}$. Assume that $\mathsf{X}$ is compact, and that the
Markov family $\\{P_{\star}\\}$ Assumption B1 holds and that $P$ has an
uniformly bounded derivative at $\Phi(\eta^{(p)})$ towards every
$\Phi(\eta^{(p)}_{n})$ for all $p\leq 2$. Then, if the Feynman-Kac flow
$(G,M)$ satisfies Assumption FK1 and Assumption FK2 it holds

$[\eta^{(2)}_{n}-\eta^{(2)}](f)\Rightarrow
N(0,\sigma^{2}_{\eta^{(2)}}\left(f-\eta^{(2)}(f))+2\sigma^{2}_{\eta^{(1)}}(\bar{Q}^{(1)}(f-\eta^{(2)}(f))\right),$
(38)

where we defined the operator $\bar{Q}$ as in Theorem 3.2.

The case $p>2$ can be dealt with using Theorem 3.3, but it also requires
complex multilevel expansion formulæ—we refer to [8].

##  4 Closing remarks and research directions

We have developed herein a basic theory for methods allowing an easy and
natural comparison between Markov Chains of the same family with different
invariant distributions, by deriving analogues of the Fundamental Theorem of
Calculus and Mean-Value Inequality for MCMC kernels viewed as functions of
their invariant distributions. These tools allow us to study when Markov
chains with different invariant distributions will move alike. For instance,
under regularity conditions, we have seen that this can be ensured for
Hastings and Gibbs samplers if the Markov chain is started under warm-start
Corollaries 2.1, 2.2, 2.3 and 2.4, with a slightly “warmer” condition required
for Hastings chains.

Other than being of theoretical interest to derive interesting relationships
and inequality per se (see also the discussion in Example 2.6), this framework
is naturally appealing to study the use of approximations of invariant
distributions in Markov Chain Monte Carlo, as shown in Section 3, where,
roughly speaking, we have seen that under boundedness of the kernel
derivatives estimators associated with a Markov chain employing an
approximation $\mu_{n}$ of the invariant distribution $\mu$ achieve a similar
asymptotic variances to the limiting chain employing $\mu$, up to an
additional variability due to the fluctuations of the approximation.

In particular, we used our framework and the derived inequalities to prove
Central Limit Theorems for Sequential and Interacting MCMC algorithms. We also
notice that the techniques developed can also be adapted can to study Markov
chain Monte Carlo kernels as functions of their proposal, for instance. We
believe that interesting research directions include extending the methods
developed in this article to compare Markov Chains in different but somehow
related Markov families, explore the other notions of gradient and derivatives
in $\mathcal{P}(\mathsf{X})$, making further connections with the theory in
[2], exploring the use of higher-order derivatives, and developing methods to
study Markov families where the dependence on the invariant distribution is
not explicit. Furthermore, it might be of interest to explore other
applications of these tools, perhaps in the contexts discussed in Section 3.

## Acknowledgmenets

RC was funded by the UK Engineering and Physical Sciences Research Council
(EPSRC) via studentship 2585619 as part of grant number EP/W523793/1; AMJ was
partially funded by the EPSRC (grant numbers EP/R034710/1 and EP/T004134/1).
For the purpose of open access, the authors have applied a Creative Commons
Attribution (CC BY) licence to any Author Accepted Manuscript version arising
from this submission. Data sharing is not applicable to this article as no new
data were created or analyzed in this study.

## References

  * [1] Sanket Agrawal, Dootika Vats, Krzysztof Łatuszyński and Gareth O Roberts  “Optimal scaling of MCMC beyond Metropolis”  In _Advances in Applied Probability_ 55, 2023, pp. 492–509
  * [2] Luigi Ambrosio, Nicola Gigli and Giuseppe Savaré  “Gradient flows: in metric spaces and in the space of probability measures”  Birkhäuser Verlag, 2005
  * [3] Christophe Andrieu, Laird A Breyer and Arnaud Doucet  “Convergence of simulated annealing using Foster-Lyapunov criteria”  In _Journal of Applied Probability_ 38, 2001, pp. 975–994
  * [4] Christophe Andrieu, Ajay Jasra, Arnaud Doucet and Pierre Del Moral  “On nonlinear Markov chain Monte Carlo”  In _Bernoulli_ 17, 2011, pp. 987–1014
  * [5] Filippo Ascolani and Giacomo Zanella  “Complexity of Gibbs samplers through Bayesian asymptotics”  In _arXiv:2304.06993_ , 2023
  * [6] Yves F Atchadé  “A cautionary tale on the efficiency of some adaptive Monte Carlo schemes”  In _Annals of Applied Probability_ 20, 2010, pp. 841–868
  * [7] Anthony A Barker  “Monte carlo calculations of the radial distribution functions for a proton-electron plasma”  In _Australian Journal of Physics_ 18, 1965, pp. 119–134
  * [8] Bernard Bercu, Pierre Del Moral and Arnaud Doucet  “Fluctuations of interacting Markov chain Monte Carlo methods”  In _Stochastic Processes and their Applications_ 122, 2012, pp. 1304–1331
  * [9] Carlo Berzuini, Nicola G Best, Walter R Gilks and Cristiana Larizza  “Dynamic conditional independence models and Markov chain Monte Carlo methods”  In _Journal of the American Statistical Association_ 92, 1997, pp. 1403–1412
  * [10] Patrick Billingsley  “Convergence of probability measures”  New York: John Wiley & Sons, 1999
  * [11] Anthony Brockwell, Pierre Del Moral and Arnaud Doucet  “Sequentially interacting Markov chain Monte Carlo methods”  In _Annals of Statistics_ 38, 2010, pp. 3387–3411
  * [12] Pierre Cardaliaguet, François Delarue, Jean-Michel Lasry and Pierre-Louis Lions  “The master equation and the convergence problem in mean field games”  Princeton, NJ: Princeton University Press, 2019
  * [13] Nicolas Chopin and Omiros Papaspiliopoulos  “An introduction to sequential Monte Carlo”  Springer, 2020
  * [14] Pierre Del Moral  “Feynman-Kac formulae: genealogical and interacting particle systems with applications”  New York: Springer-Verlag, 2004
  * [15] Pierre Del Moral and Arnaud Doucet  “Interacting Markov chain Monte Carlo methods for solving nonlinear measure-valued equations”  In _Annals of Applied Probability_ 20, 2010, pp. 593–639
  * [16] Randal Douc and Eric Moulines  “Limit theorems for weighted samples with applications to sequential Monte Carlo methods”  In _Annals of Statistics_ 36, 2008, pp. 2344–2376
  * [17] Richard M Dudley  “Real Analysis and Probability”  Cambridge University Press, 2002
  * [18] Axel Finke, Arnaud Doucet and Adam M Johansen  “Limit theorems for sequential MCMC methods”  In _Advances in Applied Probability_ 52, 2020, pp. 377–403
  * [19] Gersende Fort, Eric Moulines and Pierre Priouret  “Convergence of adaptive and interacting Markov chain Monte Carlo algorithms”  In _Annals of Statistics_ 39, 2011, pp. 3262–3289
  * [20] Gersende Fort, Eric Moulines, Pierre Priouret and Pierre Vandekerkhove  “A central limit theorem for adaptive and interacting Markov chains”  In _Bernoulli_ 20, 2014, pp. 457–485
  * [21] Marylou Gabrié, Grant M Rotskoff and Eric Vanden-Eijnden  “Efficient Bayesian sampling using normalizing flows to assist Markov chain Monte Carlo Methods”  In _ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models_ , 2021
  * [22] Marco A Gallegos-Herrada, David Ledvinka and Jeffrey S Rosenthal  “Equivalences of Geometric Ergodicity of Markov Chains”  In _Journal of Theoretical Probability_ to appear, 2023, pp. 1–27
  * [23] Andrew Golightly and Darren J Wilkinson  “Bayesian sequential inference for nonlinear multivariate diffusions”  In _Statistics and Computing_ 16, 2006, pp. 323–338
  * [24] Keith W Hastings  “Monte Carlo sampling methods using Markov chains and their applications”  In _Biometrika_ 57, 1970, pp. 97–109
  * [25] Bernd Heidergott and Haralambie Leahu  “Weak differentiability of product measures”  In _Mathematics of Operations Research_ 35, 2010, pp. 27–51
  * [26] Peter J Huber and Elvezio M Ronchetti  “Robust statistics”  Hoboken, NJ: John Wiley & Sons, 2009
  * [27] Søren Fiig Jarner and Ernst Hansen  “Geometric ergodicity of Metropolis algorithms”  In _Stochastic Processes and their Applications_ 85, 2000, pp. 341–361
  * [28] Irving Kaplansky  “Set Theory and Metric Spaces”  AMS Chelsea Publishing, 1972
  * [29] Achim Klenke  “Probability theory: a comprehensive course”  Springer London, 2013
  * [30] Qing Li, Runze Gan, Jiaming Liang and Simon J Godsill  “An Adaptive and Scalable Multi-Object Tracker Based on the Non-Homogeneous Poisson Process”  In _IEEE Transactions on Signal Processing_ 71 IEEE, 2023, pp. 105–120
  * [31] Youssef M Marzouk, Habib N Najm and Larry A Rahn  “Stochastic spectral methods for efficient Bayesian solution of inverse problems”  In _Journal of Computational Physics_ 224, 2007, pp. 560–586
  * [32] Youssef M Marzouk and Dongbin Xiu  “A Stochastic Collocation Approach to Bayesian Inference in Inverse Problems”  In _Communications in Computational Physics_ 6, 2009, pp. 826–847
  * [33] Kerrie L Mengersen and Richard L Tweedie  “Rates of convergence of the Hastings and Metropolis algorithms”  In _Annals of Statistics_ 24, 1996, pp. 101–121
  * [34] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller and Edward Teller  “Equation of state calculations by fast computing machines”  In _Journal of Chemical Physics_ 21, 1953, pp. 1087–1092
  * [35] Sean P Meyn and Richard L Tweedie  “Markov chains and stochastic stability”  Cambridge: Cambridge University Press, 2009
  * [36] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed and Balaji Lakshminarayanan  “Normalizing flows for probabilistic modeling and inference”  In _Journal of Machine Learning Research_ 22, 2021, pp. 2617–2680
  * [37] Christian Ritter and Martin A Tanner  “Facilitating the Gibbs Sampler: The Gibbs Stopper and the Griddy-Gibbs Sampler”  In _Journal of the American Statistical Association_ 87, 1992, pp. 861–868
  * [38] Gareth O Roberts and Jeffrey S Rosenthal  “General state space Markov chains and MCMC algorithms”  In _Probability surveys_ 1, 2004, pp. 20–71
  * [39] Gareth O Roberts and Richard L Tweedie  “Exponential convergence of Langevin distributions and their discrete approximations”  In _Bernoulli_ 2, 1996, pp. 341–363
  * [40] Filippo Santambrogio  “Optimal transport for applied mathematicians: Calculus of variations, PDEs, and modeling”  Birkhäuser/Springer, 2015
  * [41] François Septier, Sze Kim Pang, Avishy Carmi and Simon Godsill  “On MCMC-based particle methods for Bayesian filtering: Application to multitarget tracking”  In _2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_ , 2009, pp. 360–363

##  Appendix A Appendix to Section 2

###  A.1 Auxiliary Lemmas

We collect here some technical results which are used throughout our proofs.

######  Lemma A.1.

Let $\mu,\nu\in\mathcal{P}(\mathsf{X})$. We have

$\displaystyle\mathinner{\\!\left\lVert\mu-\nu\right\rVert}_{V}$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\sup_{f\mathrel{\mathop{\mathchar 58\relax}}|f|\leq
V}|\mu(f)-\nu(f)|=(\mu-\nu)_{+}V-(\mu-\nu)_{-}V=\int
V(x)|\mu(x)-\nu(x)|\lambda(dx),$

with the last equality holding only if
$\mu,\nu\in\mathcal{P}_{\lambda}(\mathsf{X})$, and where
$(\mu-\nu)_{+},(\mu-\nu)_{-}$ is the Hahn-Jordan decomposition of $\mu-\nu$.

###### Proof.

This is immediate from the definition, and well known—see, e.g., equation $9$
in [25]. ∎

######  Lemma A.2.

Let $\chi$ be a finite regular signed measure on
$(\mathsf{X},\mathcal{B}(\mathsf{X}))$. If $V$ is a continuously
differentiable $\chi$-integrable function we have

$\mathinner{\\!\left\lVert\chi\right\rVert}_{V}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{f\in\mathbf{B}_{V}(\mathsf{X})}|\chi(f)|=\sup_{f\in\mathbf{C}^{1}_{V}(\mathsf{X})}|\chi(f)|.$

###### Proof.

The inequality
$\sup_{f\in\mathbf{B}_{V}(\mathsf{X})}|\chi(f)|\geq\sup_{f\in\mathbf{C}^{1}_{V}(\mathsf{X})}|\chi(f)|$
is immediate, so we focus on the converse. By Lemma A.1,
$\mathinner{\\!\left\lVert\chi\right\rVert}_{V}=\chi(V1_{\mathsf{X}^{+}})-\chi(V1_{\mathsf{X}^{-}})$,
where $\mathsf{X}=\mathsf{X}^{+}\cup\mathsf{X}^{-}$ is an Hahn decomposition
w.r.t. $\chi$. Thus it suffices to prove that the latter is equal to
$\lim_{r\rightarrow\infty}|\chi(\varphi_{r})|$ for some sequence
$\\{\varphi_{r}\in\mathbf{C}^{1}_{V}(\mathsf{X})\\}_{r\in\mathbb{N}}$ as
$\lim_{r\rightarrow\infty}|\chi(\varphi_{r})|\leq\sup_{f\in\mathbf{C}^{1}_{V}(\mathsf{X})}|\chi(f)|$.
Since $\chi$ is regular, one can find closed sets
$(\tilde{\mathsf{X}}^{+},\tilde{\mathsf{X}}^{-})$ such that
$\chi(1_{\mathsf{X}^{+}\setminus\tilde{\mathsf{X}}^{+}})$ and
$\chi(1_{\mathsf{X}^{-}\setminus\tilde{\mathsf{X}}^{-}})$ are both as small as
we wish. By the integrability of $V$ one then has that for arbitrarily small
$\epsilon>0$, $\chi(V1_{\mathsf{X}^{+}/\tilde{\mathsf{X}}^{+}})<\epsilon/2$
and $\chi(V1_{\mathsf{X}^{-}/\tilde{\mathsf{X}}^{-}})<\epsilon/2$. Recall that
$\varrho$ denotes the (assumed continuously differentiable) metric on
$\mathsf{X}$. Employing the notation $(a)_{+}=\min(1,\max(0,3a^{2}-2a^{3}))$
to denote a Hermite interpolant acting as a smooth, monotonic approximation of
the positive part function on $(-\infty,1]$, we define

$\varphi_{r}^{+}\mathrel{\mathop{\mathchar
58\relax}}=V1_{\tilde{\mathsf{X}}^{+}}+V(1-\varrho(\cdot,\tilde{\mathsf{X}}^{+})/r)_{+}1_{\mathsf{X}/\tilde{\mathsf{X}}^{+}},\quad\varphi_{r}^{-}\mathrel{\mathop{\mathchar
58\relax}}=V1_{\tilde{\mathsf{X}}^{-}}+V(1-\varrho(\cdot,\tilde{\mathsf{X}}^{-})/r)_{+}1_{\mathsf{X}/\tilde{\mathsf{X}}^{-}}$

and $\varphi_{r}\mathrel{\mathop{\mathchar
58\relax}}=\varphi_{r}^{+}-\varphi_{r}^{-}$. In fact,
$\varphi_{r}\in\mathbf{C}^{1}_{V}(\mathsf{X})$ and $\varphi_{r}\rightarrow
V1_{\tilde{\mathsf{X}}^{+}}-V1_{\tilde{\mathsf{X}}^{-}}$ pointwise almost
everywhere as $r\rightarrow\infty$. Therefore
$\chi(\varphi_{r})\rightarrow\chi(V1_{\tilde{\mathsf{X}}^{+}})-\chi(V1_{\tilde{\mathsf{X}}^{-}})$
by dominated convergence and then by choice of
$(\tilde{\mathsf{X}}^{+},\tilde{\mathsf{X}}^{-})$,

$\left|\lim_{r\rightarrow
0}\chi(\varphi_{r})-\mathinner{\\!\left\lVert\chi\right\rVert}_{V}\right|\leq\epsilon.$

We conclude by letting $\epsilon\rightarrow 0$. ∎

###  A.2 Technical conditions in Propositions 2.4 and 2.5

####  A.2.1 Technical conditions in Proposition 2.4.

##### Limit exchange.

To justify the interchange of differentiation and integration performed in
Proposition 2.4 one can simply show that for all
$f\in\mathbf{C}^{1}_{V}(\mathsf{X})$,
$\varphi_{t}(u,w)\mathrel{\mathop{\mathchar
58\relax}}=|(d/dt)f(w)g(r_{\mu_{t}}(u,w))q(u,w)\rho(u)|$ is uniformly bounded
in $t\in[0,1]$ by an $L^{1}(\lambda(du)\otimes\lambda(dw))$ function (e.g.
[29, Theorem 6.28]). Since $|f|\leq V=1$ and $g^{\prime}$ is bounded, say by
$\bar{g}^{\prime}$,

$\displaystyle\varphi_{t}(u,w)$
$\displaystyle=f(w)g^{\prime}(r_{\mu_{t}}(u,w))\frac{|\chi(w)q(w,u)\mu_{t}(u)q(u,w)-\chi(u)q(u,w)\mu_{t}(w)q(w,u)|}{(\mu_{t}(u)q(u,w))^{2}}q(u,w)\rho(u)$
$\displaystyle\leq\bar{g}^{\prime}\frac{|\chi(w)\mu_{t}(u)-\chi(u)\mu_{t}(w)|}{\mu_{t}(u)^{2}}q(w,u)\rho(u)=\bar{g}^{\prime}\frac{|\mu(w)\nu(u)-\mu(u)\nu(w)|}{\mu_{t}(u)^{2}}q(w,u)\rho(u)$
$\displaystyle\leq\bar{g}^{\prime}|\mu(w)\nu(u)+\mu(u)\nu(w)|ab$

where $a\mathrel{\mathop{\mathchar
58\relax}}=\sup_{x,y}q(x,y),b\mathrel{\mathop{\mathchar
58\relax}}=\sup_{x}\rho(x)/\min(\mu(x),\nu(x))^{2}<\infty$ by our assumptions.

##### Uniform continuity of $\partial_{\pi}P_{\mu}(\rho,f)$.

We need to show that for all $\epsilon>0$ there exists a $\delta>0$ such that
for every $\rho,\rho^{\prime}\in\mathcal{A}_{x}$ with
$d_{p}(\rho,\rho^{\prime})<\delta$ we have
$|\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]-\partial_{\pi}P_{\mu}(\rho^{\prime},f)[\nu-\mu]|<\epsilon$.
Let $\rho,\rho^{\prime}\in\mathcal{A}_{x}$, and let $d_{p}$ be the Bounded-
Lipschitz metric [17, Chapter 11]
$d_{p}(\rho,\rho^{\prime})\mathrel{\mathop{\mathchar 58\relax}}=\sup|\int
fd(\rho-\rho^{\prime})|$, the supremum being taken across functions $f$ on
$B(x,r)$ with bounded Lipschitz norm $|f|_{bl}\mathrel{\mathop{\mathchar
58\relax}}=|f|_{l}+\left|f\right|_{\infty}$ no greater than 1, $|f|_{l}$
denoting the Lipschitz seminorm. Notice that for all $\rho\in\mathcal{A}_{x}$
we have $\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]=\rho(h_{1}-h_{2})$, where

$\displaystyle h_{1}(z)\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle\mu(z)^{-1}\int(f(y)-f(z))q(y,z)g^{\prime}(r_{\mu}(z,y))(\nu-\mu)(dy)$
$\displaystyle\textrm{and }h_{2}(z)\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle(\nu-\mu)(z)\mu(z)^{-2}\int(f(z)-f(y))\mu(y)q(y,z)g^{\prime}(r_{\mu}(z,y))\lambda(dy).$

Since $|h_{1}-h_{2}|_{bl}\leq|h_{1}|_{bl}+|h_{2}|_{bl}$, the claim follows
with the choice $\delta=\epsilon/(|h_{1}|_{bl}+|h_{2}|_{bl})$ provided
$h_{1},h_{2}$ have finite bounded Lipschitz norm on $B(x,r)$. Since
$g^{\prime}$ is bounded, and $q,\mu$ are continuous and bounded away from $0$
on the (compact closure of) $B(x,r)$, it follows immediately that both $h_{1}$
and $h_{2}$ are bounded on $B(x,r)$. To show that they are Lipschitz, we show
they are continuously differentiable on $B(x,r)$. Since $\mu,\nu$ are assumed
to be continuously differentiable and $f$ is too, we only need to show that
$z\mapsto\int f(y)q(y,z)g^{\prime}(r_{\mu}(z,y))\mu(dy)$ and $z\mapsto\int
f(y)q(y,z)g^{\prime}(r_{\mu}(z,y))(\nu-\mu)(dy)$ are continuously
differentiable on $B(x,r)$. Whenever the assumed domination condition hold, we
have

$\displaystyle\partial_{z}\int f(y)q(y,z)g^{\prime}(r_{\mu}(z,y))$
$\displaystyle\mu(dy)=\int
f(y)\partial_{z}(q(y,z)g^{\prime}(r_{\mu}(z,y))\mu(dy)$

(e.g. [29, Theorem 6.28]) which is a continuous function of $z$ on $B(x,r)$
too, because the integrand is continuous in $z$ and we have shown above it can
be bounded uniformly in $z$ by a $\mu$-integrable function ([29, Theorem
6.27]). This proves that $z\mapsto\int
f(y)q(y,z)g^{\prime}(r_{\mu}(z,y))\mu(dy)$ is continuously differentiable on
$B(x,r)$. For $z\mapsto\int f(y)q(y,z)g^{\prime}(r_{\mu}(z,y))(\nu-\mu)(dy)$
the proof is analogous.

####  A.2.2 Technical conditions in Proposition 2.5.

##### Limit exchange.

Much as in the proof of uniform continuity above, it suffices to show that for
all $f\in\mathbf{C}_{V}^{1}(\mathsf{X}^{2})$,
$\varphi_{t}(u,w)\mathrel{\mathop{\mathchar
58\relax}}=|(d/dt)f(w_{1},w_{2})P_{1|2,t}(u_{2},w_{1})P_{2|1,t}(w_{1},w_{2})\rho_{2}(u_{2})|$
is uniformly bounded in $t\in[0,1]$ by an
$L^{1}(\lambda(du)\otimes\lambda^{2}(dw))$ function. Write
$\varphi_{t}(u,w)=\varphi_{1,t}(u,w)+\varphi_{2,t}(u,w)$, and compute,
recalling that we take $V=1$:

$\displaystyle\varphi_{1,t}(u,w)$
$\displaystyle=f(w_{1},w_{2})\rho_{2}(u_{2})\frac{|\chi(w_{1},u_{2})\mu_{2,t}(u_{2})-\chi_{2}(u_{2})\mu_{t}(w_{1},u_{2})|}{\mu_{2,t}(u_{2})^{2}}P_{2|1,t}(w_{1},w_{2})$
$\displaystyle\leq\rho_{2}(u_{2})\frac{|\chi(w_{1},u_{2})-\chi_{2}(u_{2})P_{1|2,t}(u_{2},w_{1}))|}{\min(\mu_{2}(u_{2}),\nu_{2}(u_{2}))}P_{2|1,t}(w_{1},w_{2})$
$\displaystyle\leq
b(|\chi(w_{1},u_{2})|+|\chi_{2}(u_{2})|P_{1|2,t}(u_{2},w_{1})))P_{2|1,t}(w_{1},w_{2})$
$\displaystyle\leq
b(|\chi(w_{1},u_{2})|+|\chi_{2}(u_{2})|(P_{1|2,0}(u_{2},w_{1}))+P_{1|2,1}(u_{2},w_{1})))(P_{2|1,0}(w_{1},w_{2})+P_{2|1,1}(w_{1},w_{2}))$
where $b\mathrel{\mathop{\mathchar
58\relax}}=\sup_{x}\rho_{2}(x)/\min(\mu_{2}(x),\nu_{2}(x))<\infty$ by
assumption. To bound $\psi_{2,t}(u,w)$ we use Bayes’ formula to write
$\displaystyle\psi_{2,t}(u,w)$
$\displaystyle=f(w_{1},w_{2})\rho_{2}(u_{2})\frac{\chi(w_{1},w_{2})\mu_{1,t}(w_{1})-\chi_{1}(w_{1})\mu_{t}(w_{1},w_{2})}{\mu_{1,t}(w_{1})^{2}}P_{1|2,t}(u_{2},w_{1})$
$\displaystyle=f(w_{1},w_{2})\rho_{2}(u_{2})\frac{\chi(w_{1},w_{2})\mu_{1,t}(w_{1})-\chi_{1}(w_{1})\mu_{t}(w_{1},w_{2})}{\mu_{1,t}(w_{1})\mu_{2,t}(u_{2})}P_{2|1,t}(w_{1},u_{2})$

and then we proceed as for $\psi_{1,t}(u,w)$.

##### Uniform continuity of $\partial_{\pi}P_{\mu}(\rho,f)$.

This is almost analogous to the proof of Proposition 2.4. We notice that for
all $\rho\in\mathcal{A}_{x}$ we have
$\partial_{\pi}P_{\mu}(\rho,f)[\nu-\mu]=\rho(h_{1}-h_{2}+h_{3}-h_{4})$, where

$\displaystyle h_{1}(z)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\int
f(y_{1},w_{2})\frac{P_{2|1}(y_{1},dw_{2})}{\mu_{2}(z)}(\nu-\mu)(y_{1},z)\lambda(dy_{1}),$
$\displaystyle h_{2}(z)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\int
f(w_{1},w_{2})\frac{P_{1|2}(z,dw_{1})P_{2|1}(w_{1},dw_{2})}{\mu_{2}(z)}(\nu-\mu)(y_{1},z)\lambda(dy_{1}),$
$\displaystyle h_{3}(z)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\int
f(y_{1},y_{2})\frac{P_{1|2}(z,dy_{1})}{\mu_{1}(y_{1})}(\nu-\mu)(y_{1},y_{2})\lambda(dy_{2}),\quad\text{and}$
$\displaystyle h_{4}(z)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\int
f(y_{1},w_{2})\frac{P_{1|2}(z,dy_{1})P_{2|1}(y_{1},dw_{2})}{\mu_{1}(y_{1})}(\nu-\mu)(y_{1},y_{2})\lambda(dy_{2}).$

Hence, following the same reasoning, we just need to show that these functions
are bounded and Lipschitz on $B(x,r)$. Since $\mu$ being continuous, positive
and bounded implies that the marginal densities $\mu_{1},\mu_{2}$ are bounded
away from 0 on $B(x,r)$ and since we assumed that the full conditionals are
upper bounded, we check that
$h_{1}(z),h_{2}(z)\leq(\nu_{2}-\mu_{2})(z)/\mu_{2}(z)$ are in fact bounded, we
then use Bayes’ formula to compute

$\displaystyle h_{3}(z)$ $\displaystyle=\int
f(y_{1},y_{2})\frac{P_{2|1}(y_{1},z)}{\mu_{2}(z)}(\nu-\mu)(y_{1},y_{2})\lambda^{2}(dy),$
$\displaystyle h_{4}(z)$ $\displaystyle=\int
f(y_{1},w_{2})\frac{P_{2|1}(y_{1},z)P_{2|1}(y_{1},dw_{2})}{\mu_{2}(z)}(\nu-\mu)(y_{1},y_{2})\lambda^{2}(dy)$

after which we can use our upper bounds on the full conditionals and lower
bounds on the marginals on $B(x,r)$. To prove they are Lipschitz on $B(x,r)$,
we show again they are continuously differentiable. This follows immediately
using our domination assumption similarly to the proof of Proposition 2.4.

##  Appendix B Appendix to Section 3

Before the proofs of Theorems 3.1 and 3.3 can be given, a number of auxiliary
Lemmas and results are required. We use an approach based on the Poisson
equations and resolvents. For a Markov kernel $P_{\upsilon}$ having $\upsilon$
as invariant measure, the Poisson equation is

$\left\\{\begin{array}[]{rl}(P_{\upsilon}-\textrm{Id})R_{\upsilon}=&\upsilon-\textrm{Id},\\\