{'fraction_non_alphanumeric': 0.05796155404492864, 'fraction_numerical': 0.01640930986359339, 'mean_word_length': 4.1065517241379315, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms

We study convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms (Andrieu and Roberts [Ann. Statist. 37 (2009) 697-725]). We find that the asymptotic variance of the pseudo-marginal algorithm is always at least as large as that of the marginal algorithm. We show that if the marginal chain admits a (right) spectral gap and the weights (normalised estimates of the target density) are uniformly bounded, then the pseudo-marginal chain has a spectral gap. In many cases, a similar result holds for the absolute spectral gap, which is equivalent to geometric ergodicity. We consider also unbounded weight distributions and recover polynomial convergence rates in more specific cases, when the marginal algorithm is uniformly ergodic or an independent Metropolis-Hastings or a random-walk Metropolis targeting a super-exponential density with regular contours. Our results on geometric and polynomial convergence rates imply central limit theorems. We also prove that under general conditions, the asymptotic variance of the pseudo-marginal algorithm converges to the asymptotic variance of the marginal algorithm if the accuracy of the estimators is increased.


Introduction
Assume that one is interested in sampling from a probability distribution π defined on some measurable space (X, B(X)). One practical recipe to achieve this in complex scenarios consists of using Markov chain Monte Carlo (MCMC) methods, of which the Metropolis-Hastings update is the main workhorse [14,23]. We may write the Markov kernel related to a Metropolis-Hastings algorithm in the form (1) P (x, dy) := min {1, r(x, y)} q(x, dy) + δ x (dy)ρ(x), where r(x, y) is the Radon-Nikodym derivative as defined in [34] (2) r(x, y) := π(dy)q(y, dx) π(dx)q(x, dy) and ρ(x) := 1 − min{1, r(x, y)}q(x, dy), where q is the so-called proposal kernel (or proposal distribution). We follow the terminology of [4] and call this method the marginal algorithm.
In some situations, the marginal algorithm cannot be implemented due to the intractability of the distribution π. For example, assuming that π and q have densities (also denoted π and q) with respect to some σ-finite measure, it may be that π cannot be evaluated point-wise, and although r(x, y) may be well defined theoretically, it cannot be evaluated either. However in some situations unbiased non-negative estimatesπ(x) = W x π(x) may be available; that is, W x ∼ Q x ( · ) ≥ 0 and E[W x ] = 1 for any x ∈ X (we will refer to W x as a "weight" throughout the paper). A naive idea may be to use such estimates in place of the true values in order to compute the acceptance probability. A remarkable property is that such an algorithm is in fact correct [4]. This can be seen by consider the following probability distribution (3)π(dx, dw) := π(dx)π x (dw) with π x (dw) := Q x (dw)w on the product space (X × W, B(X) × B(W)) where W is a Borel subset of R + and B(W) are the Borel sets on W.
This is the pseudo-marginal algorithm [4], which targets π marginally since it is a marginal distribution ofπ, and may be implemented in situations where the marginal algorithm may not. As a particular instance of the Metropolis-Hastings algorithm, the pseudo-marginal algorithm converges toπ under mild assumptions [e.g. 27], and although it may be seen as a "noisy" version of the marginal algorithm, it is exact since it allows us to target the distribution of interest π. The aim of this paper is to study some of the theoretical properties of such algorithms in terms of the properties of the weights and those of the marginal algorithm. More precisely we investigate the rate of convergence of the pseudo-marginal algorithm to equilibrium and characterise the approximation of the marginal algorithm by the pseudo-marginal algorithm in terms of the variability of their respective ergodic averages. The apparently abstract structure of the pseudo-marginal algorithm is in fact shared by several practical algorithms which have recently been proposed in order to sample from intractable distributions. The distribution of w is most often implicit, as we illustrate now with one of the simplest examples. Assume for simplicity that the space X is (a Borel subset of) R d and B(X) consists of the Borel subsets of X and that both π and q(x, ·) (for any x ∈ X) have densities with respect to the Lebesgue measure. Consider a situation where the target density is of the form π(x) = π(x, z)dz where the integral cannot be computed analytically. One can suggest approximating this density with an importance sampling estimate of the integral, where h x is a probability density for each x ∈ X. Note that it is in fact possible to consider unbiased estimators up to a normalising constant since such a constant cancels in the acceptance ratio of the pseudo-marginal algorithm, and without loss of generality we will assume this constant to be equal to one throughout. This setting was considered by Beaumont in the seminal paper [8] and various extensions proposed in [4]. There are more involved applications of this idea. In the context of state-space models, it has been shown in [1] that W x can be obtained with a particle filter-resulting in "particle MCMC" algorithms. In [9] it was shown how exact sampling methods can be used to carry out inference in discretely observed diffusion models for which the transition probability is intractable. See also the discussion [19] on the connection with pseudo-marginal MCMC and approximate Bayesian computation. We now summarise our main findings, which are of two different types, although some of their underpinnings and consequences are related.
Rates of convergence. In previous work [4] it has been shown that a pseudomarginal chain is uniformly ergodic whenever the marginal algorithm targeting π(x) is uniformly ergodic and the weights are bounded uniformly in x. It was also shown that geometric ergodicity is not possible as soon as the weights W x are unbounded on a set of positive π-probability. We extend the analysis of the convergence rates of pseudo-marginal algorithms in several directions.
In Section 3, we show that if the marginal chain admits a non-zero (right) spectral gap and the weights are bounded uniformly in x, then the pseudo-marginal chain has also a non-zero spectral gap. Our proof relies on an explicit lower bound on the spectral gap (Propositions 8 and 10). Our results imply that geometric ergodicity of a marginal algorithm is inherited by the pseudo-marginal chain as soon as the weights are uniformly bounded, either through a slight modification (Remark 15) or directly in many cases by observing that the pseudo-marginal Markov operator is positive (Proposition 16).
We also restate in a more explicit form a result of [4] which establishes the necessity of the existence of a functionw : X → [0, ∞) such that Q x [0,w(x)] = 1 for the geometric ergodicity of pseudo-marginal algorithms to hold. Assuming that Q x has positive mass in any neighbourhood ofw(x) we show through specific examples that sup x∈Xw (x) < ∞ may in some cases be a necessary condition for geometric ergodicity of a pseudo-marginal algorithm to hold (second part of Remark 34) while in other situations the existence of such a uniform upper bound is not a requirement (Remark 26 and the first part of Remark 34). Intuitively the latter will correspond to situations where the marginal algorithm possesses some robustness properties which allow it to counter, up to a limit, the perturbations brought in by the pseudo-marginal approximation.
In Section 5 we consider the particular case where the pseudo-marginal algorithm is an independent Metropolis-Hastings (IMH) algorithm. The primary interest of this example is pedagogical, since the corresponding pseudo-marginal implementation is also an IMH, which lends itself to a straightforward, yet very instructive, analysis. For example it allows us to establish that the existence of (not necessarily uniformly bounded) moments for the weights leads to polynomial convergence rates, while the existence of exponential moments leads to sub-exponential rates.
In the light of this pedagogical example, we pursue our analysis by considering more general scenarios where the supports of the weight distributions may be unbounded, that is, such that on some set of positive π-probability Q x [0,w] < 1 for anyw < ∞, implying that the corresponding pseudo-marginal algorithms cannot be geometric.
In Section 6, we only assume that the marginal algorithm is uniformly ergodic (together with a mild additional condition) and that the weight distributions are uniformly integrable. We establish the existence of a Lyapunov function satisfying a sub-geometric drift condition towards a small set (Proposition 30 and Lemma 32). In particular, if the weight distributions possess finite power moments, we establish polynomial ergodicity (Corollary 31).
In Section 7 we consider the popular random-walk Metropolis (RWM). Assuming standard tail conditions on π which ensure the geometric ergodicity of the RWM [15] and the existence of uniformly bounded moments we show that the corresponding pseudo-marginal algorithm is polynomially ergodic (Theorem 38). We extend this result to the situation where moments of the weights are assumed to exist but are not necessarily uniformly bounded in x (i.e. we allow them to grow in the tails of π) in Theorem 45. We note in Remark 34 that one of the intermediate results (Lemma 34) in fact implies the existence of a geometric drift when Q x [0,w(x)] = 1 for some appropriate functionw, possibly divergent in the tails of π, which is a consequence of the fast vanishing assumptions on the tails of π.
Asymptotic variance. It is natural to compare the asymptotic performance of ergodic averages obtained from a marginal algorithm and its pseudo-marginal counterpart. One can in fact ask a more general question of practical relevance. In practice, it is often possible to choose the weight distributions Q x from a family {Q N x } N ∈N indexed by an accuracy parameter N, as for example in (5). In such situations π N x (dw) = Q N x (dw)w converge weakly to δ 1 (dw) as N → ∞ and one may wonder if the asymptotic variance of the corresponding ergodic averages converge to that of the marginal algorithm.
In Section 2 we first show that the pseudo-marginal and marginal algorithms are ordered both in terms of the mean acceptance probability (Corollary 4) and the asymptotic variance (Theorem 7). The latter result relies on a generalisation of the argument due to Peskun [28,34], which may be of independent interest. This supports and generalises the empirical observation on examples that the pseudo-marginal algorithm cannot be more efficient than its marginal version.
When the weights are uniformly bounded in x, we start Section 4 with a simple upper bound on the asymptotic variance of the pseudo-marginal algorithm (Corollary 11) from which it is straightforward to deduce that it converges to that of the marginal when the weight upper bound goes to one. We generalise this result to the situation where the weights are unbounded, but π N x (dw) converges weakly to δ 1 (dw) as N → ∞ (Theorem 21). We also show how the sub-geometric ergodicity results proved earlier are essential to establish the conditions of this theorem in practice (Proposition 25).
We conclude in Section 8 where we briefly discuss additional implications of our results such as the existence of central limit theorems, the possibility to compute quantitative expressions for the asymptotic variance and the analysis of generalisations of pseudo-marginal algorithms.

Ordering of the marginal and pseudo-marginal algorithms
We first introduce some standard notation related to probability measures and Markov transition probabilities. For Π a Markov kernel and µ a probability measure defined on some measurable space (E, B(E)) and f a measurable real-valued function on E, we let for any and Π n f (x) := Π(x, dy)Π n−1 f (y) for n ≥ 1.
We will also denote the inner product between two real-valued functions f and g on E as f, g µ := f (x)g(x)µ(dx) and the associated norm f µ := f, f 1/2 µ . We start by a simple lemma, which plays a key role in the ordering of the marginal and the pseudo-marginal algorithms.

Lemma 1.
For any x, y ∈ X, we have Proof. Notice that t → min{1, t} is a concave function. Therefore, one can apply Jensen's inequality, with the probability measure Q x (dw)wQ y (du), to get the desired inequality.
In order to facilitate the comparison of P andP we follow [4] and introduce an auxiliary transition probabilityP which is defined on the same space as the pseudo-marginal kernelP and is reversible with respect toπ, (6)P (x, w; dy, du := q(x, dy)π y (du) min{1, r(x, y)} + δ x,w (dy, du)ρ(x).
Application of Lemma 1 leads to the generic result below, which in turn implies an order between the expected acceptance rates (Corollary 4) and the asymptotic variances (Theorem 7) of the marginal and pseudo-marginal algorithms.
Then we have ∆P (g) ≥ ∆P (g) and whenever these quantities are finite, Proof. Denote a(x, y, u, w) := min{1, r(x, y)}−min 1, r(x, y) u w . Since π y (du) = 1 = Q y (du), we may write for a bounded function g where the inequality is a consequence of Lemma 1. The general case follows by a truncation argument.
Corollary 4. Let us denote the expected acceptance rates of the marginal and the pseudo-marginal algorithms as respectively. Then we have Proof. Observe first that αP := π(dx, dw) q(x, dy)Q y (du) min{1, r(x, y)} = α P .
Applying then Proposition 2 with g ≡ 1 implies The last inequality follows because ρ(x) ∈ [0, 1] for all x ∈ X.
We now define the notion of asymptotic variance for scaled ergodic averages of a Markov chain.
Definition 6. Let Π be a reversible Markov kernel with invariant distribution µ defined on some measurable space (E, B(E)), and denote by (X k ) k≥0 the corresponding Markov chain at stationarity, that is such that X 0 ∼ µ. Suppose The asymptotic variance of f under Π is defined as (7) var(f, Π) := lim Whenever the integrated autocorrelation time exists and is finite, then var(f, Lemma 52 in Appendix A shows that the limit in (7) always exists (but may be infinite) and proves the relation between τ (f, Π) and var(f, Π). We now show that a pseudo-marginal algorithm is always dominated by its associated marginal algorithm in terms of asymptotic variance. The result can be regarded as an extension of Peskun's approach [28,34]. We point out in the proof what makes the result not straightforward.
where ∆P (g λ ) and ∆P (g λ ) are defined in Proposition 2 and g λ (x, y) : for λ ∈ [0, 1). Proof. Our proof is inspired by the proof of Tierney [34, Theorem 4] but we cannot use his argument directly because Proposition 2 does not apply to functions depending also on u and w. Observe first from the definition ofP that a Markov chain (X n ,W n ) n≥0 with the kernelP and with (X 0 ,W 0 ) ∼π coincides marginally with the marginal chain, that is, (X n ) n≥0 following P with X 0 ∼ π and (X n ) n≥0 have the same distribution. Therefore, var(f,P ) = var(f, P ). We denotē 0 (X, π) := {f : X → R : π(f ) = 0, π(f 2 ) < ∞}, and with a slight abuse of notation definef (x, w) :=f (x) for all (x, w) ∈ X × W. Notice thatf ∈ L 2 0 (X × W,π). For λ ∈ [0, 1), we define the auxiliary quantities for any Markov kernel H reversible with respect toπ, where I stands for the identity operator. We note that from Lemma 51 in Appendix A the quantity var λ (f , H) is well-defined and that from Lemma 52, it is sufficient to show that var λ (f ,P ) ≤ var λ (f ,P ) holds for all λ ∈ [0, 1) in order to establish (i).
Using the notation of Lemma 51 with P 1 =P and P 2 =P , we can write Note that ifP andP would satisfy Peskun's order, then the second line is sufficient to conclude [34]. We show now that both terms on the right hand side of the last line are non-negative.
The specific lower bound (ii) follows from (8) because the first term is always non-negative.
3. Inheritance of the spectral gaps when the weights are uniformly bounded We consider now an order between the spectral gaps of the pseudo-marginal kernelP and the auxiliary kernelP defined in (6). Then, particularly, we find that if w is always bounded from above byw ∈ [1, ∞), that is, W = (0,w], and P has a non-zero (right) spectral gap (i.e. P is variance bounding; see [30,Theorem 14]), thenP has a non-zero spectral gap as well. We will also examine the asymptotic variance constants using the spectral gap bound, and conclude the section by a discussion on how our results on the spectral gap can imply geometric ergodicity ofP .
Suppose f : X × W → R is integrable with respect toπ. We denote in this section the function centred with respect to w as The Dirichlet form related to a Markov kernel Π with invariant distribution µ and a function g is given as where I is the identity operator. The spectral gap is defined through where var µ (g) is given in Definition 6.
Proposition 8. The spectral gap ofP defined in (6) satisfies where the essential supremum is with respect to π.
Remark 9. In the case where π is not concentrated on points, that is, π({x}) = 0 for all x ∈ X, the statement of Proposition 8 simplifies to Gap(P ) = Gap(P ), because then 1 − ess sup x∈X ρ(x) ≥ Gap(P ) by Lemma 54 (ii) in Appendix B.
Remark 12. From the proof of Proposition 10, one observes that in fact whereP is the Markov kernel with the proposal q(x, dy)Q y (du) and the acceptance probability min{1, r(x, y)} min{1, u/w} reversible with respect toπ. This implies, repeating the arguments in the proof of Corollary 11, that var(f,P ) ≤ var(f,P ) for allπ(f 2 ) < ∞.
We also note that in our follow-up work [5], we upper bound the spectral gap of the pseudo-marginal algorithm by that of the marginal, Gap(P ) ≤ Gap(P ).
Next we show that the boundedness of the support of the weight distributions Q x for essentially all x ∈ X is a necessary condition for the spectral gap of the pseudo-marginal algorithm. The result is similar to Theorem 8 in [4], but its proof is different and the statement more explicit.

Proposition 13. If the pseudo-marginal kernelP has a non-zero spectral gap, then there exists a functionw
Proof. We prove the claim by contradiction. Assume that there exists a set Becausew ǫ increases to infinity as ǫ → 0, we haveπ(Ã ǫ ) ∈ (0, 1/2) for small enough ǫ > 0. For such ǫ > 0, we may apply Lemma 54 (i) in Appendix B with the setÃ ǫ , to conclude that Gap(P ) Remark 14. Proposition 13 implies the necessity of the existence ofw : X → [1, ∞) for spectral gap and consequently geometric ergodicity to hold, but does not require the existence of a uniform upper boundw as in Proposition 10. Uniformity is indeed not necessary as illustrated in Remarks 26 and 34 with the independent MH and random walk MH algorithms respectively; see also [20,Remark 1]. However, the second part of Remark 34 implies that in some cases the existence of a uniform upper boundw is indeed necessary.
The above results are statements on the (right) spectral gap ofP only, which is equivalent to variance bounding property ofP [31]. In some applications, geometric ergodicity may be more desirable than variance boundedness. We first note that in general, geometricity can be enforced by a slight algorithmic modification.
In many cases, however, such a modification is unnecessary, because the pseudomarginal algorithm can be shown to exhibit also a non-zero left spectral gap, defined using the notation in (10) Non-zero left and right spectral gaps, or in other words the existence of an absolute spectral gap, is equivalent to geometric ergodicity of a reversible chain [e.g. 30, Of particular interest are positive Markov operators Π which satisfy g, Πg µ ≥ 0 for all functions g with g µ < ∞. For positive Π, clearly Gap L (Π) ≥ 1 and establishing geometric ergodicity only requires focusing on the right spectral gap. We record the following easy proposition summarising two situations where the pseudo-marginal algorithm inherits the positivity of the marginal algorithm.  (14) q(x, y) = η(z, x)η(z, y)dz.

(b) If the marginal algorithm is a random-walk Metropolis (RWM) with a proposal distribution which can be written in the form
Proof. Case (a) holds because the pseudo-marginal version of an IMH is also an IMH (see also Section 5), which is positive [e.g. 13]. Case (b) follows by using an argument of [7, Lemma 3.1], by writing for f : Remark 17. Condition (14) holds in particular with q(x, y) =q(y − x) whereq is 'divisible,' that is, it is the density of the sum of two independent random variables sharing the same symmetric density q 0 . Indeed, in such a scenarioq( . This covers the case whereq is a (possibly multivariate) Gaussian or student.
We conjecture that geometric ergodicity is inherited in general as soon as the weights are uniformly bounded. More precisely, we believe that if the marginal algorithm is geometrically ergodic (admits a non-zero absolute spectral gap) and the weights are uniformly bounded, then the pseudo-marginal algorithm is also geometrically ergodic. We have not been able to prove this in general, but we have not found counter-examples either.
For completeness, we however provide the following counter-example which shows that the left spectral gap of the marginal algorithm may not be inherited by the pseudo-marginal algorithm without the uniform upper bound assumption on the weights.
Let us then considerP with the weight distributions where ǫ k := 10 −k and a(k, n) := 2 −10 k +n , and the constants b(k, n) ∈ (1, ∞) are chosen so that Q x (w) have expectation one. Define the functions , if x = 10 k + n with n ∈ [1, 10 k ] odd and w = a(k, n) −1, if x = 10 k + n with n ∈ [1, 10 k ] even and w = a(k, n) 0, otherwise.
A straightforward calculation shows that lim k→∞ f k ,P f k π / f k 2 π = −1, which shows that there is no left spectral gap. See Appendix E for details.

Convergence of the asymptotic variance
In standard applications of the pseudo-marginal algorithm, one typically selects Q x from a family of possible proposal distributions Q N x indexed by some precision parameter N which reflects the concentration of W on 1. In most relevant scenarios we are aware of, N ∈ N corresponds to the number of samples, particles or iterates of an algorithm used to compute an unbiased estimator of the density value, as exemplified in (5). It should be clear that this is not a restriction. Hereafter, we denote the pseudo-marginal kernels and the invariant measures associated with Q N x asP N andπ N , respectively. It is easy to see that if for all x ∈ X, Q N x (dw)w → δ 1 (dw) as N → ∞ weakly, thenπ N (dx, dw) → π(dx)δ 1 (dw) weakly, suggesting that a pseudo-marginal algorithm with invariant distributionπ N may become similar to the marginal algorithm with invariant distribution π as N → ∞. As pointed out earlier, whenever W x is not bounded uniformly, a pseudo-marginal algorithm cannot be geometric, although its marginal algorithm may be. In fact it was shown in [4, Remark 1] that even in situations where the weights are uniformly bounded and the pseudomarginal algorithm is uniformly ergodic, increasing N may not improve the rate of convergence of the algorithm, that is, there is not convergence in terms of rate of convergence.
In this section we however show that in many situations such a convergence takes place in terms of the asymptotic variance, or equivalently, the integrated autocorrelation time; see Definition 6. More precisely, we show here that under simple conditions var(g,P N ) → var(g, P ) as N → ∞. We start with a very simple result, which is a direct consequence of Corollary 11.
Proposition 19. Suppose that the marginal kernel P has a non-zero spectral gap and the weight distributions are bounded uniformly in for all x ∈ X and N ≥ N 0 for some N 0 ∈ N, and lim N →∞w N = 1. Then, lim N →∞ var(g,P N ) = var(g, P ) for any g : X → R with π(g 2 ) < ∞.
Proof. The result is direct consequence of Corollary 11.
We now extend this result to situations where the distributions {Q N x } N ∈N may have an unbounded support, and therefore {P N } N ∈N may not be geometrically ergodic. We formulate our result in terms of the following technical condition assuming uniform convergence of the integrated autocorrelation series. We will return to this assumption towards the end of this section and show that it can be checked in practice with for example Lyapunov type drift conditions (see Proposition 25).
Condition 20. For g : X → R, suppose that the integrated autocorrelation time τ (g, P ) (Definition 6) is well-defined and finite. Denote by (X N k ) k≥0 the Markov chain with initial distributionπ N and kernelP N . Assume that there exists a constant N 0 < ∞ such that

The main result of this section is
Theorem 21. Assume that g : X → R satisfies π(|g| 2+δ ) < ∞ and Condition 20 holds for g. Suppose also that, Then, lim N →∞ var(g,P N ) = var(g, P ).
Proof. If var π (g) = 0, the claim is trivial. If var π (g) > 0, our conditions imply that the autocorrelation times exist and are finite for both the marginal kernel P and the pseudo-marginal kernelsP N for N ≥ N 0 ; this follows from the finiteness of the terms in the autocorrelation series ensured by the Cauchy-Schwartz inequality, and Condition 20. Therefore, without loss of generality, we prove the claim for autocorrelation times τ (g,P N ) → τ (g, P ) for a function g withπ N (g) = π(g) = 0 andπ N (g 2 ) = π(g 2 ) = 1. Consider the Markov kernelsP N defined as in (6) Notice thatP N and π N coincide marginally with P and π, respectively, that is (X N k ) k≥0 has the same distribution as that of the stationary marginal chain (X k ) k≥0 with kernel P and such that X 0 ∼ π.
Choose ǫ ∈ (0, 1) and let n 0 = n 0 (ǫ) < ∞ be such that for all N ≥ N 0 where the existence of n 0 follows from Condition 20. We have for N ≥ N 0 In order to control the last term, we consider a coupling argument. Denote q := (2 + δ)/δ ∈ (1, ∞). Lemma 22 applied withǫ = ǫn −q−1 0 /2 implies the existence of N 1 < ∞ and a setC ∈ B(X) × B(W) such that for all N ≥ N 1 , Lemma 55 in Appendix C applied to (X N k ,W N k ) 0≤k≤n 0 −1 and (X N k ,W N k ) 0≤k≤n 0 −1 with the setC shows that the laws of these processes,μ andμ respectively, satisfy the following total variation inequality for all N ≥ N 1 ,
Let µ 1 and µ 2 be two probability distributions on the space (E, B(E)). We define the total variation distance Proof. Chooseǫ > 0 and letw := 1 +ǫ/8. It is not difficult to see that assumption (15) implies for all x ∈ X, Because Q N y (du)|1 − u| ≤ 2, the dominated convergence theorem together with (15) implies for all x ∈ X, By Egorov's theorem, there exists a set C ∈ B(X) such that π(C ∁ ) ≤ǫ/2 and the convergence in both (17) and (18) is uniform in x.
For any x ∈ X, any w > 0 and any set A ∈ B(X) × B(W), where the third inequality follows because Therefore, lettingČ := C × [w −1 ,w], we can bound the total variation by With additional assumptions in Condition 20 and (15) on the rates of convergence, one could obtain a rate of convergence in Theorem 21, that is find and for any v ∈ [1, ∞), there exists probability measures {ν N } N ≥N 0 and a constant ǫ v ∈ (0, 1], such that for all N ≥ N 0 , Proposition 25. Assume Condition 24 holds for the pseudo-marginal kernelsP N , and that for some λ ∈ [0, 1) and κ ∈ [0, 1), where α κ,λ := κα(1 − λ), then Condition 20 holds.
Proof. From the assumptions, there exists a finite constant R such that for all N ≥ N 0 and any (x, w), where r(k) := (k + 1) Corollary 8]; see also [2,Proposition 3.4]. Note that we may write

Sub-geometric ergodicity with an IMH as marginal algorithm
The independent Metropolis-Hastings (IMH) algorithm is a specific case of the Metropolis-Hastings in (1) corresponding to a proposal q(x, dy) = q(dy) for all x ∈ X, such that π ≪ q. It is straightforward to check that a pseudo-marginal implementation of this algorithm is also an IMH. This fact allows for the easy exploration of conditions which ensure uniform and sub-geometric ergodicity of the pseudo-marginal IMH, and are illustrative of the general ideas we develop later in the paper. We note that these results may be relevant for example to the analysis of the Particle IMH-EM algorithm presented in [6].
We then give two conditions which ensure sub-geometric ergodicity of the pseudo-marginal IMH. Our results rely on Lemma 56 in Appendix C, which is inspired by [16] which established polynomial ergodicity and [12] which explored more general sub-geometric rates for the IMH.
The type of drift in Corollary 27 (a) implies faster than polynomial sub-geometric rates of convergence [cf. 11], whereas Corollary 27 (b) implies polynomial rates of convergence [cf. 16]. We notice that the result suggests that the pseudo-marginal algorithm may have a similar rate of convergence as that of the marginal algorithm.
6. Sub-geometric ergodicity with uniformly ergodic marginal algorithm We consider next the situation where the marginal algorithm is uniformly ergodic. This often corresponds to scenarios where the state space X ⊂ R d is compact. It turns out that when the weight distributions {Q x } x∈X do not have bounded supports but are uniformly integrable, then the corresponding pseudo-marginal algorithm satisfies a sub-geometric drift condition towards a set C := X × (0,w] for somew ∈ (1, ∞). Provided the marginal algorithm satisfies a practically mild additional condition in (19), the set C is guaranteed to be small for the pseudo-marginal chain.
We start by assuming uniform integrability in a form given by the de la Vallée-Poussin theorem [e.g. 24, p.19 T22]. This allows us to quantify the strength of the sub-geometric drift in a convenient way, for example indicating that moment conditions imply polynomial drifts and consequently polynomial ergodicity.

Condition 28. There exists a non-decreasing convex function
We record a simple implication of Condition 28. Proof. For any function f : The function f (w) := φ(w)/w is non-decreasing for w sufficiently large, therefore sup y∈X u≥w The next result establishes a drift away from large values of w for the pseudomarginal chain, given that the marginal algorithm has an acceptance probability uniformly bounded away from zero. All uniformly (and geometrically) ergodic Markov chains satisfy this property [32, Proposition 5.1].
Proposition 30. Suppose that the one-step expected acceptance probability of the marginal algorithm is bounded away from zero, α 0 := inf x∈X q(x, dy) min{1, r(x, y)} > 0, and Condition 28 holds.
In practice, Condition 28 is often verified for moments, that is, φ(w) = w β . We record the following corollary to highlight the straightforward connection of β to the polynomial drift rate.
Remark 33. The condition in (19) is more stringent than assuming P uniformly ergodic. However, it is the most common way to establish the n-step minorisation condition P n (x, · ) ≥ ǫν( · ) in practice, which holds if and only if P is uniformly ergodic. In the case of a continuous state-space X where q(x, {y}) = 0 and ν({y}) = 0 for all x, y ∈ X and n = 1, the condition in (19) is in fact equivalent to P (x, · ) ≥ ǫν( · ).

Polynomial ergodicity with a RWM as marginal algorithm
We consider next conditions which allow us to establish a polynomial drift condition for the pseudo-marginal algorithm in the case where the marginal algorithm is a geometrically ergodic random-walk Metropolis (RWM) targeting a super-exponentially decaying target with regular contours [15]. The existence of such a drift, together with additional simple assumptions, imply polynomial rates of ergodicity, but also Condition 20 (essential for the convergence of the pseudomarginal asymptotic variance to that of the marginal algorithm) and a central limit theorem for example.
Our results rely on moment conditions on the distributions Q x (dw). In Section 7.1 we assume the moments to be (essentially) uniform in x, while in Section 7.2 we consider the case where the behaviour of Q x (dw) can get worse as |x| → ∞. Note that the conditions in Section 7.2 may appear more general, but that they do not include all the cases covered by those of Section 7.1. This can be seen, for example, by comparing Conditions 37 and 46 and the admissible values of η in Theorem 38 and Corollary 47.
It is possible to extend our results beyond the polynomial case. For example one may assume the existence of exponential moment conditions; see Remark 39. For the sake of clarity and brevity, we have opted to detail here the polynomial case only.
Remark 34. While our main focus here is on unbounded weight distributions, we will see that Lemma 49 suggests that geometric ergodicity is still possible when Q x (0,w(x)] = 1 for all x ∈ R d , wherew : R d → [1, ∞) tends to infinity as |x| → ∞. This is, however, a consequence of the strong assumption properties on the tails of π which confer the algorithm with a robustness property with respect to perturbations. Indeed, consider now the RWM on a compact subset X ⊂ R d with π bounded away from zero and infinity on X. It is not difficult to establish that if there does not existw < ∞ such that Q x [0,w] = 1 for π-almost every x ∈ X, then the chain cannot be geometrically ergodic (see, for example, the proof of Proposition 13).
Throughout this section, we denote the regions of almost sure acceptance and possible rejection for the marginal and pseudo-marginal and algorithms as respectively, for all x ∈ X and w ∈ W.
7.1. Uniform moment bounds. Consider the following moment condition on the distributions {Q x } x∈X where X = R d .
Condition 35. Suppose there exist constants α ′ > 0 and β ′ > 1 such that where a ∨ b := max{a, b} and the essential supremum is taken with respect to the Lebesgue measure.
We first establish the following simple lemma, used throughout this section, which guarantees that the moment condition above holds also for any intermediate exponents.
The following condition for the target density π was introduced in [15].
Condition 37. The target distribution π has a density with respect to the Lebesgue measure (also denoted π) which is continuously differentiable and supported on R d . The tails of π are super-exponentially decaying and have regular contours, that is, respectively, where |x| denotes the Euclidean norm of x ∈ R d . Moreover, the proposal distribution satisfies q(x, A) = q(A−x) = A q(y−x)dy with a symmetric density q bounded away from zero in some neighbourhood of the origin.
The following theorem establishes a polynomial drift given the conditions above.

Theorem 38. SupposeP is a pseudo-marginal kernel with distributions Q x (dw)
satisfying Condition 35 with some constants α ′ > 0 and β ′ > 1, and that the corresponding marginal algorithm is a random walk Metropolis with invariant density π and proposal density q satisfying Condition 37.
We conjecture that the negative moment condition and the presence of w −α in the drift function are not necessary in order to establish polynomial ergodicity in general. It seems, however, difficult to establish a one-step drift condition without any control of the behaviour of the distributions Q x near zero.
We first consider a simple result which is auxiliary to the other lemmas.
Proof. The bound (i) follows by writing and using the estimate Á {u ≥ w} ≤ (u/w)β −1 . For (ii), similarly We next consider the case where w is large, and establish a polynomial drift in this case.
Proof. We may write for w ≥w ≥ 1 where We now estimate both integrals by partitioning their integration domains into their intersections with the acceptance and the rejection sets of the marginal algorithm. For notational simplicity we denote The bound for the first integral is straightforward, For the second one, observe that 1 ≤ π(x+z) We now turn to the the crucial remainder, which approaches unity as w grows.

(34)
Proof. From the proof of Lemma 42, we havẽ Consider then (34). Let δ > 0 be small enough so that inf x∈X q( for w ∈ (0, w] if w is small enough. We may further decrease w to ensure that a x,w +b x,w ≤ ǫ/4 for all w ∈ (0,w] and conclude (34) with λ = 1 − ǫ/4.

7.2.
Non-uniform moment bounds. We replace the uniform moments in Condition 35 here with the following assumption, which allows the moments of the distributions {Q x } x∈X to grow in the tails of π.
(iii) For any constant b > 1, one must have where M W : (0, ∞) → (0, ∞) is defined as follows where the essential supremum is taken with respect to the Lebesgue measure.
The assumptions in Condition 44 may appear rather implicit and technical at first. However they, together with additional assumptions required in Theorem 45 below, are implied by the more meaningful assumptions in Condition 46 and Corollary 47, whose proof may help the reader gain some intuition.
Proof. The proof follows by applying Lemma 48 below and then Lemma 49 with c w from Lemma 48, similarly to the proof of Theorem 38 by settingw := sup |x|≤Mw (x), and observing that V is bounded on C. The dependence on the various quantities is clear from the proofs of Lemmas 48 and 49.
Before proving Lemmas 48 and 49, we give sufficient conditions to establish the conditions of Theorem 45.
Proof. Choose the constants ξ w and ξ π sufficiently small so that the conditions on η, α and β in Theorem 45 are satisfied. Fix a unit vector u ∈ R d and define the functionψ : where R 0 ∈ [1, ∞); this is always possible because the function r → π(ru) is bounded away from zero on compact sets and monotone decreasing on the tail.
Define then g(x) = c gψ ρ ′ (π(x)), where the value of the constant c g ≥ 1 will be fixed later. In order to guarantee that Condition 44 (i) is satisfied for sufficiently large c g , it is sufficient to show that Due to Lemma 57 in Appendix D, if |x| is sufficiently large, then g(x) = g(ζ x |x|u) It is easy to check similarly to (40) that It is also easy to check that is uniformly bounded in x ∈ X. This is because it is sufficient to check the condition in the tails along a ray, that is, only for z = r|x|, r ≥ 1. We conclude about the existence of a constant c g ∈ [1, ∞) such that Condition 44 holds. Choose ǫ c ∈ (0, ρ − 1 − ρ ′ ) and let c(x) = exp(|x| ǫc ). It is easy to check that there exists ξ c such that (37) and (38) hold, using Lemma 59 in Appendix D to estimate q(D x ).
We start by establishing a polynomial drift when w is large.
Proof. We may writẽ where a x,w and b x,w are defined in (24) and (25), respectively.
The terms of the order w −(1+δ) or w −(1+δ ′ ) vanish faster than w −1 as w increases. Consequently, we can choose c w ∈ [1, ∞) sufficiently large so that there exists a ν ′ > 0 such that for all x ∈ X and w ≥w(x), where κ = β−1 β ∈ (0, 1). Our last lemma concentrates on the cases where either |x| is large and w bounded, or w is small.
Proof. We may writẽ whereâ x,w andb x,w are given as in (26) and (27).
< c(x)}. Lemma 57 in Appendix D implies the existence of b 1 ∈ [1, ∞) and M 0 ∈ [1, ∞) such thatĀ x ∪ D x + x ⊂ B 0, b 1 (|x| ∨ 1) for all x ∈ X. We decompose the two sums above into sub-sums onĀ x andR x , with again an obvious abuse of notation.
If the spectral gap of the marginal algorithm is not directly accessible, it can be bounded by the drift constants; see [7] and references therein, and also [18,Theorem 4.2 (ii)]. WhenP is polynomially ergodic, the class of functions g for which the CLT (46) holds is related to the exponent in the polynomial drift. For the convenience of the reader, we reformulate here a result due to Jarner and Roberts [16].
Theorem 50 is a restatement of [16,Theorem 4.2], because the pseudo-marginal kernelP is also irreducible and aperiodic if the marginal kernel P is. The asymptotic variance can also be upper bounded in the polynomial case; see [3] and [18,Theorem 5.2 (ii) and Remark 5.3]. It is also possible to deduce non-asymptotic mean square error bounds [18].
Finally some of our results apply directly to extensions of pseudo-marginal algorithms which directly make use of noisy estimates of the marginal's acceptance ratio [17,26]. However despite some similitudes and simplifications, the corresponding processes differ fundamentally in that (X k ) k≥0 is a Markov chain in this case (as opposed to the pseudo-marginal scenario) and we are currently investigating these differences. In this section, (X, B(X)) is a generic measurable space and µ is a probability measure on X. We consider the Hilbert space with the inner product f, g µ := X f (x)g(x)µ(dx). We denote the corresponding norm by f µ := f, f 1/2 µ and the operator norm for A : L 2 0 (X, µ) → L 2 0 (X, µ) as A := sup{ Af µ : f µ = 1}. Lemma 51. Let P 1 and P 2 be two Markov kernels on space X reversible with respect to µ, and define the family of interpolated kernels H β := P 1 + β(P 2 − P 1 ) for β ∈ [0, 1] also reversible with respect to µ. Then, is a well-defined operator on L 2 0 (X, µ) for all λ ∈ [0, 1) and β ∈ [0, 1] as well as the right-hand derivatives, with limits taken with respect to the operator norm, for all λ ∈ [0, 1) and β ∈ [0, 1).
Lemma 52. Suppose Π is a Markov kernel reversible with respect to µ, and (X n ) n≥0 is a Markov chain corresponding to the transition Π with X 0 ∼ µ. Then, for a function f ∈ L 2 0 (X, µ) var(f, Π) = lim where e f,Π is a positive measure on S ⊂ [−1, 1] satisfying e f,Π (S) = f 2 µ . For any f ∈ L 2 0 (X, µ), whenever the series below is convergent, then the following equality holds, is well-defined for all λ ∈ [0, 1), and satisfies lim λ→1− var λ (f, Π) = var(f, Π) and Proof. The reversibility of Π ensures that Π is a self-adjoint operator on L 2 0 (X, µ) with a spectral radius bounded by one. Therefore, by the spectral decomposition theorem, there exists a positive measure e f,Π on the Borel subsets of the spectrum S ⊂ [−1, 1] and such that f, Π k f = S x k e f,Π (dx) for all k ≥ 0 [e.g. 29, VII.2ff.]. Now, we may write x k for all |x| < 1, it is straightforward to verify by Kronecker's lemma that (49) holds. Similarly, whenever the sum in (50) is convergent, it is easy to see that the term (51) converges to (50).
The expression for A λ (1) in Lemma 51 allows us to write We conclude that lim λ→1− var λ (f, Π) = var(f, Π) by the monotone convergence theorem. For the last claim, we use the Neumann series definition of (I − λΠ) −1 , Appendix B. Lemmas for Section 3 We include the statement of [10,Theorem A.2] for the sake of self-containedness.
Lemma 53. Let A and B be self-adjoint operators on a Hilbert space H satisfying 0 ≤ f, Af ≤ f, Bf for all f ∈ H, and the inverses A −1 and B −1 exist. Then, Lemma 54. Suppose P is a Metropolis-Hastings kernel given in (1) and ρ(x) is given in (2). Then, the spectral gap of P defined in (10) satisfies (i) for any set A ∈ B(X) with π(A) ∈ (0, 1), (ii) if π does not have point masses, that is, π({x}) = 0 for all x ∈ X, then Proof. We first check (i). Denote p = P(A) ∈ (0, 1) and define f (x) = aÁ {x ∈ A}− bÁ {x / ∈ A} where the constants a, b ∈ (0, ∞) are chosen so that π(f ) = ap − b(1 − p) = 0 and π(f 2 ) = a 2 p + b 2 (1 − p) = 1. We may compute Now, according to our choice of a and b, Consider then (ii). The case Gap(P ) = 0 is trivial, so assume Gap(P ) > 0 and assume the claim does not hold. Then, there exists an ǫ > 0 and a set A ∈ B(X) with p := P(A) ∈ (0, 1) such that 1 − ρ(x) ≤ Gap(P ) − ǫ for all x ∈ A. From (i), Gap(P ) ≤ (1 − p) −1 (Gap(P ) − ǫ). Because π is not concentrated on points, we may choose p as small as we want, which leads to a contradiction.
The claim (ii) follows on compact sets by the continuity of log π, and in the tails as in [15,proof of Theorem 4.3]; the last claim (iii) follows similarly.
When the target and the proposal distributions satisfy also Condition 46, we have a decay rate for q(D x ). n(x + z) · ∇ log π(x + z) ≤ −c ℓ |x + z| ρ−1 for all |x| ≥ M ℓ , z ∈ D x .
Appendix E. Details on the counter-example in Section 2 First, easy calculation shows the Foster-Lyapunov drift for x > 0, This geometric drift to the atom {0} shows that this marginal algorithm is geometrically ergodic. We then turn into upper-bounding f k ,P f k π . We first show that P f k (x, w) ≤ −1 + 2ǫ k , for x = 10 k + n with n ∈ [2, 10 k − 1] odd and w = a(k, n) P f k (x, w) ≥ +1 − 2ǫ k , for x = 10 k + n with n ∈ [2, 10 k − 1] even and w = a(k, n).