# Comparison of Markov chains via weak Poincaré inequalities with application
to pseudo-marginal MCMC

Christophe Andrieu, Anthony Lee, Sam Power, Andi Q. Wang

University of Bristol

###### Abstract

We investigate the use of a certain class of functional inequalities known as
weak Poincaré inequalities to bound convergence of Markov chains to
equilibrium. We show that this enables the straightforward and transparent
derivation of subgeometric convergence bounds for methods such as the
Independent Metropolis–Hastings sampler and pseudo-marginal methods for
intractable likelihoods, the latter being subgeometric in many practical
settings. These results rely on novel quantitative comparison theorems between
Markov chains. Associated proofs are simpler than those relying on
drift/minorization conditions and the tools developed allow us to recover and
further extend known results as particular cases. We are then able to provide
new insights into the practical use of pseudo-marginal algorithms, analyse the
effect of averaging in Approximate Bayesian Computation (ABC) and the use of
products of independent averages, and also to study the case of lognormal
weights relevant to particle marginal Metropolis–Hastings (PMMH).

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Notation
  2. 2 Weak Poincaré inequalities
    1. 2.1 General case
      1. 2.1.1 Definitions and basic results
      2. 2.1.2 Examples of $\beta(s)$ and $\gamma=F_{a}^{-1}$
    2. 2.2 Reversible case
      1. 2.2.1 Simplified weak Poincaré inequality
      2. 2.2.2 Necessity of super-Poincaré inequalities
    3. 2.3 Illustration: Independent MH sampler
      1. 2.3.1 Exponential target and proposal case
      2. 2.3.2 Polynomial target and proposal case
  3. 3 Chaining Poincaré inequalities
  4. 4 Application to pseudo-marginal methods
    1. 4.1 A weak Poincaré inequality for pseudo-marginal chains
    2. 4.2 The effect of averaging
    3. 4.3 ABC example
    4. 4.4 Products of averages
    5. 4.5 Lognormal example
      1. 4.5.1 Tail probabilities and convergence bound
      2. 4.5.2 Mixing times
      3. 4.5.3 Asymptotic variance
  5. A Proofs and other results for Section 2
  6. B Proofs for Section 4

##  1 Introduction

###  1.1 Motivation

The theoretical analysis of Markov chain Monte Carlo (MCMC) algorithms can
provide twofold benefits for users. On the one hand, it provides fundamental
reassurance and theoretical guarantees for the correctness of algorithms, and
on the other hand, can also offer guidance on parameter tuning to maximise
efficacy.

Aside from high-dimensional scaling limit arguments [30], two approaches have
proved particularly successful for characterizing the properties of MCMC
algorithms [4]: Lyapunov drift/minorization conditions [27, 29, 13], and
functional-analytic tools on Hilbert spaces, in particular in the reversible
setup [24, 13, Chapter 22]. The former have been the most successful for the
study of stability and convergence rates, despite the inherent difficulty of
constructing an appropriate Lyapunov function. A particular success has been
the development of tools to analyse the scenario where the Markov transition
kernel does not possess a spectral gap, and hence converges at a subgeometric
rate (see [13] for a book-length treatment). In contrast, functional-analytic
tools have been particularly successful at characterising the resulting
asymptotic variance, but their application to characterising convergence rates
has been limited to the scenario where a spectral gap exists (see [22] for
example). This is despite the existence of functional-analytic tools such as
weak Poincaré or Nash inequalities, which have been successfully applied to
continuous-time Markov processes in the absence of a spectral gap [31].

The aim of this paper is to fill this gap, and show how weak Poincaré
inequalities can be particularly useful for analyzing certain MCMC algorithms
and answering pertinent practical questions. Our main focus here will be on
pseudo-marginal algorithms [2], a particular type of MCMC method for which
pointwise unbiased estimates of the target density are sufficient for their
implementation. We show that weak Poincaré inequalities allow us to
significantly expand and greatly simplify the results of [3], characterising
precisely the degradation in performance incurred when using noisy estimates
of the target density. This is particularly appealing because pseudo-marginal
Markov kernels often do not possess a spectral gap on general state spaces,
either because the noise is unbounded [2, 3] or because the noise is not
uniformly bounded and “local proposals” are used [25], which is fairly common
in practice.

To the best of our knowledge, while Nash inequalities for finite state space
Markov chains have been considered in [11], weak Poincaré inequalities have
not received the same attention in this context and it is not possible to
point to a suitable reference for background. In Section 2 we provide a
comprehensive overview of the theory tailored to the Markov chain scenario;
some of the results given therein are new to the best of our knowledge. In
Section 3 we develop a series of new comparison results between Markov chains
sharing a common invariant distribution. In Section 4 we apply our results to
pseudo-marginal algorithms, providing a simple and comprehensive theory of the
impact of using noisy densities on the convergence properties of pseudo-
marginal algorithms, which we leverage to clarify implementational
considerations. We consider the effect of averaging, with applications to
Approximate Bayesian Computation (ABC) and when using products of independent
averages, and finally provide an analysis when the weights are lognormal,
releveant to the Particle Marginal MH (PMMH). The proofs not appearing in the
main text can be found in the appendices.

###  1.2 Notation

We will write $\mathbb{N}=\\{1,2,\dots\\}$ for the set of natural numbers, and
$\mathbb{R}_{+}=(0,\infty)$ for positive real numbers.

Throughout we will be working on a general measurable space
$(\mathsf{E},\mathcal{F})$.

  * •

For a set $A\in\mathcal{F}$, its complement in $\mathsf{E}$ is denoted by
$A^{\complement}$. We denote the corresponding indicator function by
$\mathbb{I}_{A}:\mathsf{E}\to\\{0,1\\}$.

  * •

We assume $(\mathsf{E},\mathcal{F})$ is equipped with a probability measure
$\mu$, and write $\mathrm{L}^{2}(\mu)$ for the Hilbert space of (equivalence
classes) of real-valued square-integrable measurable functions with inner
product $\langle f,g\rangle=\int_{\mathsf{E}}f(x)g(x)\,\mathrm{d}\mu(x)$ and
corresponding norm $\|\cdot\|_{2}$. We write $\mathrm{L}^{2}_{0}(\mu)$ for the
set of functions $f\in\mathrm{L}^{2}(\mu)$ which also satisfy $\mu(f)=0$.

  * •

More generally, for $p\in[1,\infty)$, we write $\mathrm{L}^{p}(\mu)$ for the
Banach space of real-valued measurable functions with finite $p$-norm,
$\|f\|_{p}:=\left(\int_{\mathsf{E}}|f|^{p}\,\mathrm{d}\mu\right)^{1/p}$, and
$\mathrm{L}_{0}^{p}(\mu)$ for $f\in\mathrm{L}^{p}(\mu)$ with $\mu(f)=0$.

  * •

For a measurable function $f:\mathsf{E}\to\mathbb{R}$, let
$\|f\|_{\mathrm{osc}}:=\mathrm{ess_{\mu}}\sup f-\mathrm{ess}_{\mu}\inf f$.

  * •

For two probability measures $\mu$ and $\nu$ on $(\mathsf{E},\mathcal{F})$ we
let $\mu\otimes\nu(A\times B)=\mu(A)\nu(B)$ for $A,B\in\mathcal{F}$. For a
Markov kernel $P(x,\mathrm{d}y)$ on $\mathsf{E}\times\mathcal{F}$, we write
for $\bar{A}\in\mathcal{F}\times\mathcal{F}$, the product $\sigma$-algebra,
$\mu\otimes P(\bar{A})=\int_{\bar{A}}\mu(\mathrm{d}x)P(x,\mathrm{d}y)$.

  * •

A point mass distribution at $x$ will be denoted by $\delta_{x}(\mathrm{d}y)$.

  * •

$\mathrm{Id}:\mathrm{L}^{2}(\mu)\to\mathrm{L}^{2}(\mu)$ denotes the identity
mapping, $f\mapsto f$.

  * •

Given a bounded linear operator $T:\mathrm{L}^{2}(\mu)\to\mathrm{L}^{2}(\mu)$,
we let $\mathcal{E}(T,f)$ be the Dirichlet form defined by
$\langle(\mathrm{Id}-T)f,f\rangle$ for any $f\in\mathrm{L}^{2}(\mu)$.

  * •

For such an operator $T$, we write $T^{*}$ for its adjoint operator
$T^{*}:\mathrm{L}^{2}(\mu)\to\mathrm{L}^{2}(\mu)$, which satisfies $\langle
f,Tg\rangle=\langle T^{*}f,g\rangle$ for any $f,g\in\mathrm{L}^{2}(\mu)$.

  * •

For such an operator $T$, we denote its spectrum by $\sigma(T)$.

  * •

We will write $a\wedge b$ to mean the (pointwise) minimum of real-valued
functions $a,b$ and $a\vee b$ for the corresponding maximum. For
$s\in\mathbb{R}$, we will write $\left(s\right)_{+}:=s\vee 0$ for the positive
part.

  * •

$\inf A$ denotes the infimum of set $A$ and $\inf\emptyset=\infty$.

##  2 Weak Poincaré inequalities

###  2.1 General case

####  2.1.1 Definitions and basic results

Throughout this work, we will call a _weak Poincaré inequality_ an inequality
of the following form:

######  Definition 1.

(Weak Poincaré inequality.) Given a Markov transition operator $P$ on
$\mathsf{E}$, we will say that _ $P^{*}P$ satisfies a weak Poincaré
inequality_ if for any $f\in\mathrm{L}^{2}_{0}\left(\mu\right)$,

$\displaystyle\|f\|_{2}^{2}$
$\displaystyle\leq\alpha(r)\mathcal{E}(P^{*}P,f)+r\Phi(f),\quad\forall r>0,$

where $\alpha:(0,\infty)\to[0,\infty)$ is a decreasing function, and
$\Phi:\mathrm{L}^{2}(\mu)\to[0,\infty]$ is a functional satisfying for any
$f\in\mathrm{L}^{2}(\mu)$, $c>0$ and $n\in\mathbb{N}$,

$\Phi(cf)=c^{2}\Phi(f),\quad\Phi(P^{n}f)\leq\Phi(f),\quad\|f-\mu(f)\|_{2}^{2}\leq
a\Phi(f-\mu(f)),$ (1)

where
$a:=\sup_{f\in\mathrm{L}^{2}_{0}(\mu)\backslash\\{0\\}}\|f\|_{2}^{2}/\Phi(f)$.

######  Remark 2.

A popular choice of $\Phi$ is $\Phi=\|\cdot\|_{\mathrm{osc}}^{2}$, for which
$a=1$, but we will also later consider $\Phi=\|\cdot\|_{2p}^{2}$ for $p\geq
1$, which also has $a=1$ by Lyapunov’s inequality.

######  Remark 3.

Note that $\alpha(r)$ typically diverges as $r\to 0$. By contrast, a _strong
Poincaré inequality_ refers to the situation when $\alpha$ is uniformly
bounded above by $\alpha(r)\leq 1/C_{\mathrm{P}}$ for some $C_{\mathrm{P}}>0$;
in this case we may take $r\to 0$ and recover the standard strong Poincaré
inequality $C_{\mathrm{P}}\|f\|_{2}^{2}\leq\mathcal{E}(P^{*}P,f)$ for
$f\in\mathrm{L}^{2}_{0}(\mu)$, from which one can immediately deduce geometric
convergence [18], that is for any $f\in\mathrm{L}^{2}_{0}(\mu)$,
$n\in\mathbb{N}$,

$\|P^{n}f\|_{2}^{2}\leq(1-C_{\mathrm{P}})^{n}\|f\|_{2}^{2}.$ (2)

In what follows we show that a weak Poincaré inequality implies the existence
of a decreasing function $s\mapsto\gamma(s)$ such that for any
$f\in\mathrm{L}^{2}_{0}(\mu)$ and $\Phi(f)<\infty$,

$\|P^{n}f\|_{2}^{2}\leq\gamma(n)\Phi(f).$ (3)

An equivalent formulation of the weak Poincaré inequality that will turn out
to be very useful is the following, referred to as the super-Poincaré
inequality in [31].

######  Definition 4.

(Super-Poincaré inequality.) Given a Markov transition operator $P$ on
$\mathsf{E}$, we will say that _$P^{*}P$ satisfies a super-Poincaré
inequality_ if for any $f\in\mathrm{L}^{2}_{0}(\mu)$,

$\|f\|_{2}^{2}\leq s\mathcal{E}(P^{*}P,f)+\beta(s)\Phi(f),\quad\forall s>0,$

where $\beta:(0,\infty)\to[0,\infty)$ is a decreasing function with
$\beta(s)\downarrow 0$ as $s\to\infty$, and
$\Phi:\mathrm{L}^{2}(\mu)\to[0,\infty]$ is a functional satisfying (1) for any
$f\in\mathrm{L}^{2}(\mu)$, $c>0$ and $n\in\mathbb{N}$.

These two formulations are equivalent, as can be checked through routine
manipulations, and we will often refer to either as a weak Poincaré inequality
since this appears to be more common terminology. Because $a$ is such that
$\|f\|_{2}^{2}\leq a\Phi(f)$ for all $f\in\mathrm{L}^{2}_{0}(\mu)$, one can
always take $\beta\leq a$ in Definition 4 and $\alpha(r)=0$ for $r\geq a$ in
Definition 1.

######  Remark 5.

Suppose a weak Poincaré inequality holds for a function $\alpha$ with
$\alpha(r)=0$ for $r\geq a$. Then a super-Poincaré inequality holds with
$\beta(s):=\inf\\{r>0:\alpha(r)\leq s\\}$. Conversely, suppose a super-
Poincaré inequality holds for a function $\beta$ with $\beta\leq a$. Then a
weak Poincaré inequality holds with $\alpha(r):=\inf\\{s>0:\beta(s)\leq r\\}$.
This procedure always returns a right-continuous function, so for a given
$\alpha$ (or $\beta$) satisfying a weak Poincaré inequality (or super-Poincaré
inequality), iterating this procedure will return the right-continuous version
of $\alpha$ (or $\beta$).

While in practice establishing a weak or super-Poincaré inequality is often
the most tractable option, a third (essentially) equivalent formulation plays
an important rôle to establish (3) with optimal rate function $\gamma$. We
need the following functions:

######  Definition 6.

For $\beta$ as in Definition 4 we let

  1. 1.

$K\colon[0,\infty)\rightarrow[0,\infty)$ be such that $K(u):=u\,\beta(1/u)$
for $u>0$ and $K(0):=0$,

  2. 2.

$K^{*}\colon[0,\infty)\rightarrow[0,\infty]$ be such that
$K^{*}(v):=\sup_{u\geq 0}\left\\{uv-K(u)\right\\}$ is the convex conjugate of
$K$.

Then for $f\in\mathrm{L}^{2}_{0}(\mu)$ such that $0<\Phi(f)<\infty$, the
super-Poincaré inequality can be formulated as follows with $u=1/s>0$,

$u\left\|f\right\|_{2}^{2}\leq\mathcal{E}\left(P^{*}P,f\right)+K\left(u\right)\Phi\left(f\right),$

which by rearranging terms and optimising leads to

$K^{*}\left(\frac{\left\|f\right\|_{2}^{2}}{\Phi(f)}\right)\leq\frac{\mathcal{E}(P^{*}P,f)}{\Phi(f)}.$

Relevant properties of $K^{*}$ can be found in Lemma 60. The rate function
$\gamma$ in (3) is the inverse function of $F_{a}$ given below, which is well
defined:

######  Lemma 7.

Let $F_{a}(\cdot)\colon(0,a]\rightarrow\mathbb{R}$, where
$(0,a]\subset\mathrm{D}$, be given by

$F_{a}(x):=\int_{x}^{a}\frac{{\rm d}v}{K^{*}(v)},$

where $K^{*}$ is given in Definition 6 and $\mathrm{D}:=\\{v\geq
0:K^{*}(v)<\infty\\}$. Then $F_{a}(\cdot)$

  1. 1.

is well-defined, convex, continuous and strictly decreasing;

  2. 2.

is such that $\lim_{x\downarrow 0}F_{a}(x)=\infty$ ;

  3. 3.

has a well-defined inverse function $F_{a}^{-1}:(0,\infty)\to(0,a)$, with
$F_{a}^{-1}(x)\to 0$ as $x\to\infty$.

The main result of this section is as follows.

######  Theorem 8.

Assume that $\mu$ and $P^{*}P$ satisfy a super-Poincaré inequality as in
Definition 4. Then for $f\in\mathrm{L}^{2}_{0}(\mu)$ such that
$0<\Phi(f)<\infty$ and any $n\in\mathbb{N}$,

$\|P^{n}f\|_{2}^{2}\leq\Phi(f)F_{a}^{-1}\big{(}n\big{)},$

where $F_{a}\colon(0,a]\rightarrow\mathbb{R}$ is the decreasing convex and
invertible function as in Lemma 7.

######  Remark 9.

When $\int_{a}^{\infty}\frac{\mathrm{d}v}{K^{*}(v)}<\infty$, one can define
$F_{\infty}(x):=\int_{x}^{\infty}\frac{{\rm d}v}{K^{*}(v)}$ for each $x>0$,
and since $F_{a}(x)\leq F_{\infty}(x)$, one can similarly derive a bound
$\|P^{n}f\|_{2}^{2}\leq\Phi(f)F_{\infty}^{-1}\big{(}n\big{)}$.

######  Remark 10.

A different proof relying on an alternative use of the Poincaré inequality is
given in Appendix A for completeness. This corresponds to the formulation of
[31, Theorem 2.1], advocated by the authors for its tractability, but leads to
suboptimal results (see comments in Appendix A). We have found the formulation
of Theorem 8 sufficiently flexible for our applications.

######  Remark 11.

If $P^{*}P$ satisfies a strong Poincaré inequality with constant $C_{{\rm
P}}$, one may take the corresponding $\beta$ to be
$\beta(s)=a\mathbb{I}\\{s\leq C_{{\rm P}}^{-1}\\}$. Conversely, if
$\beta(s)=a\mathbb{I}\\{s\leq C_{{\rm P}}^{-1}\\}$ then one can deduce that a
strong Poincaré inequality holds. A simple calculation shows that
$K^{*}(v)=C_{{\rm P}}v$, for $0\leq v\leq a$, and

$F_{a}(x)=\int_{x}^{a}\frac{{\rm d}v}{C_{{\rm P}}v}{\rm d}v=C_{{\rm
P}}^{-1}\log\left(\frac{a}{x}\right),$

from which we recover an exponential rate. However,
$F_{a}^{-1}(n)=a\exp\big{(}-C_{{\rm P}}n\big{)}$ and since
$\exp\big{(}-C_{{\rm P}}n\big{)}\geq(1-C_{{\rm P}})^{n}$ because
$-x/\sqrt{1-x}\leq\log(1-x)\leq-x$ for $x\in[0,1)$, this suggests a loss
compared to a more direct method leading to (2). In this setting we may also
take $\Phi(f)=\|f\|_{2}^{2}$ and $a=1$.

######  Remark 12.

It is possible to relate convergence in the sense of Theorem 8 to
$\mathrm{L}^{2}(\mu)$ convergence of $\nu(P^{*})^{n}$ and to convergence in
total variation, for some initial distribution $\nu$, where

$\left\|\nu(P^{*})^{n}-\mu\right\|_{2}:=\left\|\frac{{\rm
d}(\nu(P^{*})^{n})}{{\rm d}\mu}-1\right\|_{2},$

bearing in mind that in the reversible case $P^{*}=P$. For any distribution
$\nu\ll\mu$ such that $\Phi\left(\frac{{\rm d}\nu}{{\rm
d}\mu}-1\right)<\infty$, we have

$\displaystyle\|\nu(P^{*})^{n}-\mu\|_{{\rm TV}}$
$\displaystyle=\int\left|\frac{{\rm d}(\nu(P^{*})^{n})}{{\rm
d}\mu}(x)-1\right|{\rm d}\mu(x)$ $\displaystyle\leq\left\|\frac{{\rm
d}(\nu(P^{*})^{n})}{{\rm d}\mu}-1\right\|_{2}$
$\displaystyle=\left\|P^{n}\left(\tfrac{{\rm d}\nu}{{\rm
d}\mu}\right)-1\right\|_{2}$ $\displaystyle\leq\Phi\left(\frac{{\rm
d}\nu}{{\rm d}\mu}-1\right)^{1/2}F_{a}^{-1}(n)^{1/2},$

where the first inequality follows from Jensen’s inequality and the last
equality follows from [13, p. 529]. The condition on $\nu$ is not very
restrictive in practical settings when one can choose $\nu$. For example, if
$\mu$ and $\nu$ have densities with respect to some common reference measure
one can choose $\nu$ to be uniformly distributed on some set on which $\mu$
has a positively lower-bounded density.

A useful lemma we will make use of later concerning linear rescalings is the
following.

######  Lemma 13.

Let $\tilde{\beta}(s):=c_{1}\beta(c_{2}s)$ for $c_{1,}c_{2}>0$. Then
$\tilde{K}^{*}(v):=\sup_{u\in\mathbb{R_{+}}}u[v-\tilde{\beta}(1/u)]=c_{1}c_{2}K^{*}(v/c_{1})$
and when $F_{\infty}(x)$ exists, then the corresponding function
$\tilde{F}_{\infty}^{-1}(x)=c_{1}F_{\infty}^{-1}(c_{2}x)$.

####  2.1.2 Examples of $\beta(s)$ and $\gamma=F_{a}^{-1}$

Throughout the following examples, we use the notation of Theorem 8.

######  Lemma 14.

For $\beta(s)=c_{0}s^{-c_{1}}$,
$K^{*}(v)=C\left(c_{0},c_{1}\right)v^{1+c_{1}^{-1}}$. Then with $F_{\infty}$
as in Remark 9, the convergence rate is bounded by

$F_{\infty}^{-1}(n)\leq c_{0}(1+c_{1})^{1+c_{1}}n^{-c_{1}}.$

######  Lemma 15.

Assume $\beta(s)=\eta_{0}\exp\left(-\eta_{1}s^{\eta_{2}}\right)$ for
$\eta_{0},\eta_{1},\eta_{2}>0$ and choose $a>0$. Then there exist $C>0$,
$0<v_{0}<1\wedge a$ such that for $v\in[0,v_{0}]$,

$K^{*}\left(v\right)\geqslant
Cv\left(\log\left(\frac{1}{v}\right)\right)^{-1/\eta_{2}}.$

In addition, there exists $C^{\prime}>0$ such that for all $n\in\mathbb{N}$,

$F_{a}^{-1}(n)\leq
C^{\prime}\exp\left(-\left(C\frac{1+\eta_{2}}{\eta_{2}}n\right)^{\eta_{2}/(1+\eta_{2})}\right).$

###  2.2 Reversible case

When the kernel $P$ is reversible with respect to $\mu$, we can derive a
simplified weak Poincaré inequality in terms of $P$ directly, rather than
$P^{*}P$, making the approach much more practical. This kind of result seems
to be new, to the best of our knowledge. Furthermore we can also derive a
converse result; a weak Poincaré inequality is necessary for subgeometric
convergence.

####  2.2.1 Simplified weak Poincaré inequality

######  Definition 16.

(Weak Poincaré inequality, super-Poincaré inequality; reversible case.) Given
a reversible Markov transition operator $P$ on $\mathsf{E}$, we will say that
_$P$ satisfies a weak Poincaré inequality_ if for any
$f\in\mathrm{L}^{2}_{0}(\mu)$,

$\|f\|_{2}^{2}\leq\alpha(r)\mathcal{E}(P,f)+r\Phi(f),\quad\forall r>0,$

where $\alpha:(0,\infty)\to[0,\infty)$ is a decreasing function, and
$\Phi:\mathrm{L}^{2}(\mu)\to[0,\infty]$ is a functional satisfying: for any
$f\in\mathrm{L}^{2}(\mu)$, $c>0$ and $n\in\mathbb{N}$,

$\Phi(cf)=c^{2}\Phi(f),\quad\Phi(P^{n}f)\leq\Phi(f),\quad\|f-\mu(f)\|_{2}^{2}\leq
a\Phi(f-\mu(f)),$

with
$a:=\sup_{f\in\mathrm{L}^{2}_{0}(\mu)\backslash\\{0\\}}\|f\|_{2}^{2}/\Phi(f)$.

A _super-Poincaré inequality for $P$_ is analogously defined: for a function
$\beta:(0,\infty)\to[0,\infty)$ decreasing with $\beta(s)\downarrow 0$ as
$s\to\infty$, for any $f\in\mathrm{L}^{2}_{0}(\mu)$,

$\|f\|_{2}^{2}\leq s\mathcal{E}(P,f)+\beta(s)\Phi(f),\quad\forall s>0.$

We are interested now to obtain an appropriate Poincaré inequality for
$P^{*}P=P^{2}$ from a corresponding Poincaré inequality for $P$. The key
complication is the left-hand side of the spectrum, around $-1$. In order to
rule out periodic behaviour (which will prevent convergence), some assumptions
on the spectrum in a neighbourhood of $-1$ are required.

######  Lemma 17.

Suppose that the reversible kernel $P$ possesses a left spectral gap: there
exists some $0<c_{\mathrm{gap}}\leq 1$ such that the spectrum of $P$ is
bounded below:

$\inf\sigma(P)\geq-1+c_{\mathrm{gap}}.$

Then we obtain the bound on the Dirichlet forms given
$f\in\mathrm{L}^{2}(\mu)$ by

$\mathcal{E}(P^{2},f)\geq c_{\mathrm{gap}}\mathcal{E}(P,f).$

######  Corollary 18.

In the setting of Lemma 17, it immediately follows that if $P$ satisfies a
super-Poincaré inequality with function $\beta$ as in Definition 16, $P^{2}$
satisfies a super-Poincaré inequality with $\tilde{\beta}$ given by
$\tilde{\beta}(s):=\beta(c_{\mathrm{gap}}s)$:

$\|f\|_{2}^{2}\leq s\mathcal{E}(P^{2},f)+\tilde{\beta}(s)\Phi(f)\quad,\forall
s>0.$

Thus the convergence rate $\tilde{F}_{a}^{-1}$ for $\|P^{n}f\|_{2}^{2}$ can be
immediately deduced from Theorem 8 and Lemma 13.

Recall that a $\mu$-reversible Markov kernel $P$ is _positive_ if for any
$f\in\mathrm{L}^{2}(\mu)$, $\langle Pf,f\rangle\geq 0$, and a positive
reversible kernel $P$ has spectrum contained in the nonnegative interval
$\sigma(P)\subset[0,1]$. When $P$ is reversible and positive, convergence of
$P^{n}$ can be straightforwardly derived as then $c_{{\rm gap}}=1$.

######  Theorem 19.

Assume that the kernel $P$ is reversible and positive and satisfies a super-
Poincaré inequality as in Definition 16. Then Theorem 8 applies, so for
$f\in\mathrm{L}^{2}_{0}(\mu)$ such that $0<\Phi(f)<\infty$ and any
$n\in\mathbb{N}$,

$\|P^{n}f\|_{2}^{2}\leq\Phi(f)F_{a}^{-1}\big{(}n\big{)}.$

###### Proof.

Since $P$ is reversible and positive, we can apply Corollary 18 with
$c_{\mathrm{gap}}=1$ to see that $P^{2}$ satisfies a super-Poincaré inequality
with the same function $\beta$. We can then immediately apply Theorem 8 to
conclude. ∎

######  Remark 20.

Realistic MCMC kernels will all possess a non-zero left spectral gap. Indeed,
popular methods such as the Independent Metropolis–Hastings sampler, many
random walk Metropolis algorithms, and the resulting pseudo-marginal chains we
will consider later are even positive [3, Proposition 16]. Furthermore, a
given reversible kernel $P$ can be straightforwardly modified to possess a
positive left spectral gap by considering the so-called lazy chain
$Q:=\epsilon\mathrm{Id}+(1-\epsilon)P$ for $\epsilon\in[0,1)$. Indeed, one of
our contributions in Section 3 is to generalize this construction and give
versions of Lemma 17 and Corollary 18 holding under weaker assumptions; see
Theorem 38.

####  2.2.2 Necessity of super-Poincaré inequalities

We can also derive a converse to Theorem 8 in the reversible setting. For our
explicit examples of $\beta$ in Section 2.1.2 as well as in the geometric case
(Remark 3), it turns out that we can derive a sharp converse result, thus
demonstrating, at least in the reversible setting, that our approach is able
to recover the best possible rates of convergence for a given $\beta$; see
Remark 22.

######  Proposition 21.

Let $P$ be $\mu-$self-adjoint Markov transition operator and assume for any
$n\in\mathbb{N}$, and $f\in\mathrm{L}^{2}_{0}(\mu)$,

$\|P^{n}f\|_{2}^{2}\leq\gamma(n)\Phi(f),$ (4)

for some functional $\Phi:\mathrm{L}^{2}(\mu)\to[0,\infty]$ satisfying (1) and
a decreasing function $\gamma:\mathbb{R}_{+}\to(0,\infty)$, with $\gamma(s)\to
0$ as $s\to\infty$. Then $P^{2}$ satisfies a super-Poincaré inequality
(Definition 4) with

$\beta\left(s\right)\leqslant\beta_{1}\left(s\right):=\sup_{t\geqslant
s}\inf_{n\geq
2}\left\\{\frac{t^{n}}{\left(t-1\right)^{n-1}}\cdot\frac{\left(n-1\right)^{n-1}}{n^{n}}\cdot\gamma\left(n\right)\right\\},\quad\forall
s>1,$

which is decreasing and decreases to $0$.

######  Remark 22.

For explicit computations, it can be useful to apply the elementary bounds

$\frac{s^{n}}{\left(s-1\right)^{n-1}}=\left(s-1\right)\cdot\left(\frac{s}{s-1}\right)^{n}\leqslant\left(s-1\right)\cdot\exp\left(\frac{n}{s-1}\right),$

and

$\frac{\left(n-1\right)^{n-1}}{n^{n}}=\frac{1}{n}\cdot\left(\frac{n-1}{n}\right)^{n-1}\leqslant\frac{1}{2n},$

to bound

$\inf_{n\geq
2}\left\\{\frac{s^{n}}{\left(s-1\right)^{n-1}}\cdot\frac{\left(n-1\right)^{n-1}}{n^{n}}\cdot\gamma\left(n\right)\right\\}\\\
\leqslant\frac{1}{2}\cdot\inf_{n\geq
2}\left\\{\gamma\left(n\right)\left(\frac{n}{s-1}\right)^{-1}\cdot\exp\left(\frac{n}{s-1}\right)\right\\}\\\
\leqslant\frac{1}{2}\cdot\sup_{t\geqslant s}\inf_{n\geq
2}\left\\{\gamma\left(n\right)\left(\frac{n}{t-1}\right)^{-1}\cdot\exp\left(\frac{n}{t-1}\right)\right\\}=:\beta_{2}\left(s\right),$

which is often more convenient to work with, and is again decreasing and
decreases to $0$.

By using the upper bounds on $\beta$ which are supplied by the proof (see
Appendix A), it is possible recover estimates on the decay of
$\left\|P^{n}f\right\|_{2}$ which are sharp (up to constant factors) in all of
our explicit examples. We do not address whether this will hold in general.

###  2.3 Illustration: Independent MH sampler

As a concrete illustration of the results of Subsection 2.2 we consider the
Independent Metropolis–Hastings (IMH) algorithm. This has been studied
previously in [20, 21] using drift/minorization conditions, and we show in
this subsection that we recover the same subgeometric rates of convergence
using super-Poincaré inequalities. We fix a target density $\pi$ and a
positive proposal density $q$ on $\mathsf{E}$ and define

$w(x):=\frac{\pi(x)}{q(x)},\quad x\in\mathsf{E}.$

Then the IMH chain has reversible transition kernel $P$ given by

$P(x,\mathrm{d}y)=a(x,y)q(y)\mathrm{d}y+\rho(x)\delta_{x}(\mathrm{d}y),$

where $a(x,y)=\left[1\wedge\frac{w(y)}{w(x)}\right]$, and
$\rho(x)=\int\left[1-a(x,y)\right]\,q(\mathrm{d}y)$. In this case, it follows
from reversibility that we have the following well-known representation:

######  Lemma 23.

We can express

$\mathcal{E}(P,f)=\frac{1}{2}\int\pi(x)\pi(y)\left(w^{-1}(x)\wedge
w^{-1}(y)\right)\left[f(y)-f(x)\right]^{2}\,\mathrm{d}x\,\mathrm{d}y,$

and

$\|f\|_{2}^{2}=\frac{1}{2}\int\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}\,\mathrm{d}x\,\mathrm{d}y.$

For the IMH, the following is known [20, 21]:

######  Proposition 24.

If $w$ is uniformly bounded from above, then the IMH sampler is uniformly
ergodic. However, if $w$ is not uniformly bounded above, then the chain is not
even geometrically ergodic.

Thus since we are interested in the case of subgeometric convergence, we
assume that $w$ is not bounded from above, or equivalently, $w^{-1}$ is not
bounded from below by any positive constant. Thus given any $s>0$, we define
the following sets:

$A(s):=\left\\{(x,y)\in\mathsf{E}\times\mathsf{E}:w^{-1}(x)\wedge
w^{-1}(y)\geq 1/s\right\\}.$

Since we are assuming the subgeometric case, there is no $s>0$ for which
$A(s)=\mathsf{E}\times\mathsf{E}$.

######  Proposition 25.

For the IMH, we have the following super-Poincaré inequality: given any
$f\in\mathrm{L}^{2}_{0}(\pi)$ and $s>0$,

$\|f\|_{2}^{2}\leq
s\mathcal{E}(P,f)+\frac{\pi\otimes\pi(A(s)^{\complement})}{2}\|f\|_{\mathrm{osc}}^{2}.$

###### Proof.

We compute directly:

$\displaystyle\|f\|_{2}^{2}$
$\displaystyle=\frac{1}{2}\int_{\mathsf{E}\times\mathsf{E}}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}$
$\displaystyle=\frac{1}{2}\int_{A(s)}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}$
$\displaystyle\quad+\frac{1}{2}\int_{A(s)^{\complement}}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}$
$\displaystyle\leq\frac{s}{2}\int_{A(s)}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left(w^{-1}(x)\wedge
w^{-1}(y)\right)\left[f(y)-f(x)\right]^{2}$
$\displaystyle\quad+\frac{1}{2}\int_{A(s)^{\complement}}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}$
$\displaystyle=\frac{s}{2}\int_{\mathsf{E}\times\mathsf{E}}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left(w^{-1}(x)\wedge
w^{-1}(y)\right)\left[f(y)-f(x)\right]^{2}$
$\displaystyle\quad+\frac{1}{2}\int_{A(s)^{\complement}}\mathrm{d}x\,\mathrm{d}y\,\pi(x)\pi(y)\left[f(y)-f(x)\right]^{2}\left(1-s\left(w^{-1}(x)\wedge
w^{-1}(y)\right)\right)$ $\displaystyle\leq
s\mathcal{E}(P,f)+\frac{\pi\otimes\pi(A(s)^{\complement})}{2}\|f\|_{\mathrm{osc}}^{2}.$

∎

Our bound in Proposition 25 allows us to directly link the tail properties of
the weights $w(x)$ under $\pi$ and the resulting rates of subgeometric
convergence. We can apply Theorem 19, since the IMH kernel is always positive
[17].

######  Remark 26.

Using this approach we recover convergence rates identical to those obtained
using drift/minorization conditions [20, 15]. Notice that
$\pi\otimes\pi(A(s)^{\complement})\leq 2\pi\big{(}w(X)\geq s\big{)}$,
suggesting the use of Markov’s inequality followed by the application of
Lemmas 14–15 to obtain upper bounds on the rate of convergence of the IMH
algorithm for the total variation distance (Remark 12). In the scenario where
$\mathbb{E}_{\pi}\left[w(X)^{\eta}\right]<\infty$ with $\eta>1$ it is possible
to determine a drift condition for the IMH algorithm (see for example [20,
Theorem 5.3], [21, Proposition 9]), and deduce a rate of $n^{-\eta}$. This is
the same as can be obtained using our Lemma 14; see also our examples below.
Similarly, when
$\mathbb{E}_{\pi}\left[\exp\left(w(X)^{\eta}\right)\right]<\infty$ it is
possible to identify a drift condition [3, Lemma 56] for the algorithm and
deduce the existence of $C_{1},C_{2}>0$ such that the total variation
convergence rate is bounded [15, p. 1365] by

$C_{1}n^{1/(1+\eta)}\exp\left(-\left\\{C_{2}\frac{1+\eta}{\eta}n\right\\}{}^{\eta/(1+\eta)}\right),$

which is consistent with our result in Lemma 15, except for the polynomial
term. However we note that it is not possible to derive the precise value of
the constant $C_{2}$ and cannot therefore conclude which of the two approaches
provides the fastest rate.

We turn now to some concrete examples inspired by [20, 21] where $\beta(s)$
can be evaluated directly.

####  2.3.1 Exponential target and proposal case

We work on $\mathsf{E}=(0,\infty)\subset\mathbb{R}$, and have target and
proposal densities

$\pi(x)=a_{1}\exp(-a_{1}x),\quad q(x)=a_{2}\exp(-a_{2}x).$

Since we are interested in the subgeometric case, we assume that
$a_{2}>a_{1}.$ For this example, it was shown in [21, Proposition 9(b)] that
there is polynomial convergence, with rate at least $a_{1}/(a_{2}-a_{1})$.

######  Lemma 27.

We have that for $s\geq 1$,

$\frac{\pi\otimes\pi(A(s)^{\complement})}{2}=\frac{1}{2}\left[1-\left(1-s^{-\frac{a_{1}}{a_{2}-a_{1}}}\right)^{2}\right]\leq
s^{{}^{-\frac{a_{1}}{a_{2}-a_{1}}}}.$

In this case, we can make use of Lemma 14 to conclude the following,
consistent with [21, Proposition 9(b)].

######  Proposition 28.

For our exponential example, we recover the convergence rate for some $C>0$,

$\|P^{n}f\|_{2}^{2}\leq
C\|f\|_{\mathrm{osc}}^{2}n^{-\frac{a_{1}}{a_{2}-a_{1}}}.$

####  2.3.2 Polynomial target and proposal case

We take $\mathsf{E}=[1,\infty)\subset\mathbb{R}$, and target and proposal
densities

$\pi(x)=\frac{b_{1}}{x^{1+b_{1}}},\quad q(x)=\frac{b_{2}}{x^{1+b_{2}}}.$

We are interested in subgeometric convergence, so assume that $b_{2}>b_{1}.$
It was shown in [21, Proposition 9(a)] that for this example there is
polynomial convergence with rate at least $b_{1}/(b_{2}-b_{1})$. An entirely
analogous calculation to the exponential example above allows us to conclude:

######  Proposition 29.

For our polynomial example, we obtain the convergence rate, for some $C>0,$

$\|P^{n}f\|_{2}^{2}\leq
C\|f\|_{\mathrm{osc}}^{2}n^{-\frac{b_{1}}{b_{2}-b_{1}}}.$

##  3 Chaining Poincaré inequalities

In this section we show how comparison of Dirichlet forms can be used to
deduce convergence properties of a given Markov chain from another one. These
results extend existing quantitative comparison results.

######  Proposition 30.

Let $P_{1}$ and $P_{2}$ be two $\mu-$invariant Markov kernels. Let
$T_{i}=P_{i}$ or $T_{i}=P_{i}^{*}P_{i}$. Assume that for all $s>0$ and
$f\in\mathrm{L}^{2}_{0}(\mu)$,

$\displaystyle C_{\mathrm{P}}\|f\|_{2}^{2}$
$\displaystyle\leq\mathcal{E}(T_{1},f)$ $\displaystyle\mathcal{E}(T_{1},f)$
$\displaystyle\leq s\mathcal{E}(T_{2},f)+\beta^{\prime}(s)\Phi(f),$

where

  1. 1.

$C_{\mathrm{P}}>0$ and $\beta^{\prime}\colon(0,\infty)\rightarrow(0,\infty)$
is decreasing and $\beta^{\prime}(s)\downarrow 0$ as $s\to\infty$,

  2. 2.

$\Phi\colon\mathrm{L}^{2}(\mu)\rightarrow[0,\infty]$ is such that (1) holds.

Then for any $s>0$,

$\|f\|_{2}^{2}\leq s\mathcal{E}(T_{2},f)+\beta(s)\Phi(f),$

with $\beta(s)=\beta^{\prime}(C_{\mathrm{P}}s)/C_{{\rm P}}$.

The proof is immediate.

######  Remark 31.

This generalises the comparison of Dirichlet forms used in [7] which
corresponds to $\beta(s)=0$ for all $s>\bar{s}$ for some $\bar{s}>0$. Further,
assume that for any $(x,A)\in\mathsf{E}\times\mathcal{F}$,
$P_{2}(x,A\setminus\\{x\\})\geq\varepsilon(x)P_{1}(x,A\setminus\\{x\\})$ for
some $\varepsilon\colon\mathsf{E}\rightarrow(0,1]$, then with
$\left\\{(x,y)\in\mathsf{E}^{2}\colon\varepsilon(x)s>1\right\\}$ and $s>0$ we
have

$\displaystyle\mathcal{E}(P_{1},f)$
$\displaystyle\leq\frac{1}{2}\int_{A(s)}\varepsilon(x)s\mu({\rm
d}x)P_{1}(x,{\rm d}y)\left[f(y)-f(x)\right]^{2}$ $\displaystyle\hskip
113.81102pt+\frac{1}{2}\int_{A(s)^{\complement}}\mu({\rm d}x)P_{1}(x,{\rm
d}y)\left[f(y)-f(x)\right]^{2}$ $\displaystyle\leq
s\mathcal{E}(P_{2},f)+\frac{1}{2}\mu\left(\varepsilon^{-1}(X)\geq
s\right)\|f\|_{{\rm osc}}^{2},$

which is a generalisation of [7, Theorem A3] and together with Theorem 19
leads to a counterpart of [7, Theorem A1] for rates of convergence. However,
we have not found an elegant generalisation of [7, Theorem A2] concerned with
asymptotic variances. Theorem 36 further generalizes these comparison ideas.

This can be further extended to the scenario where $T_{1}$ satisfies a weak
Poincaré inequality.

######  Proposition 32.

Let $P_{1}$ and $P_{2}$ be two $\mu-$invariant Markov kernels. Let
$T_{i}=P_{i}$ or $T_{i}=P_{i}^{*}P_{i}$. Assume that for all $s>0$ and
$f\in\mathrm{L}^{2}_{0}(\mu)$,

$\displaystyle\|f\|_{2}^{2}$ $\displaystyle\leq
s\mathcal{E}(T_{1},f)+\beta_{1}(s)\Phi_{1}(f)$
$\displaystyle\mathcal{E}(T_{1},f)$ $\displaystyle\leq
s\mathcal{E}(T_{2},f)+\beta_{2}(s)\Phi_{2}(f),$ (5)

where

  1. 1.

$\beta_{1},\beta_{2}\colon(0,\infty)\rightarrow(0,\infty)$ are decreasing and
$\beta_{1}(s),\beta_{2}(s)\downarrow 0$ as $s\to\infty$,

  2. 2.

$\Phi_{1},\Phi_{2}\colon\mathrm{L}^{2}(\mu)\rightarrow[0,\infty]$ are such
that (1) hold for $P_{1}$ and $P_{2}$ respectively,

  3. 3.

for any $n\in\mathbb{N}$ and $f\in\mathrm{L}^{2}_{0}(\mu)$,
$\Phi_{1}(P_{2}^{n}f)\leq\Phi_{1}(f)$.

Then for any $s>0$,

$\|f\|_{2}^{2}\leq s\mathcal{E}(T_{2},f)+\beta(s)\Phi(f),$ (6)

where $\Phi:=\Phi_{1}\vee\Phi_{2}$ and

$\beta(s):=\inf\left\\{s_{1}\beta_{2}(s_{2})+\beta_{1}(s_{1})\,|s_{1}>0,s_{2}>0,s_{1}s_{2}=s\right\\}.$

Furthermore, $\beta:(0,\infty)\to(0,\infty)$ is monotone decreasing and
satisfies $\beta(s)\downarrow 0$ as $s\to\infty$, $\Phi(cf)=c^{2}\Phi(f)$ for
$c>0$ and $\Phi(P_{2}^{n}f)\leq\Phi(f)$ for any $n\in\mathbb{N}$ and
$f\in\mathrm{L}^{2}_{0}(\mu)$.

Additionally, writing $K_{i}\left(u\right)=u\cdot\beta_{i}\left(1/u\right)$,
$K\left(u\right)=u\cdot\beta\left(1/u\right)$, it holds that

$\displaystyle K\left(u\right)$
$\displaystyle=\inf\left\\{K_{2}(u_{2})+u_{2}K_{1}(u_{1})\,|u_{1}>0,u_{2}>0,u_{1}u_{2}=u\right\\},$
$\displaystyle K^{*}\left(v\right)$ $\displaystyle=K_{2}^{*}\circ
K_{1}^{*}\left(v\right).$

###### Proof.

Fix $s>0$. Given any $s_{1},s_{2}>0$ with $s_{1}s_{2}=s$, by direct
substitution in (5), we can arrive at

$\displaystyle\|f\|_{2}^{2}$ $\displaystyle\leq
s\mathcal{E}(T_{2},f)+\beta_{1}(s_{1})\Phi_{1}(f)+s_{1}\beta_{2}(s_{2})\Phi_{2}(f)$
$\displaystyle\leq
s\mathcal{E}(T_{2},f)+\left[\beta_{1}(s_{1})+s_{1}\beta_{2}(s_{2})\right]\left[\Phi_{1}(f)\vee\Phi_{2}(f)\right].$

Taking an infimum, we arrive at (6).

Now we prove the monotonicity of $\beta$. Fix some $s>0$ and any
$s_{1},s_{2}>0$ with $s_{1}s_{2}=s$. Given any $s^{\prime}\geq s$, note that

$\displaystyle\beta(s^{\prime})$ $\displaystyle\leq
s_{1}\beta_{2}(s^{\prime}/s_{1})+\beta_{1}(s_{1})$ $\displaystyle\leq
s_{1}\beta_{2}(s/s_{1})+\beta_{1}(s_{1})$
$\displaystyle=s_{1}\beta_{2}(s_{2})+\beta_{1}(s_{1}).$

Here we made use of the fact that $\beta_{2}$ is a decreasing function. Taking
an infimum over $s_{1},s_{2}$, we conclude that
$\beta(s^{\prime})\leq\beta(s)$.

We now show that given $\epsilon>0$, we can find $s>0$ such that
$\beta(s)\leq\epsilon$. Combined with monotonicity, this proves that
$\beta(s)\downarrow 0$ as $s\to\infty$. So fix $\epsilon>0$. Choose $s_{1}>0$
such that $\beta_{1}(s_{1})\leq\epsilon/2$, which can be done since
$\beta_{1}(s)\downarrow 0$ as $s\to\infty$. Given such an $s_{1}$, now choose
$s_{2}>0$ large enough so that $s_{1}\beta_{2}(s_{2})\leq\epsilon/2$. Thus for
$s:=s_{1}s_{2}$ for these choices of $s_{1},s_{2}$, we have shown that
$\beta(s)\leq\epsilon/2+\epsilon/2=\epsilon$.

To complete the proof, write

$\displaystyle K\left(u\right)$ $\displaystyle=u\cdot\beta\left(1/u\right)$
$\displaystyle=u\cdot\inf\left\\{s_{1}\beta_{2}(s_{2})+\beta_{1}(s_{1})\,|s_{1}>0,s_{2}>0,s_{1}s_{2}=1/u\right\\}$
$\displaystyle=u\cdot\inf\left\\{\left(1/u_{1}\right)\cdot\beta_{2}(1/u_{2})+\beta_{1}(1/u_{1})\,|1/u_{1}>0,1/u_{2}>0,\left(1/u_{1}\right)\cdot\left(1/u_{2}\right)=1/u\right\\}$
$\displaystyle=\inf\left\\{\left(u/u_{1}\right)\cdot\beta_{2}(1/u_{2})+\left(u_{1}u_{2}\right)\cdot\beta_{1}(1/u_{1})\,|u_{1}>0,u_{2}>0,u_{1}u_{2}=u\right\\}$
$\displaystyle=\inf\left\\{u_{2}\beta_{2}(1/u_{2})+u_{2}\cdot
u_{1}\beta_{1}(1/u_{1})\,|u_{1}>0,u_{2}>0,u_{1}u_{2}=u\right\\}$
$\displaystyle=\inf\left\\{K_{2}\left(u_{2}\right)+u_{2}\cdot
K_{1}\left(u_{1}\right)\,|u_{1}>0,u_{2}>0,u_{1}u_{2}=u\right\\},$

as claimed. Finally,

$\displaystyle K^{*}\left(v\right)$ $\displaystyle:=\sup_{u\geqslant
0}\left\\{uv-K\left(u\right)\right\\}$ $\displaystyle=\sup_{u\geqslant
0}\left\\{uv-\inf_{u_{1},u_{2}}\left\\{K_{2}\left(u_{2}\right)+u_{2}\cdot
K_{1}\left(u_{1}\right)\right\\}\right\\}$
$\displaystyle=\sup_{u,u_{1},u_{2}}\left\\{uv-
K_{2}\left(u_{2}\right)-u_{2}\cdot K_{1}\left(u_{1}\right)\right\\},$

where $u_{1,}u_{2}$ are again constrained to be non-negative and have their
product equal to $u$. Now, rewrite $u=u_{1}u_{2}$ and eliminate the variable
$u$ to write

$\displaystyle K^{*}\left(v\right)$
$\displaystyle=\sup_{u_{1},u_{2}>0}\left\\{u_{1}u_{2}v-K_{2}\left(u_{2}\right)-u_{2}\cdot
K_{1}\left(u_{1}\right)\right\\}$
$\displaystyle=\sup_{u_{1},u_{2}>0}\left\\{u_{2}\cdot\left\\{u_{1}v-K_{1}\left(u_{1}\right)\right\\}v-K_{2}\left(u_{2}\right)\right\\}$
$\displaystyle=\sup_{u_{2}>0}\left\\{u_{2}\cdot\sup_{u_{1}>0}\left\\{u_{1}v-K_{1}\left(u_{1}\right)\right\\}-K_{2}\left(u_{2}\right)\right\\}.$

Taking the inner supremum simplifies this expression to

$K^{*}\left(v\right)=\sup_{u_{2}>0}\left\\{u_{2}\cdot
K_{1}^{*}\left(v\right)-K_{2}\left(u_{2}\right)\right\\},$

and taking the remaining supremum allows us to conclude that
$K^{*}\left(v\right)=K_{2}^{*}\left(w\right)$ with $w=K_{1}^{*}\left(v\right)$
as claimed, i.e. $K^{*}=K_{2}^{*}\circ K_{1}^{*}$. ∎

######  Example 33.

If one has $\beta_{i}\left(s\right)=c_{i}s^{-\alpha_{i}}$ for $i\in\\{1,2\\}$,
then $\beta(s)\propto s^{-\alpha_{*}}$ with
$\alpha_{*}=\frac{\alpha_{1}\alpha_{2}}{1+\alpha_{1}+\alpha_{2}}$. To see
this, write

$\displaystyle\beta(s)$
$\displaystyle:=\inf\left\\{s_{1}\beta_{2}(s_{2})+\beta_{1}(s_{1})\,|s_{1}>0,s_{2}>0,s_{1}s_{2}=s\right\\}$
$\displaystyle=\inf\left\\{c_{2}s_{1}s_{2}^{-\alpha_{2}}+c_{1}s_{1}^{-\alpha_{1}}\,|s_{1}>0,s_{2}>0,s_{1}s_{2}=s\right\\}$
$\displaystyle=\inf\left\\{c_{2}s_{1}\left(\frac{s_{1}}{s}\right)^{\alpha_{2}}+c_{1}s_{1}^{-\alpha_{1}}\,|s_{1}>0\right\\}$
$\displaystyle=\inf\left\\{c_{2}s^{-\alpha_{2}}s_{1}^{1+\alpha_{2}}+c_{1}s_{1}^{-\alpha_{1}}\,|s_{1}>0\right\\}.$

Taking derivatives and solving for a stationary point gives
$\hat{s}_{1}=\frac{c_{1}\alpha_{1}}{c_{2}\left(1+\alpha_{2}\right)}s^{\frac{\alpha_{2}}{1+\alpha_{1}+\alpha_{2}}}$,
from which point routine algebraic manipulations confirm the conclusion.

Our next main result is Theorem 36, which provides us with a practical way of
establishing (5) for $T_{i}=P_{i}$. We first establish an intermediate result.

######  Proposition 34.

Let $P$ be a $\mu$-invariant Markov kernel, and let
$A\in\mathcal{F}\otimes\mathcal{F}$. Let $p\in(1,\infty],q\geq 1$ satisfy
$p^{-1}+q^{-1}=1$. Then, one can bound for $f\in\mathrm{L}^{2}(\mu)$,

$\int_{A}\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\left(f\left(x\right)-f\left(y\right)\right)^{2}\leqslant\mu\otimes
P\big{(}A\cap\\{X\neq Y\\}\big{)}^{1/q}\cdot\Phi_{p}\left(f\right),$

with $\Phi_{p}$ given by

$\Phi_{p}(f):=\begin{cases}4\|f\|_{2p}^{2}&p\in(1,\infty)\\\
\|f\|_{\mathrm{osc}}^{2}&p=\infty\end{cases}.$ (7)

Moreover, it holds that for all $f\in\mathrm{L}^{2}(\mu)$ and
$p\in[1,\infty]$, $\Phi_{p}\left(Pf\right)\leqslant\Phi_{p}\left(f\right)$.

###### Proof.

For $p\in(1,\infty)$, we use Hölder’s inequality to write,

$\displaystyle\int_{A}\mu\left(\mathrm{d}x\right)$ $\displaystyle
P\left(x,\mathrm{d}y\right)\left(f\left(x\right)-f\left(y\right)\right)^{2}$
$\displaystyle=$
$\displaystyle\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\left\\{\mathbb{I}_{A\cap\\{x\neq
y\\}}(x,y)\cdot\left(f\left(x\right)-f\left(y\right)\right)^{2}\right\\}$
$\displaystyle\leqslant$
$\displaystyle\left(\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\mathbb{I}_{A\cap\\{x\neq
y\\}}(x,y)\right)^{1/q}\cdot\left(\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\left|f\left(x\right)-f\left(y\right)\right|^{2p}\right)^{1/p}.$

By Jensen’s inequality, one can check that
$\left|f\left(x\right)-f\left(y\right)\right|^{2p}\leqslant
2^{2p-1}\cdot\left(\left|f\left(x\right)\right|^{2p}+\left|f\left(y\right)\right|^{2p}\right)$.
Because $\mu P=\mu$,

$\displaystyle\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\left|f\left(x\right)-f\left(y\right)\right|^{2p}$
$\displaystyle\leqslant
2^{2p-1}\cdot\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\cdot\left(\left|f\left(x\right)\right|^{2p}+\left|f\left(y\right)\right|^{2p}\right)$
$\displaystyle=2^{2p}\cdot\|f\|_{2p}^{2p}.$

One then concludes that

$\displaystyle\int_{A}\mu\left({\rm
d}x\right)P\left(x,\mathrm{d}y\right)\left(f\left(x\right)-f\left(y\right)\right)^{2}$
$\displaystyle\leqslant\mu\otimes
P\left(A\right)^{1/q}\cdot\left(2^{2p}\cdot\|f\|_{2p}^{2p}\right)^{1/p}$
$\displaystyle=\mu\otimes P\left(A\right)^{1/q}\cdot\Phi\left(f\right),$

as desired. The non-expansivity of $\Phi$ under the action of $P$ can be
deduced by writing

$\displaystyle\|Pf\|_{2p}^{2p}$
$\displaystyle=\int\mu\left(\mathrm{d}x\right)\left|Pf\left(x\right)\right|^{2p}$
$\displaystyle=\int\mu\left(\mathrm{d}x\right)\left|\int
P\left(x,\mathrm{d}y\right)f\left(y\right)\right|^{2p}$
$\displaystyle\leqslant\int\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)\left|f\left(y\right)\right|^{2p}$
$\displaystyle=\int\mu\left(\mathrm{d}y\right)\left|f\left(y\right)\right|^{2p}$
$\displaystyle=\|f\|_{2p}^{2p},$

where the inequality uses Jensen’s inequality against the probability measure
$P\left(x,\cdot\right)$, and the penultimate equality uses the
$\mu$-invariance of $P$.

When $p=\infty$, we use an analogous argument, noting that
$\left(f\left(x\right)-f\left(y\right)\right)^{2}\leq\|f\|_{\mathrm{osc}}^{2}$.
∎

######  Remark 35.

In fact, given the invariance of the original integral under shifts of the
form $f\leftarrow f+c$, one can always refine the above estimate to

$\int_{A}\mu\left(dx\right)P\left(x,{\rm
d}y\right)\left(f\left(x\right)-f\left(y\right)\right)^{2}\leqslant\mu\otimes
P\left(A\right)^{1/q}\cdot\tilde{\Phi}\left(f\right),$

where

$\tilde{\Phi}\left(f\right):=\inf_{m\in\mathbb{R}}\left\\{\Phi\left(f-m\right)\right\\}.$

One can also verify that $\tilde{\Phi}$ is non-expansive under the action of
$P$ by noting that $P\left(f-m\right)=Pf-m$, and hence that

$\displaystyle\tilde{\Phi}\left(Pf\right)$
$\displaystyle=\inf_{m\in\mathbb{R}}\left\\{\Phi\left(Pf-m\right)\right\\}$
$\displaystyle=\inf_{m\in\mathbb{R}}\left\\{\Phi\left(P\left(f-m\right)\right)\right\\}$
$\displaystyle\leqslant\inf_{m\in\mathbb{R}}\left\\{\Phi\left(f-m\right)\right\\}$
$\displaystyle=\tilde{\Phi}\left(f\right).$

######  Theorem 36.

Let $P_{1}$ and $P_{2}$ be two $\mu-$invariant Markov kernels. Assume that for
any $(x,A)\in\mathsf{E}\times\mathcal{F}$,
$P_{2}(x,A\setminus\\{x\\})\geq\int_{A\setminus\\{x\\}}\varepsilon(x,y)P_{1}(x,{\rm
d}y)$ for some $\varepsilon\colon\mathsf{E}^{2}\rightarrow(0,\infty)$. Then
for any $p\in(1,\infty],q\geq 1$ such that $p^{-1}+q^{-1}=1$, any $s>0$, and
any $f\in\mathrm{\mathrm{L}}_{0}^{2p}(\mu)\subset\mathrm{L}^{2}_{0}(\mu)$,

$\mathcal{E}(P_{1},f)\leq s\mathcal{E}(P_{2},f)+\mu\otimes
P_{1}\big{(}A(s)^{\complement}\cap\\{X\neq Y\\}\big{)}^{1/q}\Phi_{p}(f),$

with $A(s):=\left\\{(x,y)\in\mathsf{E}^{2}\colon
s\,\varepsilon(x,y)>1\right\\}$ and $\Phi_{p}(f)$ as in (7), which satisfies
(1).

###### Proof.

For any $s>0$ we have

$\displaystyle\mathcal{E}(P_{1},f)$
$\displaystyle\leq\frac{1}{2}\int_{A(s)}s\,\varepsilon(x,y)\mu({\rm
d}x)P_{1}(x,{\rm d}y)\left[f(y)-f(x)\right]^{2}$ $\displaystyle\hskip
113.81102pt+\frac{1}{2}\int_{A(s)^{\complement}}\mu({\rm d}x)P_{1}(x,{\rm
d}y)\left[f(y)-f(x)\right]^{2}$ $\displaystyle\leq
s\frac{1}{2}\int_{A(s)}\mu({\rm d}x)P_{2}(x,{\rm
d}y)\left[f(y)-f(x)\right]^{2}+\mu\otimes
P_{1}\big{(}A(s)^{\complement}\cap\\{X\neq Y\\}\big{)}^{1/q}\Phi_{p}(f),$

where we have used the assumed inequality between $P_{1}$ and $P_{2}$ and
Proposition 34. ∎

######  Remark 37.

Our result concerned with the IMH algorithm in Subsection 2.3 is a particular
case where $P_{{\rm
IMH}}(x,A\setminus\\{x\\})\geq\int_{A\setminus\\{x\\}}[w^{-1}(x)\wedge
w^{-1}(y)]\pi({\rm d}y)$, which combined with Proposition 30 with $C_{{\rm
P}}=1$ leads to Proposition 25.

The following generalizes the criterion $P(x,\\{x\\})\geq\varepsilon$ for some
$\varepsilon>0$ and all $x\in\mathsf{E}$ often used to establish the existence
of a left spectral gap for reversible Markov chains.

######  Theorem 38.

Assume that $P$ is $\mu-$invariant and that for any
$(x,A)\in\mathsf{E}\times\mathcal{F}$ it satisfies
$P(x,A)\geq\varepsilon(x)\int_{A}\delta_{x}({\rm d}y)$ for some
$\varepsilon\colon\mathsf{E}\rightarrow[0,1]$. Then

  1. 1.

for any $(x,A)\in\mathsf{E}\times\mathcal{F}$,
$P^{2}(x,A)\geq\varepsilon(x)P(x,A)$,

  2. 2.

for any $p\in(1,\infty]$, $1/q=1-1/p$, any
$f\in\mathrm{\mathrm{L}}_{0}^{2p}(\mu)\subset\mathrm{L}^{2}_{0}(\mu)$ and
$s>0$

$\mathcal{E}(P,f)\leq s\mathcal{E}(P^{2},f)+\mu\big{(}\varepsilon(X)^{-1}\geq
s\big{)}^{1/q}\Phi_{p}(f).$

######  Corollary 39.

Proposition 30 or Proposition 32 can be applied with $T_{1}=P_{1}=P$ and
$T_{2}=P_{2}=P^{2}$. This can be applied to the Metropolis–Hastings (MH)
algorithm (see (9)) as soon as $\mu(\rho(X)>0)=1$ and also means that weakly
lazy chains can be defined as $\varepsilon(x){\rm
Id}+\big{(}1-\varepsilon(x)\big{)}\check{P}$ where $\check{P}$ is a MH using
proposal $P$.

###### Proof of Theorem 38.

For $(x,A)\in\mathsf{E}\times\mathcal{F}$,

$P^{2}(x,A)=\int P(x,{\rm d}y)P(y,A)\geq\varepsilon(x)P(x,A)$

and we apply Theorem 36. Now $\mu\otimes P\big{(}\\{\varepsilon(X)^{-1}\geq
s\\}\cap\\{X\neq Y\\}\big{)}\leq\mu(\varepsilon(X)^{-1}\geq s)$ and we
conclude. ∎

######  Remark 40.

It is natural to consider the scenario where $T_{1}$ and $T_{2}$ admit
different invariant distributions, $\mu_{1}$ and $\mu_{2}$ respectively. With
straightforward notation for $\|\cdot\|_{2}$ under $\mu_{1}$ and $\mu_{2}$, a
condition of the type

$\|f-\mu_{2}(f)\|_{\mu_{2}}^{2}\leq
s\|f-\mu_{1}(f)\|_{\mu_{1}}^{2}+\beta(s)\Phi(f),$ (8)

is natural. Using polarisation one can show that, with
$A(s)=\\{(x,y)\in\mathsf{E}^{2}\colon{\rm d}(\mu_{1}\otimes\mu_{1})/{\rm
d}(\mu_{2}\otimes\mu_{2})(x,y)\geq 1/s\\}$,

$\frac{1}{2}\int\big{(}f(y)-f(x)\big{)}^{2}\mathrm{d}\left(\mu_{2}\otimes\mu_{2}\right)(x,y)\leq\frac{s}{2}\int_{A(s)}\big{(}f(y)-f(x)\big{)}^{2}\mathrm{d}\left(\mu_{1}\otimes\mu_{1}\right)(x,y)\\\
+\|f\|_{{\rm osc}}^{2}\frac{\mu_{2}\otimes\mu_{2}}{2}\left(\frac{{\rm
d}(\mu_{2}\otimes\mu_{2})}{{\rm d}(\mu_{1}\otimes\mu_{1})}(X,Y)>s\right),$

implying (8). We note however that in the examples we have considered, we have
found the last term to lead to poor convergence rates.

Our final result in this section concerns the situation when one has a
sequence of super-Poincaré inequalities given by functions
$\left\\{\beta_{2,\iota}\right\\}_{\iota>0}$, which converge pointwise to an
appropriate function $\beta_{1}$. We give conditions under which the
corresponding convergence rates $F_{2,\iota}^{-1}$ will also converge to the
corresponding $F_{1}^{-1}$.

######  Proposition 41.

Let $P_{1}$ and $(P_{2,\iota})_{\iota>0}$ be $\mu-$invariant Markov kernels.
Assume $P_{1}$ satisfies a super-Poincaré inequality with function $\beta_{1}$
and that for any $\iota>0$

$\|f\|_{2}^{2}\leq
s\mathcal{E}(P_{2,\iota}^{*}P_{2,\iota},f)+\beta_{2,\iota}(s)\Phi(f),\quad\forall
s>0,$

where each $\beta_{2,\iota}$ satisfies the conditions in Definition 4. Let
$F_{1},F_{2,\iota}:(0,a]\to[0,\infty)$ for each $\iota>0$ be as defined in
Section 2.

Assume that for any $\iota>0$, $\beta_{2,\iota}\geq\beta_{1}$ pointwise and
for any $s>0$, $\lim_{\iota\rightarrow 0}\beta_{2,\iota}(s)=\beta_{1}(s).$
Then for any $\iota>0$ and $n\in\mathbb{N}$, $F_{2,\iota}^{-1}(n)\geq
F_{1}^{-1}(n)$ and

$\lim_{\iota\rightarrow 0}\sup_{n\geq
0}\big{\\{}F_{2,\iota}^{-1}(n)-F_{1}^{-1}(n)\big{\\}}=0.$

###### Proof.

Let $v>0$ and $(u_{n})$ be such that
$K_{1}^{*}(v)=\lim_{n\rightarrow\infty}u_{n}[v-\beta_{1}(1/u_{n})]$. Then for
any $\iota>0$ and any $n\geq 1$, $K_{2,\iota}^{*}(v)\geq
u_{n}[v-\beta_{2,\iota}(1/u_{n})],$ and therefore

$\liminf_{\iota\rightarrow 0}K_{2,\iota}^{*}(v)\geq\lim_{\iota\rightarrow
0}u_{n}[v-\beta_{2,\iota}(1/u_{n})]=u_{n}[v-\beta_{1}(1/u_{n})].$

Consequently,

$\liminf_{\iota\rightarrow
0}K_{2,\iota}^{*}(v)\geq\lim_{n\rightarrow\infty}u_{n}[v-\beta_{1}(1/u_{n})]=K_{1}^{*}(v).$

Since for any $\iota>0$, $\beta_{2,\iota}\geq\beta_{1}$ implies
$K_{2,\iota}^{*}\leq K_{1}^{*}$, we have $\limsup_{\iota\rightarrow
0}K_{2,\iota}^{*}(v)\leq K_{1}^{*}(v)$. We therefore conclude that
$\lim_{\iota\rightarrow 0}K_{2,\iota}^{*}(v)=K_{1}^{*}(v)$. Now let $0<x\leq
a$, and choose $\epsilon>0$ such that $K_{1}(x)-\epsilon>0$. Then there exists
$\iota_{0}>0$ such that for any $0<\iota\leq\iota_{0}$,
$K_{2,\iota}^{*}(x)\geq K_{1}(x)-\epsilon>0$, and since $v\mapsto
K_{2,\iota}^{*}(v)$ is increasing, we deduce
$0<\sup_{v\in[x,a]}\big{(}K_{2,\iota}^{*}(v)\big{)}^{-1}\leq\big{(}K_{2,\iota}^{*}(x)\big{)}^{-1}\leq\big{(}K_{1}^{*}(x)-\epsilon\big{)}^{-1}<\infty$.
We can therefore apply the bounded convergence theorem and conclude

$\lim_{\iota\rightarrow 0}\int_{x}^{a}\frac{{\rm
d}v}{K_{2,\iota}^{*}(v)}=F_{1}(x).$

For any $\iota>0$, $F_{1},F_{2,\iota}\colon(0,a]\rightarrow[0,\infty)$ are
decreasing and continuous and so are the inverse functions
$F_{1}^{-1},F_{2,\iota}^{-1}\colon[0,\infty)\rightarrow(0,a]$, and
consequently for any $x\in[0,\infty)$, $\lim_{\iota\rightarrow
0}F_{2,\iota}^{-1}(x)=F_{1}^{-1}(x)$ (note that
$F_{2,\iota}^{-1}(0)=F_{1}^{-1}(0)=a$). Since $K_{2,\iota}^{*}\leq K_{1}^{*}$,
we immediately have the ordering $F_{2,\iota}^{-1}(x)\geq F_{1}^{-1}(x)$ for
any $x\in[0,\infty)$.

Now let $\epsilon>0$, then there exists $n_{0}\in\mathbb{N}$ such that for any
$n\geq n_{0}$, $F_{1}^{-1}(n)\leq\epsilon/2$. From the convergence above,
there exists $\iota_{0}>0$ such that for any $0<\iota\leq\iota_{0}$,

$0\leq F_{2,\iota}^{-1}(n_{0})-F_{1}^{-1}(n_{0})\leq\epsilon/2,$

and since $n\mapsto F_{2,\iota}^{-1}(n)$ is decreasing, for any $n\geq n_{0}$,

$F_{2,\iota}^{-1}(n)-F_{1}^{-1}(n)\leq F_{2,\iota}^{-1}(n)\leq\epsilon.$

Now, there exists $\iota^{\prime}_{0}>0$ such that for any
$0<\iota<\iota^{\prime}_{0}$,

$\max_{0\leq
n<n_{0}}\left\\{F_{2,\iota}^{-1}(n)-F_{1}^{-1}(n)\right\\}\leq\epsilon.$

Therefore,

$\lim_{\iota\rightarrow 0}\sup_{n\geq
0}\left\\{F_{2,\iota}^{-1}(n)-F_{1}^{-1}(n)\right\\}=0.$

∎

######  Example 42.

Let $\beta_{1}(s)=a\mathbb{I}\\{s\leq C_{{\rm P}}^{-1}\\}$, which corresponds
to $P_{1}$ satisfying a strong Poincaré inequality as in Remark 11. Let
$P_{2,\iota}$ satisfy a super Poincaré inequality with
$\beta_{2,\iota}(s)=a\wedge\\{\beta^{\prime}_{\iota}(C_{{\rm P}}s)/C_{{\rm
P}}\\}$ (e.g. by Proposition 30) where
$\beta^{\prime}_{\iota}(s)\geq\mathbb{I}\\{s\leq 1\\}$ so that
$\beta_{2,\iota}\geq\beta_{1}$. If $\lim_{\iota\to
0}\beta^{\prime}_{\iota}(s)=\mathbb{I}\\{s\leq 1\\}$ for all $s>0$, then
Proposition 41 can be applied and we recover exponential convergence as
$\iota\rightarrow 0$, and for any $\epsilon>0$ the existence of $\iota>0$,
such that $F_{2,\iota}^{-1}(n)-F_{1}^{-1}(n)<\epsilon$ for all $n$. In other
words, one may obtain convergence for $P_{2}$ arbitrarily close to that given
by $\beta_{1}$ by taking $\iota$ sufficiently small.

##  4 Application to pseudo-marginal methods

We now present our main application. Fix a probability distribution $\pi$ on a
measure space $\mathsf{X}$, with a density function also denoted $\pi$.
Pseudo-marginal algorithms [2] extend the scope of the Metropolis–Hastings
algorithms to the scenario where the density $\pi$ is intractable, but for any
$x\in\mathsf{X}$, nonnegative estimators $\hat{\pi}(x)$ such that
$\mathbb{E}[\hat{\pi}(x)]=C\pi(x)$ for some constant $C>0$ are available. This
can be conveniently formulated as $\tilde{\pi}({\rm d}x,{\rm d}w)=\pi({\rm
d}x)Q_{x}({\rm d}w)w=\pi({\rm d}x)\tilde{\pi}_{x}({\rm d}w)$ with
$\int_{\mathbb{R}_{+}}wQ_{x}({\rm d}w)=1$ on an extended space
$\mathsf{E}:=\mathsf{X\times\mathbb{R}_{+}}$. We will refer to these auxiliary
$w$ random variables as _weights_ or _perturbations_.

###  4.1 A weak Poincaré inequality for pseudo-marginal chains

A question of interest is to characterise the degradation in performance,
compared to the _marginal algorithm_ , which uses the exact density $\pi$.
More specifically, for $\\{q(x,\cdot),x\in\mathsf{X}\\}$ a family of proposal
distributions, the marginal algorithm is described by the kernel

$\displaystyle P(x,{\rm d}y)$
$\displaystyle=[1\wedge\mathfrak{r}(x,y)]\,q(x,{\rm d}y)+\delta_{x}({\rm
d}y)\rho(x),$
$\displaystyle\quad\text{where}\quad\mathfrak{r}(x,y):=\frac{\pi(y)q(y,{\rm
d}x)}{\pi(x)q(x,{\rm d}y)},$ (9)

and $\rho$ is the rejection probability given by
$\rho(x):=1-\int[1\wedge\mathfrak{r}(x,y)]\,q(x,\mathrm{d}y)$ for each
$x\in\mathsf{X}$. For brevity we will also define the acceptance probability
as $a(x,y):=\left[1\wedge\mathfrak{r}(x,y)\right]$.

The pseudo-marginal Metropolis–Hastings kernel is given by

$\tilde{P}(x,w;{\rm d}y,{\rm
d}u)=\left[1\wedge\left\\{\mathfrak{r}(x,y)\frac{u}{w}\right\\}\right]q(x,{\rm
d}y)Q_{y}({\rm d}u)+\delta_{x,w}({\rm d}y,{\rm d}u)\tilde{\rho}(x,w),$

where the (joint) rejection probability $\tilde{\rho}(x,w)$ is analogously
defined. It is known in this context that perturbing the acceptance ratio of
the marginal algorithm leads to a loss in performance, in particular in terms
of convergence rates to equilibrium. More specifically, if $P$ is
geometrically ergodic, then $\tilde{P}$ is geometrically ergodic if the
perturbations are bounded uniformly in $x$, and cannot be geometrically
ergodic if the perturbations are unbounded on a set of positive
$\pi$-probability, which addressed in [3] in specific scenarios using
Foster–Lyapunov and minorisation conditions by linking the existence of
moments of the perturbations to the subgeometric rate of convergence of the
algorithm. When the perturbations are bounded for each $x$ but not bounded
uniformly in $x$, the situation is more complicated: if “local proposals” are
used then [25] proves that $\tilde{P}$ cannot be geometric under fairly weak
assumptions in statistical applications whereas if global proposals are used
$\tilde{P}$ may still be geometric (consider, for instance, the setting of
[10, Remark 5]). We show here that convergence results can be made completely
general using weak Poincaré inequalities, with much simpler and considerably
more transparent arguments.

We will be assuming throughout this section that the pseudo-marginal kernel
$\tilde{P}$ is positive, in order to utilize our results from Section 2.2.1.
We note that this positivity assumption is not restrictive; as established in
[3, Proposition 16], $\tilde{P}$ will be positive if the marginal chain $P$ is
an Independent MH sampler, or a random walk Metropolis kernel with
multivariate Gaussian or student-$t$ increments.

The following comparison theorem plays a central role.

######  Theorem 43.

Let $\bar{P}$ be the embedding of $P$ in the joint space
$\mathsf{E}=\mathsf{X}\times\mathbb{R}_{+}$,

$\bar{P}(x,w;{\rm d}y,{\rm d}u):=a(x,y)q(x,{\rm d}y)\tilde{\pi}_{y}({\rm
d}u)+\delta_{x,w}({\rm d}y,{\rm d}u)\rho(x).$

Then for any $p\in(1,\infty],q\geq 1$ such that $p^{-1}+q^{-1}=1$, any $s>0$,
and any
$f\in\mathrm{L}^{2p}(\tilde{\pi})\subset\mathrm{L}^{2}_{0}(\tilde{\pi})$,

$\mathcal{E}(\bar{P},f)\leq
s\mathcal{E}(\tilde{P},f)+\Phi_{p}(f)\left(\int_{\mathsf{X}}\tilde{\pi}_{x}(w\geq
s)\,\pi({\rm d}x)\right)^{1/q},$

with $\Phi_{p}(f)$ given in (7).

###### Proof.

We apply Theorem 36. Let $\varepsilon(w,u):=w^{-1}\wedge u^{-1}$, then for any
$(x,w)\in\mathsf{E}$ and $B\in\mathcal{F}$,

$\displaystyle\int_{B\setminus\\{x,w\\}}\varepsilon(w,u)\bar{P}(x,w;{\rm
d}y,{\rm d}u)$ $\displaystyle=\int_{B}$ $\displaystyle
q(x,\mathrm{d}y)\tilde{\pi}_{y}({\rm d}u)a(x,y)(w^{-1}\wedge u^{-1})$
$\displaystyle=\int_{B}$ $\displaystyle q(x,{\rm d}y)Q_{y}({\rm
d}u)u\,a(x,y)(w^{-1}\wedge u^{-1})$ $\displaystyle=\int_{B}$ $\displaystyle
q(x,{\rm d}y)Q_{y}({\rm d}u)a(x,y)(1\wedge\frac{u}{w})$
$\displaystyle\leq\int_{B}$ $\displaystyle q(x,{\rm d}y)Q_{y}({\rm
d}u)[1\wedge\bigl{(}\mathfrak{r}(x,y)\frac{u}{w}\bigr{)}],$ $\displaystyle=$
$\displaystyle\tilde{P}(x,w;B\setminus\\{x,w\\}).$

where we have used that $1\wedge(ab)\geq(1\wedge a)(1\wedge b)$ for $a,b\geq
0$. Now for $s>0$ let

$\displaystyle A(s)$ $\displaystyle:=\left\\{(w,u)\in\mathbb{R}_{+}^{2}\colon
w^{-1}\wedge u^{-1}>1/s\right\\},$ $\displaystyle\bar{A}(s)$
$\displaystyle:=\left\\{(x,w,y,u)\in\mathsf{E}\times\mathsf{E}\colon
w^{-1}\wedge u^{-1}>1/s\right\\}.$

Then,

$\displaystyle\mu\otimes\bar{P}\big{(}\bar{A}^{\complement}(s)\cap\\{(X,W)\neq(Y,U)\\}\big{)}\leq$
$\displaystyle\int_{\bar{A}(s)^{\complement}}a(x,y)\pi({\rm d}x)q(x,{\rm
d}y)\tilde{\pi}_{x}({\rm d}w)\tilde{\pi}_{y}({\rm d}u)$ $\displaystyle=$
$\displaystyle\int_{\mathsf{X}^{2}}\left[a(x,y)\int_{A(s)^{\complement}}\tilde{\pi}_{x}(\mathrm{d}w)\tilde{\pi}_{y}(\mathrm{d}u)\right]\pi({\rm
d}x)q(x,{\rm d}y),$

and

$\displaystyle\int_{A(s)^{\complement}}\tilde{\pi}_{x}({\rm
d}w)\tilde{\pi}_{y}({\rm d}u)$ $\displaystyle=1-\tilde{\pi}_{x}(w\leq
s)\tilde{\pi}_{y}(u\leq s)$
$\displaystyle=1-[1-\tilde{\pi}_{x}(w>s)][1-\tilde{\pi}_{y}(u>s)]$
$\displaystyle\leq\tilde{\pi}_{x}(w\geq s)+\tilde{\pi}_{y}(u\geq s).$

Therefore,

$\mu\otimes\bar{P}\big{(}\bar{A}(s)^{\complement}\cap\\{(X,W)\neq(Y,U)\\}\big{)}\leq
2\int\tilde{\pi}_{x}(w\geq s)\pi({\rm d}x).$

We conclude. ∎

We are now in a position to apply Proposition 30 or Proposition 32. We will
see that the tail behaviour of the perturbations governs the rate at which our
bound on $\|\tilde{P}^{n}f\|_{2}$ vanishes as $n\rightarrow\infty$. For
simplicity, for the remainder of this section we focus on the case where
$\Phi(f)=\|f\|_{{\rm osc}}^{2}$.

######  Corollary 44.

When $\bar{P}$ satisfies a strong Poincaré inequality with constant
$C_{\mathrm{P}}$ as in Remark 3, Proposition 30 establishes that $\tilde{P}$
satisfies Definition 16 with $\beta(s)=\beta^{\prime}(C_{\mathrm{P}}s)/C_{P}$
where $\beta^{\prime}(s)=\int\tilde{\pi}_{x}(w\geq s)\pi({\rm d}x)$ and
$\Phi(f)=\|f\|_{{\rm osc}}^{2}$. Consequently, Theorem 19 applies to
$\tilde{P}$ with a rate determined by $\beta(s)$.

Furthermore, using Markov’s inequality, the existence of moments of $W$ under
$\tilde{\pi}_{x}$ of order $k\in\mathbb{N_{*}}$ implies

$\beta^{\prime}(s)\leq
s^{-k}\int_{\mathsf{X}}\mathbb{E}_{\tilde{\pi}_{x}}\left[|W|^{k}\right]\pi({\rm
d}x).$

Provided the integral is finite, this leads to a polynomial rate of
convergence $O(n^{-k})$ by Lemma 14.

Similarly, if $\bar{P}$ satisfies a weak Poincaré inequality, one can apply
Proposition 32 and deduce the new rate of convergence as in Example 33.

######  Remark 45.

Notice that when the perturbations are uniformly bounded, i.e. there exists
$\bar{w}$ such that for all $x\in\mathsf{X}$,
$\tilde{\pi}_{x}(w\geq\bar{w})=0$, and $\bar{P}$ satisfies a strong Poincaré
inequality, then $C_{{\rm
P}}\|f\|^{2}\leq\mathcal{E}(\bar{P},f)\leq\bar{w}\mathcal{E}(\tilde{P},f)$ and
we recover the known results of [2, 3].

We provide a general result demonstrating that under very weak conditions
pseudo-marginal convergence can be made arbitrarily close to marginal
convergence, strengthening the result of [2, Section 4].

######  Remark 46.

Assume that there is a parameter $\iota>0$ controlling the quality of the
perturbations $W\sim\tilde{\pi}_{x,\iota}$ such that for each
$x\in\mathsf{X}$, $W$ converges in probability to $1$ as $\iota\to 0$:

$\lim_{\iota\to 0}\tilde{\pi}_{x,\iota}(w\geq s)=\mathbb{I}\\{s\leq
1\\},\qquad x\in\mathsf{X},s>0.$

Let

$\beta_{\iota}(s):=\int_{\mathsf{X}}\tilde{\pi}_{x,\iota}(w\geq s)\,\pi({\rm
d}x),$

then the bounded convergence theorem implies that

$\lim_{\iota\to 0}\beta_{\iota}(s)=\mathbb{I}\\{s\leq 1\\},\qquad s>0.$

Assume now that $\bar{P}$ satisfies a weak Poincaré inequality with function
$\bar{\beta}$. Similar to Example 42, one can compare the convergence bounds
for $\tilde{P}_{\iota}$ and $\bar{P}$ via their respective functions
$\tilde{\beta}_{\iota}$ and $\bar{\beta}$. Indeed, Theorem 43 and Proposition
32 imply that $\tilde{P}_{\iota}$ satisfies a super-Poincaré inequality with
function

$\tilde{\beta}_{\iota,\epsilon}(s)=\frac{s}{1+\epsilon}\beta_{\iota}(1+\epsilon)+\bar{\beta}\left(\frac{s}{1+\epsilon}\right),$

where $\epsilon>0$ is arbitrary. Note that for $s>0$,
$\tilde{\beta}_{\iota,\epsilon}(s)\geq\bar{\beta}\big{(}s/(1+\epsilon)\big{)}\geq\bar{\beta}(s)$
and since $\lim_{\iota\rightarrow
0}\tilde{\beta}_{\iota}(s)=\bar{\beta}\left(s/(1+\epsilon)\right)$ we can
apply Proposition 41 to obtain convergence bounds arbitrarily close to those
of $\bar{P}$ with rate function $\bar{\beta}$.

###  4.2 The effect of averaging

A natural idea to reduce the variability of pseudo-marginal chains is to
average several estimators $\hat{\pi}$ of the target density at each
iteration. As pointed out in [3], this is unlikely to affect asymptotic rates
of convergence. Furthermore, it was established in [6, 33] that when
considering asymptotic variance, it is preferable to combine the output of $N$
independent chains each using $1$ estimator, rather than running $1$ chain
averaging $N$ estimators at each iteration. The following, motivated by the
application of Markov’s inequality, adds nuance to these conclusions by
showing how bias can be reduced by averaging, particularly in situations where
higher order moments of the perturbations are large.

######  Lemma 47.

Let $\\{W_{i}\\}$ be i.i.d., of expectation $1$ and such that for a given
$p\in\mathbb{N}$ with $p\geq 2$, $\mathbb{E}\left(|W_{1}|^{p}\right)<\infty$.
Then there are some constants $\left\\{C_{p,k}\right\\}$, such that for any
$N\in\mathbb{N}$,

$\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}W_{i}\right|^{p}\right]\leq
1+\sum_{k=2}^{p}N^{-k/2}C_{p,k}\mathbb{E}\left[|W_{1}-1|^{k}\right].$ (10)

For large $N$, this bound is $1+O(N^{-1})$.

As an illustration, we focus here on the scenario where the marginal chain
satisfies a strong Poincaré inequality (Remark 3) and the moments are
uniformly bounded in $x\in\mathsf{X}$. Let
$\mathcal{W}_{N}:=N^{-1}\sum_{i=1}^{N}W_{i}$, then Markov’s inequality implies
that for the pseudo-marginal algorithm which averages $N$ estimators,

$\displaystyle\beta^{\prime}_{N}(s)$
$\displaystyle\leq\left[\sup_{x\in\mathsf{X}}\mathbb{E}_{\tilde{\pi}_{x}}\big{(}\mathcal{W}_{N}^{p}\big{)}\right]s^{-p},$

and while the rate of convergence in $s$ is independent of $N$, the
multiplicative constant in square brackets does depend on $N$. Indeed, by
Lemma 47, averaging by choosing $N>1$ can reduce its magnitude and reduce our
convergence upper bounds in Theorem 19, thanks to Lemma 13. The bound obtained
in (10) suggests that while the asymptotic rate of decay for large $N$ is
governed by the term $\mathbb{E}\left[\left|W_{1}-1\right|^{2}\right]N^{-1}$,
inversely proportional to the increased computational cost at each MCMC
iteration, higher order moments may play an important role for small to
moderate values of $N$.

This is expected for heavy-tailed distributions: for example, consider an
inverse gamma distribution of expectation $1$ and shape parameter
$\mathsf{s}>1$. Its raw (polynomial) moments grow very rapidly as
$\mathbb{E}\left(W_{1}^{k}\right)=(\mathsf{s}-1)^{k}/\prod_{i=1}^{k}(\mathsf{s}-i)$
for $k\in\mathbb{N}$, $k<\mathsf{s}$ and $\mathsf{s}$ large, and for small and
moderate values of $N$, summands other than $k=2$ in (10) will be most
prominent.

###  4.3 ABC example

We consider an Approximate Bayesian Computation (ABC) setting, using notation
inspired by [25]. We assume we have a true posterior density
$\pi_{0}(x)\propto\nu(x)\ell_{y}(x)$ on a space
$\mathsf{X}\subset\mathbb{R}^{d_{x}}$, where $\nu(\cdot)$ represents the prior
and $x\mapsto\ell_{y}(x)$ is an intractable likelihood corresponding to a
probability density $f_{x}(y)=\ell_{y}(x)$ for some fixed observations
$y\in\mathsf{Y}\subset\mathbb{R}^{\mathrm{d}}$. It is known that ABC Markov
chains of the type considered here cannot be geometrically ergodic under
fairly weak conditions when a “local proposal” is used [25, Theorem 2].

Fix an $\epsilon>0$ and $x\in\mathcal{\mathsf{X}}$, and for $j=1,\dots,N$, let
$z_{j}\overset{{\rm iid}}{\sim}f_{x}(\cdot)$ be auxiliary random variables and
define the random variables $W_{j}$, where $\left|\cdot\right|$ denotes the
Euclidean norm,

$W_{j}=\begin{cases}1/\ell_{{\rm ABC}}(x)&\text{if
}\left|z_{j}-y\right|<\epsilon,\\\ 0&\text{else,}\end{cases}$

with $\ell_{{\rm ABC}}(x):=\mathbb{P}_{x}(\left|z_{1}-y\right|<\epsilon)$. In
an ABC setup, the intractable $\pi_{0}$ is replaced with the ABC posterior
$\pi(x)\propto\nu(x)\ell_{{\rm ABC}}(x)$, which is typically also intractable
and itself approximated using a pseudo-marginal approach: for fixed
$N\in\mathbb{N}$, define

$\displaystyle\tilde{\pi}(x,z_{1},\ldots,z_{N})$
$\displaystyle\propto\nu(x)\ell_{{\rm
ABC}}(x)\left[\prod_{j=1}^{N}f_{x}(z_{j})\right]\cdot\frac{1}{N}\sum_{j=1}^{N}W_{j}.$

It is easily seen that $\mathcal{W}_{N}:=\frac{1}{N}\sum_{j=1}^{N}W_{j}$ has
expectation 1 under $\big{[}\prod_{j=1}^{N}f_{x}(z_{j})\big{]}{\rm
d}z_{1}\times\cdots\times{\rm d}z_{N}$ for a fixed $x\in\mathsf{X}$. In our
previous notation, $Q_{x}(\mathrm{d}w)$ is then the law of $\mathcal{W}_{N}$
when the $(z_{1},\ldots,z_{N})$ are drawn from
$\big{[}\prod_{j=1}^{N}f_{x}(z_{j})\big{]}{\rm d}z_{1}\times\cdots\times{\rm
d}z_{N}$, and $\tilde{\pi}_{x}(\mathrm{d}w)=wQ_{x}(\mathrm{d}w)$. Given
$x\in\mathsf{X}$, it is clear that under $Q_{x}$, we have that $\ell_{{\rm
ABC}}(x)\sum_{j=1}^{N}W_{j}\sim\mathrm{Bin}\big{(}N,\ell_{{\rm
ABC}}(x)\big{)}$.

Thus from our previous result, Corollary 44, in order to bound the rate of
convergence of the resulting pseudo-marginal algorithm, we need to bound for
$s>0$,

$\int_{\mathsf{X}}\pi(\mathrm{d}x)\tilde{\pi}_{x}(\mathcal{W}_{N}\geq s).$

So given $x\in\mathcal{\mathsf{X}}$, $s>0$, we first consider
$\tilde{\pi}_{x}(\mathcal{W}_{N}\geq s)$. Using Markov’s inequality, for any
$p\in\mathbb{N}$, we can bound

$\tilde{\pi}_{x}(\mathcal{W}_{N}\geq
s)\leq\frac{\tilde{\pi}_{x}\left[\mathcal{W}_{N}^{p}\right]}{s^{p}}=\frac{Q_{x}\left[\mathcal{W}_{N}^{p+1}\right]}{s^{p}}.$

This seems to suggest that if the marginal algorithm is geometrically ergodic,
then its ABC approximation converges at any polynomial rate. The following
result tells us that this may not be the case.

######  Proposition 48.

For a given $p\in\mathbb{N}$, suppose that $\int_{\mathsf{X}}\nu(x)\ell_{{\rm
ABC}}^{-(p-1)}(x)\mathrm{d}x<\infty$. Then there is $C_{N,p}>0$ such that for
all $s>0$,

$\int_{\mathcal{\mathsf{X}}}\pi(\mathrm{d}x)\tilde{\pi}_{x}(\mathcal{W}_{N}\geq
s)\leq C_{N,p}s^{-p},$

and as $N\to\infty$, $C_{N,p}=1+O(1/N)$. In particular, we may always take
$p=1$. The resulting convergence rate for the pseudo-marginal chain is then
also $O(n^{-p})$ as in Lemma 14.

###  4.4 Products of averages

The results in Sections 4.2–4.3 suggest that $N$ may not need to be taken too
large in the case of simple averaging. We consider here a scenario where the
perturbation is instead a product of $T$ independent averages, which gives
different conclusions, and can be seen as a simple version of the perturbation
involved in a particle marginal Metropolis–Hastings (PMMH) algorithm [1], a
special case of a pseudo-marginal algorithm. Such scenarios can arise in
random effects and latent variable models. For example, [35, Section 4.1] uses
a random effects model from [12, Section 6.1] to analyze the data from [19],
while [26, Section 4.2] considers an ABC example with i.i.d. data and [26,
Section 4.3] considers a single-cell gene expression model proposed by [28]
and employed, e.g., by [34].

The following bound can be used in Corollary 44, and indicates that it is
sufficient to take $N$ proportional to $T$ to obtain $T$-independent bounds on
the relevant tail probabilities as long as $\pi$ is sufficiently concentrated.

######  Proposition 49.

Assume $W\sim Q_{x}$ can be written as $W=\prod_{t=1}^{T}W_{t}$, where each
$W_{t}$ is independent and nonnegative, and for each $t\in\\{1,\ldots,T\\}$,

$W_{t}=\frac{1}{N}\sum_{i=1}^{N}W_{t,i},$

is an average of nonnegative, identically distributed random variables with
mean $1$. Assume that for some $p\in\mathbb{N}$ with $p\geq 2$, and any
$x\in\mathsf{X}$,

$\max_{t\in\\{1,\ldots,T\\}}\mathbb{E}\left[W_{t,1}^{p}\right]<\infty.$

Then there exists a function $M_{p}:\mathsf{X}\to\mathbb{R}_{+}$ such that if
we take

$N\geq\alpha T+\frac{1}{2}+\sqrt{\alpha T},$

for some $\alpha>0$, then

$\int\pi({\rm d}x)\tilde{\pi}_{x}(W\geq s)\leq s^{-p+1}\int\pi({\rm
d}x)\exp\left(\frac{M_{p}(x)}{\alpha}\right),$

where the right-hand side may be finite or infinite depending on $\pi$.

In particular, we can see that if the function $M_{p}$ grows quickly in the
tails of $\pi$, then the bound is finite only if $\pi$ has sufficiently light
tails.

######  Example 50.

Assume $M_{p}(x)=bx^{k}$ and $\pi({\rm d}x)\propto{\bf
1}_{\mathbb{R}_{+}}(x)\exp(-cx^{\ell}){\rm d}x$ for some $k,\ell\geq 0$. If
$\ell<k$ then the integral $\int\pi({\rm d}x)\exp\left(M_{p}(x)/\alpha\right)$
in Proposition 49 is infinite. If $\ell>k$, then the integral is finite. If
$\ell=k$, then the integral is finite if and only if $\alpha>b/c$.

###  4.5 Lognormal example

We consider now a limiting case of the perturbations in a PMMH algorithm,
motivated by [5, Theorem 1.1], which has also been analyzed using other
techniques [16, 32]. The result of [5] concerns a particular mean 1
perturbation $W_{T,N}$ that is also a product of $T$ averages, with $N$ random
variables involved in each average, but where the random variables are not
independent. They show that, under regularity conditions, if $N=\alpha T$
there is a $\sigma_{0}^{2}$ such that with $\sigma^{2}=\sigma_{0}^{2}/\alpha$,
$\log(W_{T,N})$ converges in distribution to
$N(-\frac{1}{2}\sigma^{2},\sigma^{2})$ as $T\to\infty$.

We consider here the setting where for some large $T$, the log-perturbation is
exactly $N(-\frac{1}{2}\sigma^{2},\sigma^{2})$, in which case one can think of
$\sigma^{2}=\sigma_{0}^{2}T/N$, and since the precise value of $T$ is not
relevant we suppress it in the sequel. To be explicit, we have that $W$ has
law

$Q_{x}(\mathrm{d}w)=\frac{1}{w\sigma\sqrt{2\pi}}\exp\left(-\frac{\left(\log
w+\sigma^{2}/2\right)^{2}}{2\sigma^{2}}\right)\mathrm{d}w,$

where $\mathrm{d}w$ is Lebesgue measure on $\mathbb{R}_{+}$ and $\sigma>0$ is
a variance parameter, which we assume for simplicity is independent of $x$. We
note that a pseudo-marginal kernel with log-normal perturbations can only
converge subgeometrically, since the perturbations are not bounded.

####  4.5.1 Tail probabilities and convergence bound

######  Lemma 51.

We have the bound, for $s>0$, $\tilde{\pi}_{x}(W\geq s)\leq\beta(s)$, where

$\beta(s):=\exp\left(-\frac{\left(\left(\log
s-\sigma^{2}/2\right)_{+}\right)^{2}}{2\sigma^{2}}\right).$ (11)

######  Remark 52.

Note that despite (11) being an upper bound on the quantity of interest, it
satisfies the conditions in Example 42 and Remark 46, implying that the rate
of convergence of the marginal algorithm is recovered in the limit, as
$\sigma\rightarrow 0$.

Although it is theoretically possible to work directly with $\beta$ as in
(11), in order to derive clean and practically useful tuning guidelines, we
now derive some tractable bounds on the corresponding convergence rate.

######  Lemma 53.

We have a lower bound on the convex conjugate, for $0<v<1$,
$K^{*}(v)\geq\frac{v}{2}\exp\left(-\sigma\sqrt{-2\log\frac{v}{2}}-\sigma^{2}/2\right)$.

###### Proof.

This is immediate from choosing
$u=\exp\left(-\sigma\sqrt{-2\log\frac{v}{2}}-\sigma^{2}/2\right)$ in the
definition of the convex conjugate,
$K^{*}(v)=\sup_{u>0}\left\\{uv-u\beta(1/u)\right\\}$. ∎

As before, we define $F(w):=\int_{w}^{1}\frac{\mathrm{d}v}{K^{*}(v)}$. We are
able to deduce the following convergence bound.

######  Lemma 54.

We have the upper bound for $x>0$,

$F^{-1}(x)\leq
2\exp\left\\{-\frac{1}{2\sigma^{2}}\mathsf{W}^{2}\left(\frac{x\sigma^{2}}{2\exp(\sigma^{2}/2)}\right)\right\\},$
(12)

where $\mathsf{W}^{2}$ denotes the Lambert function squared.

######  Proposition 55.

Assume that the marginal chain $\bar{P}$ satisfies a strong Poincaré
inequality with constant $C_{\mathrm{P}}$ as in Remark 3. Then the final
convergence bound for the pseudo-marginal chain is given by

$F_{\mathrm{PM}}^{-1}(n)\leq\frac{2}{C_{\mathrm{P}}}\exp\left\\{-\frac{1}{2\sigma^{2}}\mathsf{W}^{2}\left(\frac{C_{\mathrm{P}}n\sigma^{2}}{2\exp(\sigma^{2}/2)}\right)\right\\}.$
(13)

###### Proof.

This is immediate from Corollary 44, Lemma 54. ∎

####  4.5.2 Mixing times

It is possible to obtain mixing time type results.

######  Proposition 56.

Let $\epsilon\in(0,1]$ and $\sigma^{2}>0$. Then, to obtain $F_{{\rm
PM}}^{-1}(n)\leq\epsilon^{2}$ it is sufficient to take

$n\geq\frac{2\sqrt{H(\epsilon)}}{C_{{\rm
P}}\sigma}\exp\left(\frac{\sigma^{2}}{2}+\sqrt{H(\epsilon)}\sigma\right),$
(14)

where $H(\epsilon)=2\log(2/(\epsilon^{2}C_{{\rm P}}))$.

###### Proof.

One can calculate directly that the bound of $F_{{\rm PM}}^{-1}$ in (12)
evaluated at the right-hand side of (14) is equal to
$2\exp(-H(\epsilon)/2)/C_{{\rm P}}$, which combined with the definition of
$H(\epsilon)$ and the monotonicity of $F_{{\rm PM}}^{-1}$ gives the result. ∎

Now we consider the minimum computational budget required to achieve a given
precision of $\epsilon$, and the corresponding split between the number of
MCMC iterations $n$ and the number of particles $N$. The budget required is
significantly lower than the result in Proposition 56 would imply for a fixed
$N$ and therefore $\sigma^{2}$.

######  Proposition 57.

Let $\epsilon\in(0,1]$. For simplicity, let $\bar{n}$ and $\bar{N}$ be real-
valued counterparts of $n$ and $N$, respectively. The ‘budget’ function
$(\bar{n},\bar{\sigma})\mapsto\mathsf{B}(\bar{n},\bar{\sigma})=\bar{n}\bar{N}=\bar{n}\sigma_{0}^{2}/\bar{\sigma}^{2}$
on $\mathbb{R}_{+}^{2}$ is minimized subject to the constraint $F_{{\rm
PM}}^{-1}(\bar{n};\bar{\sigma})=\epsilon^{2}$ (with $F_{{\rm PM}}^{-1}$ as in
(12)) when

$\bar{\sigma}=\bar{\sigma}_{\star}(\epsilon):=\frac{\sqrt{H(\epsilon)+12}-\sqrt{H(\epsilon)}}{2},$

where $H(\epsilon):=2\log\bigl{(}\frac{2}{C_{{\rm P}}\epsilon^{2}}\bigr{)}>0$
and
$\lim_{H(\epsilon)\to\infty}\sqrt{H(\epsilon)}\bar{\sigma}_{\star}(\epsilon)=3$.
Moreover, for $\epsilon>0$ such that $H(\epsilon)\geq 1$, we obtain $F_{{\rm
PM}}^{-1}(\bar{n};\bar{\sigma})=\epsilon^{2}$ with
$\bar{\sigma}(\epsilon)=3/\sqrt{H(\epsilon)}$,

$\displaystyle\bar{N}(\epsilon)$
$\displaystyle=\frac{2}{9}\sigma_{0}^{2}\log\left(\tfrac{2}{C_{{\rm
P}}\epsilon^{2}}\right),$ $\displaystyle\bar{n}(\epsilon)$
$\displaystyle\leq\frac{4\exp\left(15/2\right)}{3C_{{\rm
P}}}\log\left(\tfrac{2}{C_{{\rm P}}\epsilon^{2}}\right),$
$\displaystyle\mathsf{B}(\epsilon)$
$\displaystyle\leq\frac{8\sigma_{0}^{2}\exp\left(15/2\right)}{27C_{{\rm
P}}}\log\left(\tfrac{2}{C_{{\rm P}}\epsilon^{2}}\right)^{2},$

which is asymptotically accurate and optimal as $H(\epsilon)\to\infty$, i.e.
if $\epsilon\downarrow 0$ or $C_{{\rm P}}\downarrow 0$, except that the
constant factors $\exp\left(15/2\right)$ will tend to $\exp(3)$.

These non-asymptotic results take into account both $C_{{\rm P}}$ and
$\sigma_{0}^{2}$ in a natural manner and are easily interpretable. We note
that they also indicate how a given computational budget $\mathsf{B}$ should
be split between $N$ and $n$ in order to achieve best precision: in particular
$N$ should increase as $\mathsf{B}$ increases. This is to be contrasted with
results (see [16, 32] and below) concerned with the asymptotic variance which
recommend a fixed number of particles for any $\mathsf{B}$ sufficiently large
and allocation of the remaining resources to iterating the MCMC algorithm for
this fixed number of particles.

####  4.5.3 Asymptotic variance

We now show that our bounds lead to recommendations for $N$ similar to those
of [16, 32] when considering the asymptotic variance as a criterion. We can
use the bound (13) to give an upper bound on the resulting asymptotic
variance.

######  Lemma 58.

Fix a test function $f\in\mathrm{L}^{2}_{0}(\mu)$. In the setting of Theorem
19, for a reversible Markov kernel $P$, the asymptotic variance $v(f,P)$ is
bounded by

$v(f,P)\leq-\|f\|_{2}^{2}+4\Phi(f)\sum_{n=0}^{\infty}F^{-1}(n).$

######  Example 59.

For our log-normal pseudo-marginal example, we can then ask for a given $f$,
how to tune $\sigma$ in order to minimize the resulting bound on the
asymptotic variance. We can bound

$\displaystyle\sum_{n=1}^{\infty}F_{\mathrm{PM}}^{-1}(n)$
$\displaystyle\leq\sum_{n=1}^{\infty}\frac{2}{C_{\mathrm{P}}}\exp\left\\{-\frac{1}{2\sigma^{2}}\mathsf{W}^{2}\left(\frac{C_{\mathrm{P}}n\sigma^{2}}{2\exp(\sigma^{2}/2)}\right)\right\\}$
$\displaystyle\leq\frac{2}{C_{\mathrm{P}}}\int_{0}^{\infty}\exp\left(-\mathsf{a}\mathsf{W}^{2}(\mathsf{b}x)\right)\,\mathrm{d}x,$

where $\mathsf{a}:=1/(2\sigma^{2})$ and
$\mathsf{b}:=C_{\mathrm{P}}\sigma^{2}/(2\exp(\sigma^{2}/2))$. Here we used the
fact that the Lambert function is increasing. Through routine calculations and
making use of the substitution $\mathsf{b}x=u\exp(u)\Leftrightarrow
u=\mathsf{W}(\mathsf{b}x)$, this integral can be simplified and written as

$\tilde{v}(\sigma):=\frac{1}{\mathsf{b}}\left[\exp(1/(4\mathsf{a}))\left(1+\frac{1}{2\mathsf{a}}\right)\mathsf{a}^{-1/2}\int_{-\mathsf{a}^{-1/2}/2}^{\infty}\exp(-w^{2})\,\mathrm{d}w+\frac{1}{2\mathsf{a}}\right].$

In this final expression, both $\mathsf{a}$ and $\mathsf{b}$ depend on
$\sigma$, and the resulting function of
$\sigma\mapsto\tilde{v}(\sigma)/\sigma^{2}$ can be optimized numerically,
where we divide by $\sigma^{2}$ to take into account the additional
computational cost; see Figure 1. Note that the optimal value $\sigma_{*}$ of
$\sigma$ does not depend on $C_{\mathrm{P}}$, and we find numerically that
$\sigma_{*}\approx 0.973$. This is consistent with [16] who report optimal
values in the range $\sigma_{*}\approx 1.0-1.7$ (dependent on the performance
of the marginal algorithm) using another bound on the asymptotic variance,
while [32] find $\sigma_{*}\approx 1.812$ using a scaling and diffusion
approximation.

Figure 1: A plot of the function
$\sigma\mapsto\log\left(\tilde{v}(\sigma)/\sigma^{2}\right)$ in the case
$C_{\mathrm{P}}=1$.

##  Appendix A Proofs and other results for Section 2

######  Lemma 60.

With $\beta$ as in Definition 4, let $K(u):=u\,\beta(1/u)$ for $u>0$ and
$K(0):=0$. Define $K^{*}\colon[0,\infty)\rightarrow[0,\infty]$ to be the
convex conjugate, $K^{*}(v):=\sup_{u\geq 0}\left\\{uv-K(u)\right\\}$ for
$v\in[0,\infty)$. Let $K^{-}\left(v\right):=\sup\\{u\geqslant 0\colon
K\left(u\right)\leq uv\\}$. Write
$a:=\sup\left\\{\frac{\left\|f\right\|_{2}^{2}}{\Phi\left(f\right)}:f\in\mathrm{L}^{2}_{0}\left(\mu\right)\setminus\left\\{0\right\\}\right\\}$,
then

  1. 1.

for $v\in\left[0,a\right)$, it holds that
$K^{-}\left(v\right)\in\left[0,\infty\right)$, and one can write

$K^{*}\left(v\right)=\sup_{0\leq u\leq K^{-}(v)}\left\\{uv-K(u)\right\\};$

  2. 2.

$K^{*}(0)=0$ and for $v\neq 0$, $K^{*}(v)>0$;

  3. 3.

$v\mapsto K^{*}(v)$ is convex, continuous and strictly increasing on its
domain;

  4. 4.

for $v\in\left[0,a\right]$, it holds that $K^{*}(v)\leq v$;

  5. 5.

the function $v\mapsto v^{-1}K^{*}(v)$ is increasing.

###### Proof.

To begin with, take $s\in\left[0,1\right)$, and compute that

$\displaystyle\left\|f\right\|_{2}^{2}$ $\displaystyle\leqslant
s\mathcal{E}\left(P^{*}P,f\right)+\beta\left(s\right)\Phi\left(f\right)$
$\displaystyle\leqslant
s\left\|f\right\|_{2}^{2}+\beta\left(s\right)\Phi\left(f\right).$

Rearranging shows that for all
$f\in\mathrm{L}^{2}_{0}\left(\mu\right)\setminus\left\\{0\right\\}$, it holds
that
$\beta\left(s\right)\geqslant\left(\left\|f\right\|_{2}^{2}/\Phi\left(f\right)\right)\cdot\left(1-s\right)$,
and hence that

$\displaystyle\beta\left(s\right)$
$\displaystyle\geqslant\left(\sup_{f\in\mathrm{L}^{2}_{0}\left(\mu\right)\setminus\left\\{0\right\\}}\frac{\left\|f\right\|_{2}^{2}}{\Phi\left(f\right)}\right)\cdot\left(1-s\right)$
$\displaystyle=a\cdot\left(1-s\right).$

It thus follows that $K\left(u\right)=u\beta\left(1/u\right)\geqslant
a\cdot\left(u-1\right)$. Now, write

$\displaystyle K^{-}(v)$ $\displaystyle=\sup\\{u\geqslant 0\colon
K\left(u\right)\leq uv\\}$ $\displaystyle\leqslant\sup\\{u\geqslant 0\colon
a\cdot\left(u-1\right)\leq uv\\},$

to see that for $v\in\left[0,a\right)$, $K^{-}\left(v\right)<\infty$. Now, for
$u>K^{-}\left(v\right)$, it holds by definition that $K\left(u\right)>u\cdot
v$, and hence that $u\cdot v-K\left(u\right)<0$. Given that at $u=0$, it holds
that $u\cdot v-K\left(u\right)=0$, we can safely restrict the supremum to be
taken over the interval $\left[0,K^{-}\left(v\right)\right]$ as claimed.

Write $K^{*}\left(0\right):=\sup_{u\geq 0}\left\\{-K(u)\right\\}$. By
nonnegativity of $K$, it is clear that $K^{*}\left(0\right)\leqslant 0$, and
taking $u=0$ in the supremum ensures that $K^{*}\left(0\right)=0$. For $v>0$,
note that $u^{-1}K\left(u\right)$ tends to $0$ at $0$, and so there exists
some positive $u$ such that $K\left(u\right)<uv$, from which one can deduce
that $K^{*}\left(v\right)>0$.

Convexity and continuity of $K^{*}$ follow from classical arguments. Moreover,
for $0<v<v^{\prime}$, convexity implies that

$\frac{K^{*}\left(v\right)-K^{*}\left(0\right)}{v}\leqslant\frac{K^{*}\left(v^{\prime}\right)-K^{*}\left(0\right)}{v^{\prime}},$

from which one can deduce that $K^{*}$ is strictly increasing.

To upper-bound $K^{*}$, let $v\in\left[0,a\right]$, and compute

$\displaystyle K^{*}\left(v\right)$ $\displaystyle=\sup_{u\geq
0}\left\\{uv-K\left(u\right)\right\\}$ $\displaystyle\leqslant\sup_{u\geq
0}\left\\{uv-a\cdot\left(u-1\right)\right\\}$
$\displaystyle=a+\sup_{u\geqslant 0}\left\\{u\cdot\left(v-a\right)\right\\}$
$\displaystyle=a,$

so for $v\in\left[0,a\right]$, it holds that $K^{*}\left(v\right)\leqslant a$.
Applying Jensen’s inequality allows us to deduce that
$K^{*}\left(v\right)\leqslant v$ on $\left[0,a\right]$.

The final point follows immediately from convexity of $K^{*}$ and the fact
that $K^{*}(0)=0$.

∎

###### Proof of Lemma 7.

Note that $x\mapsto F_{a}(x)$ is well-defined since $K^{*}$ is continuous and
$K^{*}(v)>0$ and clearly strictly decreasing with $F_{a}\left(a\right)=0$.
Further, $\lim_{x\downarrow 0}F_{a}(x)=\infty$ since $1/K^{*}(v)\geq v^{-1}$
for $0<v<a$ as in Lemma 60. As such, there is a well-defined inverse function
$F_{a}^{-1}:(0,\infty)\to(0,a)$, with $F_{a}^{-1}(x)\to 0$ as $x\to\infty$. ∎

###### Proof of Theorem 8..

Since $v\mapsto 1/K^{*}(v)$ is decreasing and $k\mapsto\|P^{k}f\|_{2}$
decreasing, for $n\geq 1$,

$\displaystyle
F_{a}\big{(}\|P^{n}f\|_{2}^{2}/\Phi(f)\big{)}-F_{a}\big{(}\|P^{n-1}f\|_{2}^{2}/\Phi(f)\big{)}$
$\displaystyle=\int_{\|P^{n}f\|_{2}^{2}/\Phi(f)}^{\|P^{n-1}f\|_{2}^{2}/\Phi(f)}1/K^{*}(v)\,{\rm
d}v$
$\displaystyle\geq\frac{\|P^{n-1}f\|_{2}^{2}-\|P^{n}f\|_{2}^{2}}{K^{*}\big{(}\|P^{n-1}f\|_{2}^{2}/\Phi(f)\big{)}\Phi(f)}$
$\displaystyle=\frac{\mathcal{E}(P^{*}P,P^{n-1}f)/\Phi(f)}{K^{*}\big{(}\|P^{n-1}f\|_{2}^{2}/\Phi(f)\big{)}}.$

Now, applying the optimised super-Poincaré inequality with $f$ replaced by
$P^{n-1}f$, one can bound

$\frac{\mathcal{E}\left(P^{*}P,P^{n-1}f\right)}{\Phi\left(P^{n-1}f\right)}\geqslant
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(P^{n-1}f\right)}\right).$

By assumption, $\Phi\left(P^{n-1}f\right)\leqslant\Phi\left(f\right)$, and
hence
$\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(P^{n-1}f\right)}\geqslant\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}$.
Additionally, since $u\mapsto u^{-1}K^{*}\left(u\right)$ is increasing (Lemma
60), we obtain the conclusion

$\displaystyle\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(P^{n-1}f\right)}\right)^{-1}\cdot
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(P^{n-1}f\right)}\right)$
$\displaystyle\geqslant\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}\right)^{-1}\cdot
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}\right)$
$\displaystyle\implies
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(P^{n-1}f\right)}\right)$
$\displaystyle\geqslant\left(\frac{\Phi\left(f\right)}{\Phi\left(P^{n-1}f\right)}\right)\cdot
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}\right).$

We thus see that

$\displaystyle\frac{\mathcal{E}\left(P^{*}P,P^{n-1}f\right)}{\Phi\left(P^{n-1}f\right)}$
$\displaystyle\geqslant\frac{\Phi\left(f\right)}{\Phi\left(P^{n-1}f\right)}\cdot
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}\right)$
$\displaystyle\implies\frac{\mathcal{E}\left(P^{*}P,P^{n-1}f\right)}{\Phi\left(f\right)}$
$\displaystyle\geqslant
K^{*}\left(\frac{\left\|P^{n-1}f\right\|_{2}^{2}}{\Phi\left(f\right)}\right).$

Combining this with our earlier inequalities, we see that
$F_{a}\big{(}\|P^{n}f\|_{2}^{2}/\Phi(f)\big{)}-F_{a}\big{(}\|P^{n-1}f\|_{2}^{2}/\Phi(f)\big{)}\geqslant
1$. As a result, for $n\geq 1$, it holds that

$F_{a}\big{(}\|P^{n}f\|_{2}^{2}/\Phi(f)\big{)}-F_{a}\big{(}\|f\|_{2}^{2}/\Phi(f)\big{)}\geq
n,$

from which we obtain

$\|P^{n}f\|_{2}^{2}\leq\Phi\left(f\right)F_{a}^{-1}(n).$

∎

Weak Poincaré inequalities were considered in [31], who used it to derive
subexponential convergence rates for continuous-time Markov semigroups. We
give here the analogous discrete-time result, and note that the obtained rate
is weaker than our previous Theorem 8.

######  Proposition 61.

Assume that a weak Poincaré inequality for $P^{*}P$ holds as in Definition 1.
Then, for any $f\in\mathrm{L}^{2}_{0}(\mu)$ with $\Phi(f)<\infty$, we have the
bound

$\|P^{n}f\|_{2}^{2}\leq\tilde{\gamma}(n)\left(\|f\|_{2}^{2}+\Phi(f)\right),$

where

$\tilde{\gamma}(n)=\inf\left\\{r>0\colon\big{(}1-1/\alpha(r)\big{)}^{n}\leq
r\right\\},$ (15)

and $\tilde{\gamma}$ satisfies $\gamma(n)\downarrow 0,$ as $n\to\infty$,
replacing $\alpha$ with $\alpha\vee 1$ if necessary.

###### Proof.

We will use the following identity; for any $g\in\mathrm{L}^{2}(\mu)$,

$\displaystyle\|Pg\|_{2}^{2}-\|g\|_{2}^{2}$
$\displaystyle=\bigl{\langle}P^{*}Pg,g\bigr{\rangle}-\bigl{\langle}g,g\bigr{\rangle}$
$\displaystyle=-\mathcal{E}(P^{*}P,g).$

This implies in particular for $n\geq 1$,

$\displaystyle\|P^{n}f\|_{2}^{2}-\|P^{n-1}f\|_{2}^{2}$
$\displaystyle=-\mathcal{E}(P^{*}P,P^{n-1}f)$
$\displaystyle\leq-\|P^{n-1}f\|_{2}^{2}/\alpha(r)+(r/\alpha(r))\Phi(P^{n-1}f).$

Therefore with $u_{n}:=\|P^{n}f\|_{2}^{2}$ and using the nonexpansive property
of $\Phi$, we have

$u_{n}\leq\big{(}1-1/\alpha(r)\big{)}u_{n-1}+(r/\alpha(r))\Phi(f),$ (16)

and by iterating this, we obtain

$\displaystyle u_{n}$
$\displaystyle\leq\big{(}1-1/\alpha(r)\big{)}^{n}u_{0}+r\Phi(f).$

Thus if we define $\tilde{\gamma}(n)$ as in (15), the desired bound on
$\|P^{n}f\|_{2}^{2}$ is immediate. ∎

######  Remark 62.

The rate (15) is weaker than the rate of Theorem 8 because in the proof of
Theorem 8, we are essentially optimizing over $r>0$ at every step of the
iteration (16), rather than fixing the same $r>0$ for every iteration and then
optimizing only at the end as in (15).

###### Proof of Lemma 13.

For the first part, notice that
$u[v-c_{1}\beta(c_{2}/u)]=c_{1}c_{2}(u/c_{2})\\{v/c_{1}-\beta(c_{2}/u)\\}$.
Then,

$\tilde{F}_{\infty}(w)=\int_{w}^{\infty}\frac{{\rm
d}v}{c_{1}c_{2}K^{*}(v/c_{1})}=\frac{1}{c_{2}}\int_{w/c_{1}}^{\infty}\frac{c_{1}{\rm
d}v^{\prime}}{c_{1}K^{*}(v^{\prime})}=c_{2}^{-1}F_{\infty}(w/c_{1}),$

and the result follows. ∎

###### Proof of Lemma 14..

From direct calculation, we find that

$K^{*}(v)=C\left(c_{0},c_{1}\right)v^{1+c_{1}^{-1}},$

where
$C\left(c_{0},c_{1}\right):=\frac{c_{0}c_{1}}{\left(c_{0}(1+c_{1})\right)^{1+c_{1}^{-1}}}$.
We then calculate that, for a fixed $a>0$,

$F(v)=\int_{w}^{a}\frac{\mathrm{d}v}{K^{*}(v)}=\tilde{C}\left(c_{0},c_{1}\right)\left[w^{-c_{1}^{-1}}-a^{-c_{1}^{-1}}\right],$

with
$\tilde{C}\left(c_{0},c_{1}\right):=c_{1}/C\left(c_{0},c_{1}\right)=(1+c_{1})^{1+c_{1}^{-1}}c_{0}^{c_{1}^{-1}}$.
Inverting this, we find that

$\displaystyle F^{-1}(n)$
$\displaystyle=\left(\frac{1}{n/\tilde{C}\left(c_{0},c_{1}\right)+a^{-c_{1}^{-1}}}\right)^{c_{1}}$
$\displaystyle\leq\tilde{C}\left(c_{0},c_{1}\right)^{c_{1}}n^{-c_{1}}$
$\displaystyle=c_{0}(1+c_{1})^{1+c_{1}}n^{-c_{1}}.$

∎

###### Proof of Lemma 15..

We have

$\displaystyle K^{*}(v)$
$\displaystyle=\sup_{u\in[0,\infty)}\left\\{uv-u\eta_{0}\exp\left(-\eta_{1}u^{-\eta_{2}}\right)\right\\}.$

For some $\eta>0$ and $v\in(0,1]$, take
$u_{v}:=\left(\frac{1}{\eta}\log\left(\frac{1}{v}\right)\right)^{-1/\eta_{2}}$,
that is such that $v=\exp\left(-\eta u_{v}^{-\eta_{2}}\right)<1$. As a result
we have a lower bound on $K^{*}$ as

$K^{*}(v)\geqslant
v\left(\frac{1}{\eta}\log\left(\frac{1}{v}\right)\right)^{-1/\eta_{2}}-\eta_{0}v^{\eta_{1}/\eta}.$

Provided that $\eta\text{$\in\left(0,\eta_{1}\right)$}$, the second term will
decay faster as $v\downarrow 0$ and the first statement follows.

The second statement follows upon noticing that for $0\leq w\leq v_{0}$, and
writing $M:=\int_{v_{0}}^{a}\frac{\mathrm{d}v}{K^{*}(v)}$,

$\displaystyle F_{a}(w)$ $\displaystyle\leq
C^{-1}\int_{w}^{v_{0}}v^{-1}\left(-\log v\right)^{1/\eta_{2}}{\rm d}v+M$
$\displaystyle=C^{-1}\frac{\eta_{2}}{1+\eta_{2}}\left[\left(-\log
w\right)^{(\eta_{2}+1)/\eta_{2}}-\left(-\log
v_{0}\right)^{(\eta_{2}+1)/\eta_{2}}\right]+M$ $\displaystyle\leq
C^{-1}\frac{\eta_{2}}{1+\eta_{2}}\left(-\log
w\right)^{(\eta_{2}+1)/\eta_{2}}+M.$

This leads for $n\geq M$ to

$F_{a}^{-1}(n)\leq\exp\left(-\left(C\frac{1+\eta_{2}}{\eta_{2}}(n-M)\right)^{\eta_{2}/(1+\eta_{2})}\right).$

For $n\geq M$, by concavity of $[0,M]\ni x\mapsto(n-x)^{\gamma}$ for
$\gamma\in(0,1)$ we have
$n^{\gamma}-\gamma(n-M)^{\gamma-1}M\leq(n-M)^{\gamma}$ and
$(n-M)^{\gamma-1}\leq(\lceil M\rceil-M)^{\gamma-1}$ so we conclude that there
exists $C^{\prime}>0$ such that for $n\in\mathbb{N}$,

$F_{a}^{-1}(n)\leq
C^{\prime}\exp\left(-\left(C\frac{1+\eta_{2}}{\eta_{2}}n\right)^{\eta_{2}/(1+\eta_{2})}\right).$

∎

###### Proof of Lemma 17.

From routine calculations, the conclusion is equivalent to

$(1-c_{\mathrm{gap}})\langle
f,f\rangle\geq\langle(P^{2}-c_{\mathrm{gap}}P)f,f\rangle.$

By the spectral theorem [9, Chapter 9], this can be expressed as

$(1-c_{\mathrm{gap}})\int_{-1}^{1}\mathrm{d}\nu_{f}(\lambda)\geq\int_{-1}^{1}(\lambda^{2}-c_{\mathrm{gap}}\lambda)\,\mathrm{d}\nu_{f}(\lambda).$
(17)

It is easily seen that for any $0<c\leq 1$ we have that,
$\lambda^{2}-c\lambda\leq 1-c$ for all $\lambda\geq-1+c$. By choosing
$c=c_{\mathrm{gap}}$, and see that equation (17) holds for this choice of $c$
under the assumption of a left spectral gap. ∎

###### Proof of Proposition 21.

The proof borrows ideas from [31]. Recall that a super-Poincaré inequality
holds if we can find a function $\beta$ such that for all $f$ satisfying
$\Phi\left(f\right)<\infty$, it holds that $\|f\|_{2}^{2}\leq
s\mathcal{E}(P^{*}P,f)+\beta(s)\Phi(f)$. The sharpest such $\beta$ can then be
recovered as

$\beta\left(s\right):=\sup_{f:0<\Phi\left(f\right)<\infty}\left\\{\frac{\|f\|_{2}^{2}}{\Phi(f)}-s\frac{\mathcal{E}(P^{*}P,f)}{\Phi\left(f\right)}\right\\}.$

Defining
$u\left(f\right):=\frac{\|f\|_{2}^{2}}{\Phi(f)},v\left(f\right):=\frac{\mathcal{E}(P^{*}P,f)}{\Phi\left(f\right)}$,
we thus seek to find uniform upper bounds on the scale-free quantity
$u\left(f\right)-s\cdot v\left(f\right)$ over the set of such $f$.

By self-adjointness of $P$, for any $n\geqslant 0$ we can apply the spectral
theorem to write

$P^{n}=\int_{\sigma\left(P\right)}\lambda^{n}\,\mathrm{d}E_{\lambda},$

where $\sigma\left(P\right)$ is the spectrum of $P$ and
$\left\\{E_{\lambda}:\lambda\in\sigma\left(P\right)\right\\}$ is the
corresponding spectral family. For $f\in\mathrm{L}^{2}_{0}\left(\mu\right)$
such that $\|f\|_{2}^{2}=1$, write

$\|P^{n}f\|_{2}^{2}=\int_{\sigma\left(P\right)}\left|\lambda\right|^{2n}\,\mathrm{d}\left\|E_{\lambda}f\right\|^{2}\geqslant\left(\int_{\sigma\left(P\right)}\left|\lambda\right|^{2}\,\mathrm{d}\left\|E_{\lambda}f\right\|^{2}\right)^{n}=\left\|Pf\right\|_{2}^{2n},$

noting that $\mathrm{d}\left\|E_{\lambda}f\right\|^{2}$ is a probability
measure and applying Jensen’s inequality. By a scaling argument, one can then
deduce that
$\left\|Pf\right\|_{2}\leqslant\left\|f\right\|_{2}^{1-1/n}\cdot\left\|P^{n}f\right\|_{2}^{1/n}$.

Combining this with our assumption, we obtain the estimate
$\left\|Pf\right\|_{2}^{2}\leqslant\left\|f\right\|_{2}^{2\left(1-1/n\right)}\cdot\left(\gamma\left(n\right)\cdot\Phi\left(f\right)\right)^{1/n}$.
Rearranging this, we see that

$\displaystyle\mathcal{E}\left(P^{*}P,f\right)$
$\displaystyle=\|f\|_{2}^{2}-\left\|Pf\right\|_{2}^{2}\geqslant\|f\|_{2}^{2}-\left\|f\right\|_{2}^{2\left(1-1/n\right)}\cdot\left(\gamma\left(n\right)\cdot\Phi\left(f\right)\right)^{1/n},$

and dividing through by $\Phi\left(f\right)$ tells us that
$v\left(f\right)\geqslant
u\left(f\right)-\gamma\left(n\right)^{1/n}u\left(f\right)^{1-1/n}$. One can
then write that

$\displaystyle u\left(f\right)-s\cdot v\left(f\right)$ $\displaystyle\leqslant
s\cdot\gamma\left(n\right)^{1/n}u\left(f\right)^{1-1/n}-\left(s-1\right)\cdot
u\left(f\right)$
$\displaystyle\leqslant\frac{s^{n}}{\left(s-1\right)^{n-1}}\cdot\frac{\left(n-1\right)^{n-1}}{n^{n}}\cdot\gamma\left(n\right),$

where the second inequality comes from taking the supremum of the right-hand
side over $u\left(f\right)>0$, provided that $n\geqslant 2$. One can then
deduce that

$\beta\left(s\right)=\sup_{f:0<\Phi\left(f\right)<\infty}\left\\{u\left(f\right)-s\cdot
v\left(f\right)\right\\}\leqslant\inf_{n\geq
2}\left\\{\frac{s^{n}}{\left(s-1\right)^{n-1}}\cdot\frac{\left(n-1\right)^{n-1}}{n^{n}}\cdot\gamma\left(n\right)\right\\}=:\beta_{0}\left(s\right).$

Defining $\beta_{1}\left(s\right):=\sup_{t\geqslant
s}\beta_{0}\left(t\right)$, one can see that $\beta_{1}$ is also a valid upper
bound, and is decreasing. Moreover, writing $s=n+\delta$ with
$n\in\text{$\mathbb{N}$},\delta\in\left[0,1\right)$, one can bound

$\displaystyle\beta_{0}\left(s\right)$
$\displaystyle\leqslant\frac{s^{n}}{\left(s-1\right)^{n-1}}\cdot\frac{\left(n-1\right)^{n-1}}{n^{n}}\cdot\gamma\left(n\right)$
$\displaystyle=\left(\frac{n+\delta}{n}\right)^{n}\cdot\left(\frac{n-1}{n-1+\delta}\right)^{n-1}\cdot\gamma\left(n\right)$
$\displaystyle\leqslant\exp\left(\delta\right)\cdot
1\cdot\gamma\left(n\right)$ $\displaystyle\leqslant
e\cdot\gamma\left(\left\lfloor s\right\rfloor\right),$

which vanishes as $s$ grows. Moreover, since $\gamma$ is decreasing, one can
write

$\beta_{1}\left(s\right)=\sup_{t\geqslant s}\beta_{0}\left(t\right)\leqslant
e\cdot\sup_{t\geqslant s}\gamma\left(\left\lfloor
t\right\rfloor\right)=e\cdot\gamma\left(\left\lfloor s\right\rfloor\right),$

to conclude that $\beta_{1}$ decreases to $0$. ∎

###### Proof of Lemma 27.

Direct calculation:

$\displaystyle\frac{\pi\otimes\pi(A(s)^{\complement})}{2}$
$\displaystyle=\frac{1}{2}\left[1-\int_{A(s)}\mathrm{d}x\,\mathrm{d}y\,a_{1}^{2}\exp\left(-a_{1}(x+y)\right)\right]$
$\displaystyle=\frac{1}{2}\left[1-\int_{0}^{\frac{\log
s}{a_{2}-a_{1}}}\mathrm{d}x\int_{0}^{\frac{\log
s}{a_{2}-a_{1}}}\mathrm{d}y\,a_{1}^{2}\exp\left(-a_{1}(x+y)\right)\right]$
$\displaystyle=\frac{1}{2}\left[1-\int_{0}^{\frac{\log
s}{a_{2}-a_{1}}}\mathrm{d}x\,a_{1}\exp(-a_{1}x)\left[-\exp(-a_{1}y)\right]_{0}^{\frac{\log
s}{a_{2}-a_{1}}}\right]$
$\displaystyle=\frac{1}{2}\left[1-\int_{0}^{\frac{\log
s}{a_{2}-a_{1}}}\mathrm{d}x\,a_{1}\exp(-a_{1}x)\left(1-s^{-\frac{a_{1}}{a_{2}-a_{1}}}\right)\right]$
$\displaystyle=\frac{1}{2}\left[1-\left(1-s^{-\frac{a_{1}}{a_{2}-a_{1}}}\right)^{2}\right].$

The inequality follows from
$1-\left(1-s^{-\frac{a_{1}}{a_{2}-a_{1}}}\right)^{2}=\left(2-s^{-\frac{a_{1}}{a_{2}-a_{1}}}\right)s^{-\frac{a_{1}}{a_{2}-a_{1}}}$.
∎

##  Appendix B Proofs for Section 4

###### Proof of Lemma 47..

We centre the $W_{i}$, which are nonnegative, and then use the binomial
theorem: writing $\overline{W}_{i}:=W_{i}-1$ for each $i$,

$\displaystyle\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}W_{i}\right|^{p}\right]$
$\displaystyle=\mathbb{E}\left[\left(1+\frac{1}{N}\sum_{i=1}^{N}\overline{W}_{i}\right)^{p}\right]$
$\displaystyle=1+\sum_{k=2}^{p}\left(\begin{array}[]{c}p\\\
k\end{array}\right)\mathbb{E}\left[\left(\frac{1}{N}\sum_{i=1}^{N}\overline{W}_{i}\right)^{k}\right]$
$\displaystyle\leq 1+\sum_{k=2}^{p}\left(\begin{array}[]{c}p\\\
k\end{array}\right)\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}\overline{W}_{i}\right|^{k}\right],$

where we used the fact that each $\mathbb{E}\overline{W}_{i}=0$ to cancel the
$k=1$ summand. We now make use of the Marcinkiewicz–Zygmund inequality, which
tells us that for $k\geq 2$, there exist universal constants
$\left\\{B_{k}\right\\}$, such that

$\displaystyle\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}\overline{W}_{i}\right|^{k}\right]$
$\displaystyle\leq
B_{k}\mathbb{E}\left[\left(\frac{1}{N^{2}}\sum_{i=1}^{N}\overline{W}_{i}^{2}\right)^{k/2}\right]$
$\displaystyle\leq
B_{k}N^{-k/2}\mathbb{E}\left[\left|\overline{W}_{1}\right|^{k}\right],$

where for the latter inequality we use Minkowski’s inequality with exponent
$k/2$. This gives us the bound, for some constants $\left\\{C_{p,k}\right\\}$,

$\mathbb{E}\left[\left|\frac{1}{N}\sum_{i=1}^{N}W_{i}\right|^{p}\right]\leq
1+\sum_{k=2}^{p}N^{-k/2}C_{p,k}\mathbb{E}\left[\left|\overline{W}_{1}\right|^{k}\right].$

∎

###### Proof of Proposition 48..

Since under $Q_{x}$, $\ell_{{\rm
ABC}}(x)\sum_{j=1}^{N}W(z_{j})\sim\mathrm{Bin}\big{(}N,\ell_{{\rm
ABC}}(x)\big{)}$, we can write

$Q_{x}\left[\mathcal{W}_{N}^{p+1}\right]=\frac{\mathbb{E}\left[\mathrm{Bin}(N,\ell_{{\rm
ABC}}(x))^{p+1}\right]}{(N\ell_{{\rm ABC}}(x))^{p+1}}.$

The (non-centered) moments of a binomial random variable are known [23] to
have the form,

$\mathbb{E}\left[\mathrm{Bin}(N,\ell_{{\rm
ABC}}(x))^{p+1}\right]=\sum_{k=1}^{p+1}c_{p+1,k}N^{\underline{k}}\ell_{{\rm
ABC}}(x)^{k},$

for appropriate coefficients $c_{p+1,k}$ and where
$N^{\underline{k}}=N(N-1)\cdots(N-k+1)$ is the $k$th falling power of $N$. The
result follows immediately from this identity. ∎

###### Proof of Proposition 49..

We observe that by independence, we may write for a given $x\in\mathsf{X}$,

$Q_{x}(W^{p})=Q_{x}\left(\prod_{t=1}^{T}W_{t}^{p}\right)=\prod_{t=1}^{T}Q_{x,t}\left(W_{t}^{p}\right),$

for some distributions $Q_{x,1},\ldots,Q_{x,T}$. By Lemma 47, we have (with
dependence on $t$ and $x$ suppressed from $C_{p,k}$)

$\displaystyle Q_{x,t}\left(W_{t}^{p}\right)$ $\displaystyle\leq
1+\sum_{k=2}^{p}N^{-k/2}C_{p,k}Q_{x,t}\left[|W_{t}-1|^{k}\right]$
$\displaystyle\leq
1+\max_{k\in\\{2,\ldots,p\\}}\left\\{C_{p,k}Q_{x,t}\left[|W_{t}-1|^{k}\right]\right\\}\sum_{k=2}^{p}N^{-k/2}$
$\displaystyle=:1+M_{t,p}\sum_{k=2}^{p}N^{-k/2},$

for some constants $\\{C_{p,k}\\}$ and $M_{t,p}$. Since
$\sum_{k=2}^{\infty}N^{-k/2}=1/(N-\sqrt{N})$, we deduce that there exists
functions $M_{t,p}\leq M_{p}$ such that for any $x\in\mathsf{X}$,

$Q_{x}(W^{p})=Q_{x}\left(\prod_{t=1}^{T}W_{t}^{p}\right)\leq\prod_{t=1}^{T}\left(1+\frac{M_{t,p}(x)}{N-\sqrt{N}}\right)\leq\left(1+\frac{M_{p}(x)}{N-\sqrt{N}}\right)^{T}.$

For the given choice of $N$,

$Q_{x}(W^{p})\leq\left(1+\frac{M_{p}(x)}{\alpha
T}\right)^{T}\leq\exp\left(\frac{M_{p}(x)}{\alpha}\right).$

Hence, we obtain,

$\displaystyle\int\pi({\rm d}x)\tilde{\pi}_{x}(W\geq s)$
$\displaystyle\leq\int\pi({\rm d}x)\frac{\tilde{\pi}_{x}(W^{p-1})}{s^{p-1}}$
$\displaystyle=\int\pi({\rm d}x)\frac{Q_{x}(W^{p})}{s^{p-1}}$
$\displaystyle\leq s^{-p+1}\int\pi({\rm
d}x)\exp\left(\frac{M_{p}(x)}{\alpha}\right),$

as required. ∎

###### Proof of Lemma 51..

We calculate directly: recalling that
$\tilde{\pi}_{x}(\mathrm{d}w)=wQ_{x}(\mathrm{d}w)$,

$\displaystyle\tilde{\pi}_{x}(W$ $\displaystyle\geq
s)=\int_{s}^{\infty}\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{\left(\log
w+\sigma^{2}/2\right)^{2}}{2\sigma^{2}}\right)\,\mathrm{d}w$
$\displaystyle=\frac{1}{\sigma\sqrt{2\pi}}\int_{\log
s}^{\infty}\exp\left(-\frac{\left(z-\sigma^{2}/2\right)^{2}}{2\sigma^{2}}\right)\,\mathrm{d}z$
$\displaystyle=\mathbb{P}\left(Z\geq\frac{\log
s-\sigma^{2}/2}{\sigma}\right),$

where we used the substitution $z=\log w$, and in the final expression
$Z\sim\mathcal{N}(0,1)$. The result then follows from standard sub-Gaussian
tail bounds, e.g. [36, Chapter 2, Prop. 2.5]. ∎

###### Proof of Lemma 54..

This follows by first bounding $F(w)$ using Lemma 53:

$\displaystyle F(w)$ $\displaystyle=\int_{w}^{1}\frac{\mathrm{d}v}{K^{*}(v)}$
$\displaystyle\leq
2\exp(\sigma^{2}/2)\int_{w}^{1}\frac{1}{v}\exp\left(\sigma\sqrt{-2\log\frac{v}{2}}\right)\,\mathrm{d}v$
$\displaystyle=2\exp(\sigma^{2}/2)\int_{-\log\frac{1}{2}}^{-\log\frac{w}{2}}\exp\left(\sigma\sqrt{2z}\right)\,\mathrm{d}z$
$\displaystyle=2\exp(\sigma^{2}/2)\left[\sigma^{-2}\exp\left(\sigma\sqrt{2z}\right)\left(\sigma\sqrt{2z}-1\right)\right]_{-\log\frac{1}{2}}^{-\log\frac{w}{2}}$
$\displaystyle\leq
2\exp(\sigma^{2}/2)\sigma^{-2}\exp\left(\sigma\sqrt{-2\log\frac{w}{2}}\right)\sigma\sqrt{-2\log\frac{w}{2}}.$

where we made use of the substitution $z=-\log\frac{v}{2}$. The result then
follows from inverting this relationship, using the fact that $\mathsf{W}$ is
the inverse of the map $x\mapsto x\exp(x)$. ∎

###### Proof of Proposition 57..

For notational simplicity we may drop the argument of some of the functions
involved. Let $C=\mathsf{B}C_{\mathrm{P}}/2\sigma_{0}^{2}$ then the constraint
gives

$-\frac{1}{\sigma^{2}}\mathsf{W}^{2}\left(\frac{C\sigma^{4}}{\exp(\sigma^{2}/2)}\right)=-H(\epsilon)=-2\log\left(\frac{2}{C_{{\rm
P}}\epsilon^{2}}\right).$

We may express $C$ in terms of $\sigma$,

$C(\sigma)=\sqrt{H}\frac{\exp\left(\sigma^{2}/2+\sigma\sqrt{H}\right)}{\sigma^{3}},$

which we optimise w.r.t. $\sigma$, to obtain the minimiser
$\bar{\sigma}_{\star}=(-\sqrt{H}+\sqrt{H+12})/2.$ Since

$\frac{6}{H(1+12/H)^{1/2}}\leq\frac{1}{2}\int_{0}^{12/H}(1+u)^{-1/2}{\rm
d}u\leq\frac{6}{H},$

for $H\geq 1$,

$\frac{1}{4}\frac{3}{\sqrt{H}}\leq\frac{3}{\sqrt{H}(1+12/H)^{1/2}}\leq\bar{\sigma}_{\star}\leq\frac{3}{\sqrt{H}},$

while $\lim_{H\to\infty}\sqrt{H}\bar{\sigma}_{\star}=3$. We may bound the
budget by taking $\bar{\sigma}(\epsilon)=3/\sqrt{H(\epsilon)}$ so
$\bar{N}(\epsilon)=\sigma_{0}^{2}H(\epsilon)/9$,

$\mathsf{B}(\epsilon)=\frac{2\sigma_{0}^{2}}{C_{{\rm
P}}}C(\sigma(\epsilon))=\frac{2\sigma_{0}^{2}H(\epsilon)^{2}\exp\left(\frac{9}{2H}+3\right)}{27C_{{\rm
P}}}\leq\frac{2\sigma_{0}^{2}H(\epsilon)^{2}\exp\left(15/2\right)}{27C_{{\rm
P}}},$

and we have

$\bar{n}(\epsilon)\leq\frac{2H(\epsilon)\exp\left(15/2\right)}{3C_{{\rm P}}}.$

Taking $H(\epsilon)=2\log\left(\frac{2}{C_{{\rm P}}\epsilon^{2}}\right)$ then
gives the result. ∎

###### Proof of Lemma 58..

We use the following expression for the asymptotic variance,

$\displaystyle v(f,P)$
$\displaystyle=2\langle(\mathrm{Id}-P)^{-1}f,f\rangle-\|f\|_{2}^{2}$
$\displaystyle=2\sum_{n=0}^{\infty}\langle f,P^{n}f\rangle-\|f\|_{2}^{2}$
$\displaystyle=2\sum_{l=0}^{\infty}\left\langle
P^{l}f,(I+P)P^{l}f\right\rangle-\|f\|_{2}^{2}$ $\displaystyle\leq
4\sum_{l=0}^{\infty}\|P^{l}f\|_{2}^{2}-\|f\|_{2}^{2}$ $\displaystyle\leq
4\sum_{l=0}^{\infty}\Phi(f)F^{-1}(l)-\|f\|_{2}^{2}.$

∎

## Acknowledgments

We would like to thank Gareth Roberts for useful comments. Research of CA, AL
and AQW supported by EPSRC grant ‘CoSInES (COmputational Statistical INference
for Engineering and Security)’ (EP/R034710/1), and research of CA and SP
supported by EPSRC grant Bayes4Health, ‘New Approaches to Bayesian Data
Science: Tackling Challenges from the Health Sciences’ (EP/R018561/1).

## References

  * [1] Andrieu, C., Doucet, A., & Holenstein, R. (2010). Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society. Series B: Statistical Methodology, 72(3), 269–342.
  * [2] Andrieu, C., & Roberts, G. O. (2009). The pseudo-marginal approach for efficient Monte Carlo computations. The Annals of Statistics, 37(2), 697–725.
  * [3] Andrieu, C., & Vihola, M. (2015). Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms. Annals of Applied Probability, 25(2), 1030–1077.
  * [4] Bakry, D., Cattiaux, P., & Guillin, A. (2008). Rate of convergence for ergodic continuous Markov processes: Lyapunov versus Poincaré. Journal of Functional Analysis, 254(3), 727–759.
  * [5] Bérard, J., Moral, P. Del, & Doucet, A. (2014). A lognormal central limit theorem for particle approximations of normalizing constants. Electron. J. Probab., 19, 1–28.
  * [6] Bornn, L., Pillai, N., Smith A. and D. Woodard (2014). One pseudo-sample is enough in approximate Bayesian computation MCMC. Biometrika, 99(1), 1–10, 2014.
  * [7] Caracciolo, S., Pelissetto, A. & Sokal, A.D. (1990). Nonlocal Monte Carlo algorithm for self-avoiding walks with fixed endpoints. J. Stat. Phys. 60, 1–53.
  * [8] Cattiaux, P., Guillin, A., & Roberto, C. (2010). Poincaré inequality and the Lp convergence of semigroups. Electronic Communications in Probability, 15, 270–280.
  * [9] Conway, J. B. (1990). A Course in Functional Analysis (2nd ed.). Springer-Verlag.
  * [10] Deligiannidis, G., & Lee, A. (2018). Which ergodic averages have finite asymptotic variance?. The Annals of Applied Probability, 28(4), 2309-2334.
  * [11] Diaconis, P., & Saloff-Coste, L. (1996). Nash Inequalities for Finite Markov Chains. Journal of Theoretical Probability, 9(2), 459–510.
  * [12] Donohue, M. C., Overholser, R., Xu, R., & Vaida, F. (2011). Conditional Akaike information under generalized linear and proportional hazards mixed models. Biometrika, 98(3), 685–700.
  * [13] Douc, R., Moulines, E., Priouret, P., & Soulier, P. (2018). Markov Chains. In Springer Series in Operations Research and Financial Engineering (1st ed.).
  * [14] Douc, R., Fort, G., Moulines, E., & Soulier, P. (2004). Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Probab., 14(3), 1353–1377.
  * [15] Douc, R., Moulines, E., & Soulier, P. (2007). Computable convergence rates for sub-geometric ergodic Markov chains. Bernoulli, 13(3), 831–848.
  * [16] Doucet, A., Pitt, M. K., Deligiannidis, G., & Kohn, R. (2015). Efficient implementation of Markov chain Monte Carlo when using an unbiased likelihood estimator. Biometrika, 102(2), 295-313.
  * [17] Gåsemyr, J. (2006). The Spectrum of the Independent Metropolis–Hastings Algorithm. Journal of Theoretical Probability, 19(1), 152–165.
  * [18] Fill, J. A. (1991). Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process. The Annals of Applied Probability, 1(1), 62–87.
  * [19] Greenberg, E. R., Baron, J. A., Stukel, T. A., Stevens, M. M., Mandel, J. S., Spencer, S. K., … & Skin Cancer Prevention Study Group. (1990). A clinical trial of beta carotene to prevent basal-cell and squamous-cell cancers of the skin. New England Journal of Medicine, 323(12), 789-795.
  * [20] Jarner, S. F., & Roberts, G. O. (2002). Polynomial convergence rates of Markov chains. Annals of Applied Probability, 12(1), 224–247.
  * [21] Jarner, S. F., & Roberts, G. O. (2007). Convergence of Heavy-tailed Monte Carlo Markov Chain Algorithms. Scandinavian Journal of Statistics, 34(4), 781–815.
  * [22] Khare, K. and Hobert, J. P. (2011). A spectral analytic comparison of trace- class data augmentation algorithms and their sandwich variants. Annals of Statistics 39(5), 2585–2606.
  * [23] Knoblauch, A. (2008). Closed-Form Expressions for the Moments of the Binomial Probability Distribution. SIAM Journal on Applied Mathematics, 69(1), 197–204.
  * [24] Kontoyiannis, I., & Meyn, S. P. (2003). Spectral theory and limit theorems for geometrically ergodic Markov processes. The Annals of Applied Probability, 13(1), 304–362.
  * [25] Lee, A., & Łatuszyński, K. (2014). Variance bounding and geometric ergodicity of Markov chain Monte Carlo kernels for approximate Bayesian computation. Biometrika, 101(3), 655–671.
  * [26] Lee, A., Tiberi, S., & Zanella, G. (2019). Unbiased approximations of products of expectations. Biometrika, 106(3), 708-715.
  * [27] Meyn, S.P. and Tweedie, R.L. (2012). Markov Chains and Stochastic Stability. Springer Science & Business Media.
  * [28] Peccoud, J., & Ycart, B. (1995). Markovian modeling of gene-product synthesis. Theoretical population biology, 48(2), 222-234.
  * [29] Rosenthal, J. S. (1995). Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo. Journal of the American Statistical Association, 90(430), 558–566.
  * [30] Roberts, G.O., Gelman, A., Gilks, W.R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Probab. 7(1) 110–120.
  * [31] Röckner, M., & Wang, F.-Y. (2001). Weak Poincaré Inequalities and L2 Convergence Rates of Markov Semigroups. Journal of Functional Analysis, 185, 564–603.
  * [32] Sherlock, C., Thiery, A. H., Roberts, G. O., & Rosenthal, J. S. (2015). On the efficiency of pseudo-marginal random walk Metropolis algorithms. The Annals of Statistics, 43(1), 238-275.
  * [33] Sherlock, C., Thiery, A. H., & Lee, A. (2017). Pseudo-marginal Metropolis–Hastings sampling using averages of unbiased estimators. Biometrika, 104(3), 727–734.
  * [34] Tiberi, S., Walsh, M., Cavallaro, M., Hebenstreit, D., & Finkenstädt, B. (2018). Bayesian inference on stochastic gene transcription from flow cytometry data. Bioinformatics, 34(17), i647–i655.
  * [35] Tran, M. N., Kohn, R., Quiroz, M., & Villani, M. (2016). The block pseudo-marginal sampler. arXiv preprint arXiv:1603.02485.
  * [36] Wainwright, M. J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press.