Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance

This is a self-archived version of an original article. This version may differ from the original in pagination and typographic details. Author(s): Title: Year: Version: Copyright: Rights: Rights url: Please cite the original version: CC BY-NC-ND 4.0 https://creativecommons.org/licenses/by-nc-nd/4.0/ Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance © 2020 Elsevier BV Accepted version (Final draft) Franks, Jordan; Vihola, Matti Franks, J., & Vihola, M. (2020). Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance. Stochastic Processes and Their Applications, 130(10), 6157-6183. https://doi.org/10.1016/j.spa.2020.05.006 2020 IMPORTANCE SAMPLING CORRECTION VERSUS STANDARD AVERAGES OF REVERSIBLE MCMCS IN TERMS OF THE ASYMPTOTIC VARIANCE JORDAN FRANKS AND MATTI VIHOLA Abstract. We establish an ordering criterion for the asymptotic variances of two consistent Markov chain Monte Carlo (MCMC) estimators: an importance sampling (IS) estimator, based on an approximate reversible chain and subsequent IS weighting, and a standard MCMC estimator, based on an exact reversible chain. Essentially, we relax the criterion of the Peskun type covariance ordering by considering two different invariant probabilities, and obtain, in place of a strict ordering of asymptotic variances, a bound of the asymptotic variance of IS by that of the direct MCMC. Simple examples show that IS can have arbitrarily better or worse asymptotic variance than Metropolis-Hastings and delayed-acceptance (DA) MCMC. Our ordering implies that IS is guaranteed to be competitive up to a factor depending on the supremum of the (marginal) IS weight. We elaborate upon the criterion in case of unbiased estimators as part of an auxiliary variable framework. We show how the criterion implies asymptotic variance guarantees for IS in terms of pseudo-marginal (PM) and DA corrections, essentially if the ratio of exact and approximate likelihoods is bounded. We also show that convergence of the IS chain can be less affected by unbounded high-variance unbiased estimators than PM and DA chains. 1. Introduction Let ν(θ, z)dθdzbe a probability measure on a jointly measurable space T× Zwith σ-finite dominating measure dθdz, and suppose one desires to calculate expectations with respect to νor its marginal ν∗(θ):=Rν(θ, z)dz. In many scenarios of interest, ν∗(θ) is intractable to evaluate and Zis high-dimensional. Even if the full joint density ν(θ, z) is tractable up to a normalising constant, high-dimensional Markov chain Monte Carlo (MCMC) based on targeting νwith Metropolis-Hastings (MH) is often inefficient or even useless due to difficulty with the design of proposal distribution [35]. To deal with these issues, often one can transform the high-dimensional MCMC into a pseudo-marginal (PM) [6] or approximate marginal MCMC [51]. Then the proposal distribution can live on the low-dimensional space T, and the resulting chains are often much more efficient. The PM approach is asymptotically exact, while the approximate marginal approach requires an importance sampling (IS) correction to make it so. We next describe these approaches, and give our main result comparing the relative efficiency of these approaches in terms of the asymptotic variance. Key words and phrases. Asymptotic variance, delayed acceptance, importance sampling, Markov chain Monte Carlo, pseudo-marginal algorithm, unbiased estimator. 1 arXiv:1706.09873v6 [stat.CO] 24 Mar 2020 2 JORDAN FRANKS AND MATTI VIHOLA Algorithm 1 Pseudo-marginal algorithm, for iteration k≥1. (PM 1) Propose a transition Θ0∼qΘk−1(·). (PM 2) Given Θ0, generate (ζ0(1:m), Z0(1:m)), and with probability min 1,qΘ0(Θk−1)Pm i=1 ζ0(i) qΘk−1(Θ0)Pm i=1 ζ(i) k−1 set (Θk, ζ(i) k, Z(i) k)←(Θ0, ζ0(i), Z0(i)). Otherwise, set (Θk, ζ(i) k, Z(i) k)) ← (Θk−1, ζ(i) k−1, Z(i) k−1). 1.1. Pseudo-marginal Markov chain Monte Carlo. The PM approach is based on replacing ν∗(θ) with a non-negative unbiased estimator ˆν∗(θ) of ν∗(θ) (up to constant) within the standard (but assumed unavailable) MH algorithm targeting ν∗[6, 32]. That is, we assume there is a constant cν>0 such that E[ˆν∗(θ)] = cνν∗(θ) (1) for all θ. A standard example of such an estimator is ˆν∗(θ) = 1 m m X i=1 ν(θ, Zi) Qθ(Zi), where Ziare sampled i.i.d. from some instrumental distribution Qθ(·) satisfying Qθ(z) = 0 =⇒ν(θ, z) = 0. An unbiased estimator satisfying (1) will allow for calculation of marginal expectations with respect to ν∗using the approaches we consider, but often one can do much better, allowing also for joint expectations with respect to ν[2, 51]. That is, suppose one has access to non-negative unbiased estimators for a subclass L1(ν) of functions which we now describe. With θ∈T,ζ(i)∈[0,∞) and z(i)∈Zfor i= 1, . . . , m, set ζ(g):=1 m m X i=1 ζ(i)g(θ, z(i)) for g∈L1(ν). Let Qbe a probability kernel from Tto V:= [0,∞)m×Zm. Let L1(ν) consist of those functions f∈L1(ν) such that for g∈ {f, |f|}, ZQθ(dv)ζ(g) = cνν∗(θ)Zg(θ, z)ν(dz|θ) (2) for all θ∈Tand v:= (ζ(1:m), z(1:m))∈V, where cν>0 is some fixed constant not depending on (θ, v), and ν(dz|θ) denotes a regular conditional probability of νgiven θ. Note that if 1 ∈ L1(ν), then (1) is satisfied with ˆν∗(θ):=1 mPm i=1 ζ(i), and L1(ν∗) is naturally included into L1(ν) via f(θ, z):=f(θ) for f∈L1(ν∗). In the following, we will always assume that 1 ∈ L1(ν), since the schemes we consider require this for consistency. Let qbe a transition density on T, where qθ(θ0) denotes the probability to move from θto θ0. With (Θ0, ζ(1:m) 0, Z(1:m) 0)∈T×[0,∞)m×Zminitial values with Pm i=1 ζ(i) 0>0, for k= 1, . . . , n, the PM iteration is given in Algorithm 1 [see 6]. IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 3 Algorithm 2 Delayed-acceptance (DA0), for iteration k≥1. (DA0 1) Propose a transition Θ0∼qΘk−1(·). (DA0 2) Proceed to Step (DA0 3) with probability min 1,µ∗ u(Θ0)qΘ0(Θk−1) µ∗ u(Θk−1)qΘk−1(Θ0). Otherwise, set (Θk, ζ(i) k, Z(i) k)←(Θk−1, ζ(i) k−1, Z(i) k−1)) and exit. (DA0 3) Given Θ0, generate (ζ0(1:m), Z0(1:m)). With probability min 1,(Pm i=1 ζ0(i))/µ∗ u(Θ0) (Pm i=1 ζ(i) k−1)/µ∗ u(Θk−1) set (Θk, ζ(i) k, Z(i) k)←(Θ0, ζ0(i), Z0(i)). Otherwise, set (Θk, ζ(i) k, Z(i) k)← (Θk−1, ζ(i) k−1, Z(i) k−1). Assuming 1 ∈ L1(ν) and the PM chain is Harris ergodic (see Section 2), for f∈ L1(ν) the estimator 1 n n X k=1 ˆ ζ(i) kf(Θk, Z(i) k)n→∞ −−−→ ν(f):=Eν[f] (3) with ˆ ζ(i) k:=ζ(i) k/Pm j=1 ζ(j) k, is a consistent estimator for ν(f) [6]. 1.2. Accelerations based on an approximation. Suppose one has an approximation µ∗of ν∗, by which we mean that µ∗is some probability measure on T such that µ∗(θ) = 0 =⇒ν∗(θ) = 0,(4) and there is some constant cµ>0 (perhaps unknown) such that we can evaluate unnormalised µ∗ u(θ) = cµµ∗(θ) for all θ∈T. The approximation µ∗could arise, for example, when subsampling data [10, 42] or using a more tractable diffusion model instead of a Markov jump process model [26], giving rise to the approximate posterior µ∗. We next describe delayed-acceptance (DA) in two variants, and IS, all of which make use of the approximation µ∗. 1.2.1. Delayed-acceptance MCMC in two variants. If one has an approximation µ∗ of ν∗as above, one can use a PM acceleration technique known as DA [17, 32, 34], which has garnered considerable interest. With (Θ0, ζ(1:m) 0, Z(1:m) 0)∈T×[0,∞)m× Zminitial values with µ∗(Θ0)>0 and Pm i=1 ζ(i) 0>0, for k= 1, . . . , n, iterate as given in Algorithm 2. The DA estimator for ν(f) is given in (3), which is the same as in the PM case. Note that Step (DA0 3), which involves possibly expensive unbiased estimator generation, is only run if the proposal Θ0is assigned sufficient approximate probability in Step (DA0 2) which means it is likely to be accepted in Step (DA0 3). Consider now Algorithm 3, which is a variant, DA1, of DA0 Algorithm 2. DA1 is considered in [34, ‘surrogate transition method,’ Section 9.4.3]. In the deterministic case 1 mPm i=1 ζ(i)=cνν∗(θ) almost surely for all θwith (ζ(1:m), Z(1:m))∼Qθ(·), 4 JORDAN FRANKS AND MATTI VIHOLA Algorithm 3 Delayed-acceptance (DA1), for iteration k≥1. (DA1 1) Propose a transition Θ0∼qΘk−1(·). (DA1 2) With probability min 1,µ∗ u(Θ0)qΘ0(Θk−1) µ∗ u(Θk−1)qΘk−1(Θ0) set Θ00 ←Θ0. Otherwise, set Θ00 ←Θk−1. (DA1 3) Given Θ00, generate (ζ00(1:m), Z00(1:m)), With probability min 1,(Pm i=1 ζ00(i))/µ∗ u(Θ00) (Pm i=1 ζ(i) k−1)/µ∗ u(Θk−1) set (Θk, ζ(i) k, Z(i) k)←(Θ00, ζ00(i), Z00(i)). Otherwise, set (Θk, ζ(i) k, Z(i) k)←(Θk−1, ζ(i) k−1, Z(i) k−1). Algorithm 4 Importance sampling correction of approximate MCMC (IS Phase 1) Let (Θ0, ζ(1:m) 0, Z(1:m) 0)∈X×(0,∞)m×Zmbe some initial values with µ∗(Θ0)>0 and Pm i=1 ζ(i) 0>0. For k= 1, . . . , n, do: i. Propose a transition Θ0∼qΘk−1(·). ii. With probability min 1,µ∗ u(Θ0)qΘ0(Θk−1) µ∗ u(Θk−1)qΘk−1(Θ0) set Θk←Θ0. Otherwise, set Θk←Θk−1. (IS Phase 2) For each k∈ {1, . . . , n}, given Θk, generate (ζ(1:m) k, Z(1:m) k). With ξ(i) k:=ζ(i) k/µ∗ u(θ), form the IS estimator EIS n(f):=Pn k=1 Pm i=1 ξ(i) kf(Θk, Z(i) k) Pn k=1 Pm i=1 ξ(i) k n→∞ −−−→ ν(f),(5) consistent if the Phase 1 chain is Harris ergodic and 1, f ∈ L1(ν). then DA0 and DA1 have the same transition kernels (Proposition 14). But in general DA1 has lower asymptotic variance than DA0 (Proposition 14), although DA0 is probably more computationally efficient. This is evident from the fact that Step (DA1 3) is performed at every iteration of DA1 (Algorithm 3). 1.2.2. Importance sampling correction of approximate MCMC. MCMC-IS (Algorithm 4) consists of targeting an approximation µ∗of ν∗with MCMC, and then using importance sampling (IS) correction over the latent states [20, 24, 25, 27, 40, 51]. Let µ∗be an approximation of ν∗as in (4). Note that IS Phase 2, which involves the generation of unbiased estimators, may be done independently for each kwhich allows for efficient parallelisation. 1.3. Defining the asymptotic variance. As PM/DA and MCMC-IS are viable approaches for consistent inference, the central question is which one should be used. The standard measure of statistical efficiency for MCMCs is the asymptotic variance. IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 5 Definition 1 (Asymptotic variance).Let (Xk) be a ν-Harris ergodic Markov chain with transition L. For f∈L2(ν) the asymptotic variance of fwith respect to Lis defined, whenever the limit exists in [0,∞], as var(L, f):= lim n→∞ Eh 1 √n n X k=1 [f(X(s) k)−ν(f)]2i,(6) where (X(s) k) denotes a stationary version of the chain (Xk), i.e. X(s) 0∼ν. For reversible L, which is the focus of this paper, var(L, f) always exists in [0,∞] [see 49]. Moreover, a CLT holds under general conditions. Proposition 1. Let (Xk)k≥1be an aperiodic ν-reversible Harris ergodic Markov chain with transition L. If f∈L2(ν)and var(L, f)<∞, then, for all initial distributions, 1 √nn X k=1 [f(Xk)−ν(f)]n→∞ −−−→ N0,var(L, f),in distribution,(7) where N(a, b2)is a normal distribution with mean aand variance b2. Proposition 1 follows from [29, Cor. 1.5], where it holds under all initial conditions because of the Harris ergodicity assumption [see 21, Cor. 21.1.6]. Proposition 1 above explains the importance of the asymptotic variance, since it is the CLT limiting variance. The asymptotic variance characterises the statistical efficiency of the method in the asymptotic regime, but also characterises the finite sample efficiency in the finite regime [see 46]. 1.4. Comparing the asymptotic variances. We first define some objects. Given Xk= (Θk, ζ(1:m) k, Z(1:m) k) and f:X→R, define ζk(f) = 1 m m X i=1 ζ(i) kf(Θk, Z(i) k),ˆ ζ(i) k:=ζk(f) ζk(1) ξk(f):=ζk(f) µ∗ u(Θk). We also define the MCMC-IS kernel to be ¯ Kθv(dθ0,dv0):=Kθ(dθ0)Qθ0(dv0) (8) where Kis the approximate marginal MH kernel in IS (Algorithm 4) Phase (1) with invariant measure µ∗[51]. ¯ Kis ¯µ-reversible, where ¯µ(dθ, dv):=µ∗(dθ)Qθ(dv). Define the extended IS weights wu(Xk):=ξk(1) and w(Xk):=wu(Xk)∗(cµ/cν). Assume 1 ∈ L1(ν) and (4) holds. By our discussion of the asymptotic variance, varL, ˆ ζ(f)is assigned to the PM/DA estimator n−1Pn k=1 ˆ ζk(f) given in (3). Now let ¯ Kbe the MCMC-IS kernel defined in (8), and note that the IS estimator (5) can be written as EIS n(f) = 1 nPn k=1 ξk(f) 1 nPn k=1 ξk(1) = 1 nPn k=1 wu(Xk)ˆ ζk(f) 1 nPn k=1 wu(Xk).(9) Since var( ¯ K, wuˆ ζ(f)) is assigned to the numerator from the definition of the asymptotic variance, and the denominator converges almost surely to cν/cµunder a Harris ergodicity assumption, the asymptotic variance var( ¯ K, wˆ ζ(f)) is assigned to the IS estimator by (7) and Slutsky’s lemma. 6 JORDAN FRANKS AND MATTI VIHOLA For a function g:X→Rand probability νon X, define the norm kgkL∞(ν):=ν-ess sup x∈X|g(x)|.(10) Let us define the marginal weight w∗(θ):=ν∗(θ)/µ∗(θ) and note that kw∗kL∞(µ∗)≤ kwkL∞(¯µ). Under Harris ergodicity, we remark that a consistent upper bound estimator for kwkL∞(¯µ)is given by cn:=1 n−nb n X k=nb+1 ξk(1)−1 max nb<k≤nξk(1),(11) which is moreover a consistent estimator for kwkL∞(¯µ)as nb, n → ∞, where nb≥1 denotes the burn-in of the chain. Let Lbe the transition corresponding to the PM, DA0, or DA1 chain. Then L has invariant probability π(dθ, dζ(1:m),dz(1:m)):=c−1 νdθQθ(dζ(1:m),dz(1:m))ζ(1) Define L2(ν):={f∈ L1(ν) : f2∈ L1(ν)}, where we recall L1(ν) was defined through (2). Our main result (Theorem 12) in the present context says the following. Corollary 2. Suppose 1∈ L1(ν). Let Lbe the transition kernel of the PM, DA0 or DA1 chains defined in Algorithm 1-3 respectively. Suppose (4) holds, and let ¯ Kbe the MCMC-IS kernel (8) corresponding to Algorithm 4, and let f∈ L2(ν). Suppose Kand Lare Harris ergodic and var( ¯ K, wˆ ζ(f)) <∞. Set ¯ f:=f−ν(f). The following hold: (i) If kw∗kL∞(µ∗)<∞then, var¯ K, wˆ ζ(f)≤ kw∗kL∞(µ∗)varL, ˆ ζ(f)+ varπˆ ζ(f)+ 3 var¯µwˆ ζ(¯ f). (ii) If kwkL∞(¯µ)<∞, then var¯ K, wˆ ζ(f)+ var¯µwˆ ζ(¯ f)≤ kwkL∞(¯µ)varL, ˆ ζ(f)+ varπˆ ζ(f). (iii) If wˆ ζ(f)∈L2(¯µ), then var¯ K, wˆ ζ(f)+ var¯µwˆ ζ(¯ f)≥(¯µ-ess inf w)varL, ˆ ζ(f)+ varπˆ ζ(f). Although these bounds do not provide an ordering of asymptotic variances as in the Peskun-Tierney ordering for direct MCMCs, we could never hope these bounds to do so in our context: we give simple examples showing that PM/DA (resp. IS) can do arbitrarily better than IS (resp. PM/DA) in terms of the asymptotic variance in Appendix D. IS seems to perform better than PM/DA when the approximation is good in the sense that the weight whas a low supremum, as Corollary 2 would suggest. In the usual unbounded space case, this means that µ(θ) would need to have fatter tails than ˙ν(θ), or at least that ν(θ)/µ(θ) is bounded, which can often be done by inflating µu(θ) uniformly by a positive constant [see 51]. IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 7 The rest of this paper is concerned with proving Corollary 2 and other versions, for example, for general reversible chains, IS jump chains, and when µ∗ u(θ) requires unbiased estimators. 1.5. Previous work. In various settings and different ways, we are not the first to compare direct MCMC with IS MCMC. A study of self-normalised IS versus the independence MH has been made in [33]. Asymptotic variances are explicitly computed and compared in some discrete examples in [12] who find that IS and MH can be competitive, but that MH can do much better (see also [11, Sect. 4.2]). On the other hand, [50] study independent IS with unbiased estimators, and find that this performs better than PM in their experiments (see also [16]). The IS versus DA question is noted in [18, Sect. 3.3.3], who mention the likely improvement of IS over DA in massive parallelisation. A methodological comparison of the alternatives in the general MCMC and joint inference context is made in [51], who investigate empirically the relative efficiencies, finding that IS and DA can be competitive, with IS doing slightly better than DA in their experiments, with little or no parallelisation. The gap widens with increased parallelisation, a known strength of the IS correction [see 18, 30, 51]. We consider here general reversible Markov chains, in particular PM/DA, and seek a Peskun type ordering of the asymptotic variances. 1.6. Outline. After preliminaries in Section 2, we state in Section 3 the Peskun type ordering result for normalised IS (Theorems 3) and augmented IS kernels (Theorem 5). We define jump chains and self-normalised importance sampling (SNIS) in Section 4, before proceeding to Section 5, where we consider a general auxiliary variable framework which accommodates IS and PM type schemes that use unbiased estimators. Specific PM type algorithms and kernels which we consider are given in Section 6, and we compare them with IS (Theorem 16). We discuss some stability considerations in Section 7. Proofs of the Peskun type orderings are given in Appendix A. Dirichlet form bounds and proof of the main comparison application (Theorem 16) are found in Appendix B. Appendix C mentions some properties of augmented chains. Appendix D contains the examples mentioned earlier. 2. Notation and definitions 2.1. Notation. The spaces we consider Xare assumed equipped with a σ-algebra, denoted B(X), and with a σ-finite dominating measure, denoted ‘dx.’ Product spaces will be assumed equipped with their product σ-algebras and corresponding product measures. If µis a probability density on X, we denote the corresponding probability measure with the same symbol, so that µ(dx) = µ(x)dx. For p∈[1,∞), we denote by Lp(µ) the Banach space of equivalence classes of measurable f:X→Rsatisfying kfkp<∞under the norm kfkLp(µ):= {R|f(x)|pµ(dx)}1/p. We similarly define L∞(µ) under the norm kfkL∞(µ)as in (10). We denote by Lp 0(µ) the subset of Lp(µ) with µ(f) = 0, where µ(f):= Rf(x)µ(dx). For f∈L1(µ) and Kx(dx0) a Markov kernel on X, we define 8 JORDAN FRANKS AND MATTI VIHOLA µK(A):=Rµ(dx)Kx(A) for A∈ B(X), Kf(x):=RKx(dx0)f(x0), and inductively Knf(x):=Kn−1(Kf)(x) for n≥2. For f, g ∈L2(µ), we define hf, giµ:=Rf(x)g(x)µ(dx), kfkµ:= (hf, fiµ)1/2,and varµ(f):=µ(f2)−µ(f)2. For m∈Nand x(i)∈Xfor i= 1,...m, we write x(1:m):= (x(1), . . . , x(m)). Throughout, νwill denote the target probability of interest, and for ϕ∈L1(ν) we set ¯ϕ:=ϕ−ν(ϕ), element of L1 0(ν). 2.2. Definitions. Let µand νbe σ-finite measures on X. If µ(A) = 0 implies ν(A) = 0 for all A∈ B(X), we say that νis absolutely continuous with respect to µ, and write νµ. Suppose νµ. Recall that a Radon-Nikod´ym derivative of νwith respect to µis a non-negative measurable function dν dµ (x) on Xsuch that µ(dν dµg) = ν(g) for all g∈L1(ν). If also µand νare probability densities, then it is easy to see that dν dµ(x) is in L1(µ), and is equivalent with ν(x) µ(x). Let µbe a probability on X. A Markov chain Kon Xis µ-invariant if µK =µ. If also hf, Kfiµ≥0 for all f∈L2(µ), then Kis positive. If µ(dx)Kx(dx0) = µ(dx0)Kx0(dx), then Kis said to satisfy detailed balance with respect to µ, or briefly, Kis µ-reversible. This implies that Kis µ-invariant, and that the Dirichlet form EK(f) for f∈L2(µ) satisfies EK(f):=hf, (1 −K)fiµ=1 2Zµ(dx)Kx(dx0)f(x)−f(x0)2.(12) We say Markov chain Kis µ-Harris ergodic if Kis µ-invariant, ψ-irreducible, and Harris recurrent. See [36] for the definition of ψ-irreducibility and Harris recurrence, and further details. Most MCMC schemes are Harris ergodic, although a careless implementation can lead to a non-Harris chain [see 43]. 3. Peskun type ordering for normalised importance sampling 3.1. General case. Let µand νbe probability measures on a measurable space X, and let w:X→[0,∞) be a non-negative measurable function. Assumption 1 (Importance sampling).A triplet (µ, ν, w) is such that νµ and w(x) = dν dµ(x) is the Radon-Nikod´ym derivative. Assumption 2. A heptuple (µ, ν, w, K, L, c, c) is such that (µ, ν, w) satisfies Assumption 1, Kand Lare Harris ergodic Markov chains reversible with respect to µand ν, respectively, and the constants c, c ≥0 satisfy (a) cEK(g)≤ EL(g)≤cEK(g), for all g∈L2(µ), and (b) c≤w≤c,µ-a.e. Theorem 3. If Assumption 2 holds, then for all ϕ∈L2(ν), var(K, wϕ) + varµ(w¯ϕ)≤cvar(L, ϕ) + varν(ϕ),(13) var(K, wϕ) + varµ(w¯ϕ)≥cvar(L, ϕ) + varν(ϕ).(14) Remark 4.Here, we recall the notation ¯ϕ:=ϕ−ν(ϕ). Regarding Theorem 3, whose proof is given in Appendix A: (i) If w= 1 constant, in which case µ=ν, it reduces to [4, Lemma 32]. If also (c, c) = (0,1), it is the covariance ordering [37, Thm. 4.2], which is a IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 15 8, given by, KDA1 θuv (dθ0,du0,dv0) = Kθu(dθ0,du0)Q(V) θ0u0(dv0) min 1, ξ0(1)/ξ(1) + [1 −αDA1(θ, u, v)]δθuv(dθ0,du0,dv0),(25) where αDA1(θ, u, v):=RKθu(dθ0,du0)Q(V) θ0u0(dv0) min 1, ξ0(1)/ξ(1). Let Kbe ‘µ-proposal-rejection kernel,’ that is, a µ-reversible kernel of the form Kθu(dθ0,du0) = qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0) + rK(θ, u)δθu(dθ0du0) (26) for some function α: (T×U)2→[0,1] and rK= 1−Rqθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0). The DA0 correction of Kis defined to be KDA0 x(dx0) = qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Q(V) θ0u0(dv0) min 1, ξ0(1)/ξ(1) + [1 −αDA0(x)]δθuv(dθ0,du0,dv0),(27) where αDA0(x) = Rqθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Q(V) θ0u0(dv0) min 1, ξ0(1)/ξ(1), and X:=T×U×V,x∈X,x:= (θ, u, v). Decreasing the variability of ξ0(1) = ζ0(1)/η0(1) by coupling the u0and v0variables can lead to improved mixing of (27), and is similar in idea to recently proposed ‘correlated PM’ [19] and ‘MHAAR’ [3] chains. The mere requirement of reversibility allows the kernel Kto be taken to be approximate versions of the two chains listed above, or an approximate DA or ‘multi-stage DA’ [10]. Regardless, the most straightforward choice for Kis the (approximate) PM kernel targeting µwith proposal q, given by, Kθu(dθ0,du0) = qθ(dθ0)Q(U) θ0(du0) min 1, r(U)(x, x0) + [1 −α(θ, u)]δθu(dθ0,du0),(28) where α(θ, u):=Rqθ(dθ0)Q(U) θ0(du0) min 1, r(U)(x, x0). The asymptotic variance of DA1 is never more than that of DA0. Proposition 14. If Kis the µ-proposal-rejection kernel (26), then: (i) var(KDA1, g)≤var(KDA0, g)for all g∈L2(π). (ii) If V∼Q(V) θu (·)with V= (M, Z(1:M), ζ(1:M))has the property that ζ(1) = ϕ(θ, u) (29) is a deterministic function ϕof θand u, then KDA0 =KDA1. However, for the reason discussed in Section 6.1, DA0 is likely more computationally efficient than DA1 in practice. We define the PM parent kernel Pof KDA1 to be given by Pθuv(dθ0,du0,dv0) = qθ(dθ0)Q(U) θ0(du0)Q(V) θ0u0(dv0) min 1, r(V)(x, x0) + [1 −αPMP(θ, v)]δθuv(dθ0,du0,dv0),(30) where αPMP(θ, v):=Rqθ(dθ0)Q(U) θ0(du0)Q(V) θ0u0(dv0) min 1, r(V)(x, x0). We define a probability kernel from Tto Vby ˆ Q(V) θ(dv):=ZU Q(U) θ(du)Q(V) θu (dv) (31) 16 JORDAN FRANKS AND MATTI VIHOLA We then define the following PM kernel with proposal q, Mθv(dθ0,dv0) = qθ(dθ0)ˆ Q(V) θ0(dv0) min 1, r(V)(x, x0) + [1 −αPM(θ, v)]δθv(dθ0,dv0),(32) targeting ˆπ(dθ, dv):=RUπ(dθ, du, dv), where αPM(θ, v):=Rqθ(dθ0)ˆ Q(V) θ0(dv0) min 1, r(V)(x, x0). When Ukand Vkare independent given θ, i.e. Q(V) θu (dv) = Q(V) θ(dv),(33) then M(32) is the standard PM with proposal q, since, ˆ Q(V) θ(dv) = Q(V) θ(dv). Proposition 15. If Kis the approximate PM (28), and L∈ {M, P}, then: (i) var(L, ˆ ζ(f)) ≤var(KDA0,ˆ ζ(f)) for all f∈L2 π(ν). (ii) If (29) holds, then for all f∈L2 π(ν), var(L, ˆ ζ(f)) ≤var(KDA1,ˆ ζ(f)). 6.3. Comparison with importance sampling correction. Note that the following result only involves the weight, not the Dirichlet forms. Theorem 16. Suppose Assumption 4 (PM kernels) holds, and that one of the following conditions for pairs of kernels holds: (I) L=KDA0 is DA0 correction (27), and Kis µ-proposal-rejection (26), (II) L=KDA1 is DA1 correction (25), and Kis µ-reversible, (III) L=Pis the PM parent (30), and Kis the approx. PM (28), or (IV) L=Mis the PM kernel (32), and Kis the approx. PM (28). Assume Kand Lare Harris ergodic, and a function f∈ L2(ν)is such that VIS f<∞. The following statements hold: (i) The IS asymptotic variance (22) satisfies, with c:= ¯µ-ess inf w, VIS f+µ(a)var¯µwˆ ζ(¯ f)≤µ(a)kwkL∞(¯µ)varL, ˆ ζ(f)+ varπˆ ζ(f)+D¯ f VIS f+µ(a)var¯µwˆ ζ(¯ f)≥µ(a)·c·varL, ˆ ζ(f)+ varπˆ ζ(f)+D¯ f. (ii) With NK:= 0 if Kis positive and NK:= 1 if not, the following holds: VIS f≤µ(a)kw∗kL∞(µ)varL, ˆ ζ(f)+ varπˆ ζ(f) + (1 + 2NK)µ(a)var¯µwˆ ζ(¯ f)+D¯ f. See Remark 13(i) for wand w∗. See Appendix B for the proof of Theorem 16, which follows from Theorem 12, after bounding the Dirichlet forms. 7. Discussion and further stability considerations A necessary condition for a successful implementation of an IS or PM scheme is a simple support condition, Assumption 4(ii), that can often be easily ensured by Remark 8(ii). On the other hand, Theorem 16 depends on a uniform bound on the marginal weight w∗∝m1, with mf(θ, u) as in (20). This bound is much weaker than a bound on w, and can often be ensured. For example, assuming that η(1)m1is bounded, one can often inflate η(1) as in Remark 8(ii) to obtain IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 17 an uniform bound on w∗. Other techniques may be applicable if a bounded w∗ is particularly desired, such as a combination of cutoff functions, approximations, or tempering [see 39, 51]. When considering a PM/DA implementation, the issue of boundedness of the full weight w∝ζ(1)/η(1) takes particular importance, more so than in the case with IS. This is because PM and DA are more liable to be poorly mixing, while IS is less affected by noisy estimators. Namely, if ζ(1) is not bounded, then PM parent and KDA0, with Kas in (28), are not geometrically ergodic (Proposition 25). On the other hand, the IS chain may converge fast, even in the case of unbounded ζ(1). For example, if Kis a random walk MH chain, then Kis geometrically ergodic essentially if µhas exponential or lighter tails and a certain contour regularity condition holds [28, 45], where we have said nothing about the exact level estimator ζ(1). We then apply Lemma 24(v), which says that whenever Kis geometrically ergodic then so is ¯ K, to conclude that the IS chain is geometrically ergodic, even in the case of unbounded ζ(1). This may be beneficial if adaptation is used [5, 7, 44]. Of course, high variability affects also the IS estimator, but we believe this noise to be a smaller issue in IS, as the noise is in the IS output estimator rather than in the acceptance ratio as in PM/DA. This can make a significant difference in the evolution and ergodicity of the chains, as described above. Acknowledgments Support has been provided for JF and MV from the Academy of Finland (grants 274740, 284513 and 312605), and for JF from The Alan Turing Institute. JF thanks the organisers of the 2017 SMC course and workshop in Uppsala. Appendix A. Proofs for the Peskun type orderings A.1. Subprobability kernels. Let Kbe a µ-reversible Markov kernel on X. For all λ∈(0,1], λK is a subprobability kernel:λK(x, X)≤1 for all x∈X. The Dirichlet form EλK(f) of the subprobability kernel λK is EλK(f):=hf, (1 −λK)fiµ=λEK(f) + (1 −λ)kfk2 µ,(34) defined for f∈L2(µ). For f∈L2 0(µ), if (1 −K)−1fexists in L2(µ), then by (6), var(K, f)=2hf, (1 −K)−1fiµ−µ(f2) [see 9]. Following [9, 49], we then (formally) extend Definition 1 of the asymptotic variance to subprobability kernels: for λ∈(0,1), the operator (1 −λK) is always invertible, and we define var(λK, f):= 2 f, (1 −λK)−1fµ−µ(f2).(35) Moreover, (12) and (34) imply for λ∈(0,1] that 1 −λK is a positive operator, i.e. EλK(f)≥0 for all f∈L2(µ). By a result attributed to Bellman [14, Eq. 14], for positive self-adjoint operators, and used e.g. in [1, 9, 15, 38, 37], we have another asymptotic variance representation: for all λ∈(0,1) and f∈L2 0(µ), var(λK, f) = 2 sup g∈L2(µ)2hf, giµ−EλK (g)−µ(f2).(36) 18 JORDAN FRANKS AND MATTI VIHOLA Here, the supremum is attained with g:= (1−λK)−1f, in which case (36) simplifies to (35). For λ∈(0,1), equalities (35–36) hold and are finite for any f∈L2 0(µ). The function λ7→ var(λK, f) has a limit as λ↑1 on the extended real numbers [0,∞], and var(K, f) equals this limit [49]. A.2. Normalised importance sampling ordering. We set NK:=−inf µ(g)=0,µ(g2)=1 hg, Kgiµ(37) for a µ-reversible kernel K, so that the left spectral gap of Kis 1 −NK[see 9]. We have NK∈[−1,1] in general, but NK∈[−1,0] if Kis positive. The conditions of the next two lemmas will seem more natural once Lemma 20 is stated. Lemma 17. Suppose (µ, ν, w, K, L, c, c)satisfies Assumption 3 on X:=T×Y. Let ϕ∈L2 0(ν)be such that wϕ ∈L2(µ). Define uλ:= (1 −λK)−1(wϕ)and ˇuλ:=uλ−wϕ, in L2(µ)for all λ∈(0,1). The following hold: (i) If uλ(θ, y) = uλ(θ),λ∈(0,1), then (13) holds. (ii) If ˇuλ(θ, y) = ˇuλ(θ),λ∈(0,1), then (16) holds, with NKas in (37). Proof. Note that L2(µ∗)⊂L2(ν∗) by Assumption 3(b). For g∈L2(µ∗), EλL(g) = λEL(g) + (1 −λ)ν∗(g2)≤cλEK(g) + (1 −λ)ν∗(g2), by Assumption 3(a). From the above first equality, now for λK and µ∗, EλL(g)≤cEλK(g)−(1 −λ)µ∗(g2)+ (1 −λ)ν∗(g2) =cEλK(g)−(1 −λ)µ∗g2[c−w∗]≤cEλK(g),(38) by Assumption 3(b). Since 1 −λK is self-adjoint on L2(µ), we also note that EλK(ˇuλ) = EλK(uλ−wϕ) = EλK(uλ) + EλK(wϕ)−2kwϕk2 µ, as hvλ,(1 −λK)wϕiµ=kwϕk2 µ.Regardless of λ∈(0,1), 1 −λK has support of its spectral measure contained in [0,1+NK]. Hence, EλK(wϕ)≤(1+NK)kwϕk2 µ, so EλK(ˇuλ)≤ EλK(uλ)+(NK−1) kwϕk2 µ.(39) We now compare the asymptotic variances. By (35), LS := var(λK, wϕ) + kwϕk2 µ= 2 hwϕ, uλiµ= 22hwϕ, uλiµ−EλK(uλ). With ψ:=uλfor (i), and with ψ:= ˇuλfor (ii) using (39), LS ≤22hwϕ, ψiµ−EλK(ψ)+Eψ, where Eψ:= 0 if ψ=uλand Eψ:= 2(1 + NK)kwϕk2 µif ψ= ˇuλ. Hence, LS ≤22hϕ, ψiν−EλK (ψ)+Eψ≤22hϕ, ψiν−(c)−1EλL(ψ)+Eψ, where we have used (38). Since ψ∈L2(µ∗)⊂L2(ν), LS ≤1 c2 sup g∈L2(ν)2hcϕ, giν−EλL(g)−kcϕk2 ν+ckϕk2 ν+Eψ =cvar(λL, ϕ) + kϕk2 ν+Eψ, IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 19 by (36). We then take the limit λ↑1 [49]. Noting that kwϕk2 µ= varµ(wϕ) since µ(wϕ) = ν(ϕ) = 0, we conclude.  Lemma 18. Suppose the assumptions of Lemma 17 hold, where cmay be also ∞. If vλ:= (1 −λL)−1(ϕ)satisfies vλ(θ, y) = vλ(θ), then (14) holds. Proof. The lower bound (14) is trivial if c= 0. Assume c > 0. Then µν, w−1≤c−1(implying L2(ν)⊆L2(µ)), and EK(g)≤c−1EL(g) for all g∈L2(ν). The result follows by applying Lemma 17(i).  Remark 19.Regarding Lemma 17 and Lemma 18: (i) The solution vλto the Poisson equation [see 36], (1 −λL)g=ϕin L2(µ), is also used in [9, Thm. 17] as a lemma for the proof of the convex order criterion Peskun type ordering for PM chains [9, Thm. 10]. (ii) It is reasonable to use a single constant cin Assumptions 3(a–b). If one replaces Assumption 3(b) with w∗≤c0µ∗−a.e., then, if c0< c, one obtains the same result after bounding a nonpositive quantity by zero in (38). If c0> c, then one would need to impose the unappealing condition that supλ∈(0,1) kuλk2 µ∗<∞and add a positive constant involving this bound to the final results. Anyways, for the the application in this paper, we have c=c0(Lemma 23). (iii) Assumption 3(a) can be replaced with the weaker assumption that EL(g)≤ cEK(g) for all g∈ G ⊂ L2(µ∗), where G:={uλ:λ∈(0,1)}for (i) and G:={ˇuλ:λ∈(0,1)}for (ii). Lemma 20. Let Kbe a µ-reversible chain on X=T×Y. For h∈L2(µ)and λ∈(0,1), set hλ:= (1 −λK)−1hand ˇ hλ:=hλ−h, which are in L2(µ). (i) If Y={y0}is the trivial space, then hλ(θ, y) = hλ(θ). (ii) If Kis an augmented kernel, then ˇ hλ(θ, y) = ˇ hλ(θ). Moreover, if also h(θ, y) = h(θ), then hλ(θ, y) = hλ(θ). Proof. (i) is clear. For (ii), we write the series representation for the inverse of an invertible operator and use Lemma 24(iii), to get that, hλ(θ, y) = ∞ X n=0 λnKnh(θ, y) = h(θ, y) + ∞ X n=1 λn˙ Kn(Qh)(θ). The result then follows.  Proof of Theorem 3. The upper bound (13) follows from Lemma 17(i) and Lemma 20(i), while (14) follows from Lemma 18 and Lemma 20(i).  Proof of Theorem 5. Follows by Lemma 17 and Lemma 20(ii).  A.3. Importance sampling schemes. The following CLT, based on Proposition 1, and asymptotic variance formula, are [51, Theorem 7 and 15]. Proposition 21. Under Assumption 5, the IS estimator (21) satisfies the CLT (22), with limiting variance VIS f=µ(a)var(K, mf) + µ(av ¯ f)/c2 ξ. Proof of Theorem 12. We first note that ξ(f):=ζ(f) η(1) =cζ cη·cη cζ ζ(1) η(1) ·ζ(f) ζ(1) =cξwˆ ζ(f). 20 JORDAN FRANKS AND MATTI VIHOLA By Slutsky’s lemma applied to (21) in the IS0 case, VIS0 f= var¯ K, ξ(f)/c2 ξ= var¯ K, wˆ ζ(f). Then (i) follows by Theorem 3, and (ii) by Theorem 5, for the IS0 case. To prove the result for the ISJ case, we first note the relationship VISJ f=µ(α)c−2 ξhvar(K, mf) + µ(v¯ f) + µ(α˜v¯ f−v¯ f)i=µ(α)VIS0 f+˜ D¯ f, from Proposition 21. The result then follows from the IS0 case.  Appendix B. Proofs for main comparison application Lemma 22. Let (K, L)be the pair of kernels as in (I),(II), or (III) of Theorem 16, where we assume that (¯µ, ν, w)satisfies Assumption 1, with (¯ K, ¯µ)the Q(V)- augmentation of K(23). Then, the following hold: (i) If kwkL∞(¯µ)<∞, then EL(g)≤ kwkL∞(¯µ)E¯ K(g)for all g∈L2(¯µ). If c:= ¯µ-ess inf w, then EL(g)≥cE¯ K(g)for all g∈L2(¯µ). (ii) If kw∗kL∞(µ)<∞, then EL(g)≤ kw∗kL∞(µ)E¯ K(g)for all g∈L2(µ). Proof. This is done separately below for the cases L∈ {P, KDA0, KDA1}. Set G:= [g(x)−g(x0)]2,g∈L2(¯µ), with x, x0∈X:=T×U×V. Then, EP(g) = 1 2Zπ(dx)qθ(dθ0)Q(U) θ0(du0)Q(V) θ0u0(dv0) min 1, r(V)(x, x0)G =1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)Q(V) θ0u0(dv0) min w(x), w(x)r(V)(x, x0)G =1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)Q(V) θ0u0(dv0) min w(x), w(x0)r(U)(x, x0)G, because w(x)r(V)(x, x0) = w(x0)r(U)(x, x0), well-defined on the set of interest. We then use the bounds c≤w≤ kwkL∞(¯µ)¯µ-a.e. to conclude (i) for L=P. Now assume g∈L2(µ), so G= [g(θ, u)−g(θ0, u0)]2. By Jensen’s inequality and concavity of (x, x0)7→ min{x, x0}when one of x, x0≥0 is held fixed, EP(g) = 1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)GZQ(V) θ0u0(dv0) min w(x), w(x0)r(U)(x, x0) ≤1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)Gmin w(x), w∗(θ0, u0)r(U)(x, x0). Here, we have used that r(U)(x, x0) does not depend on v0∈V, and that Zw(x)Q(V) θu (dv) = cη cζ 1 η(1) Zζ(1)Q(V) θu (dv) = π∗(dθ, du) µ(dθ, du)=w∗(θ, u). We then apply Jensen again, this time integrating out v∈V, to get, EP(g) ≤1 2ZdθQ(U) θ(du)η(1) cη qθ(dθ0)Q(U) θ0(du0)GZQ(V) θu (dv) min w(x), w∗(x0)r(U)(x, x0) ≤1 2ZdθQ(U) θ(du)η(1) cη qθ(dθ0)Q(U) θ0(du0) min w∗(θ, u), w∗(θ0, u0)r(U)(x, x0)G. IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 21 We then apply the bound w∗≤ kw∗kL∞(µ)µ-a.e. and use the fact that EK(g) = E¯ K(g) for all g∈L2(µ) to conclude (ii) for L=P. Now consider the case L=KDA0. With G:= [g(x)−g(x0)]2on X2, EKDA0 (g) = 1 2Zπ(dx)qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Q(V) θ0u0(dv0) min n1,w(x0) w(x)oG =1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Q(V) θ0u0(dv0) min w(x), w(x0)G, for all g∈L2(¯µ). As before, this allows us to conclude (i) for L=KDA0. Now assume g∈L2(µ), with G:= [g(θ, u)−g(θ0, u0)]2. By Jensen, EKDA0 (g)≤1 2Z¯µ(dx)qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Gmin w(x), w∗(θ0, u0) ≤1 2Zµ(dθ, du)qθ(dθ0)Q(U) θ0(du0)α(θ, u;θ0, u0)Gmin w∗(θ, u), w∗(θ0, u0), which allows us to conclude (ii) as before. Now consider the case L=KDA1. With G:= [g(x)−g(x0)]2on X2, EKDA1 (g) = 1 2Zπ(dx)Kθu(dθ0,du0)Q(V) θ0u0(dv0) min n1,w(x0) w(x)oG =1 2Z¯µ(dx)Kθu(dθ0,du0)Q(V) θ0u0(dv0) min w(x), w(x0)G, for all g∈L2(¯µ). As before, this allows us to conclude (i) for L=KDA1. Now assume g∈L2(µ), with G:= [g(θ, u)−g(θ0, u0)]2. By Jensen, EKDA1 (g)≤1 2Z¯µ(dx)Kθu(dθ0,du0)Gmin w(x), w∗(θ0, u0) ≤1 2Zµ(dθ, du)Kθu(dθ0,du0)Gmin w∗(θ, u), w∗(θ0, u0), which allows us to conclude (ii) as before.  Lemma 23. With assumptions as in Lemma 22, and additionally assuming that Kand Ldetermine Harris ergodic chains, the following hold: (i) If kwkL∞(¯µ)<∞, then (¯µ, π, w, ¯ K, L, c, kwkL∞(¯µ))satisfies Assumption 2. (ii) If kw∗kL∞(µ)<∞, then (¯µ, π, w, ¯ K, L, 0,kw∗kL∞(µ))satisfies Assumption 3. Proof. Lemma 22(i) and (ii) imply respectively (i) and (ii).  Proof of Theorem 16. The support condition Assumption 4(ii) implies that (¯µ, π, w) satisfies Assumption 1. Under conditions (I), (II), or (III), the result follows by Lemma 23 and Theorem 12. Assume condition (IV). Because g:=ˆ ζ(f) is a function on X=T×U×V which does not depend on the second coordinate, Pkg(θ, u, v) = Mkg(θ, v) for all (θ, u, v)∈Xand k≥1. Therefore, var(M, g) = var(P, g).  Proof of Proposition 14. For any g∈L2(π), set G:= [g(θ, u, v)−g(θ0, u0, v0)]2. We have EKDA1 (g) = EKDA0 (g) + 1 2Zπ(dx)rK(θ, u)Q(V) θu (dv0) min 1,ξ0(1) ξ(1) G, 22 JORDAN FRANKS AND MATTI VIHOLA so (i) follows from the covariance ordering. For (ii), we have KDA1 x(dx0) = KDA0 x(dx0)−(1−αDA0(x))δx(dx0)+rK(θ, u)δx(dx0)+(1−αDA1(x))δx(dx0), from which we conclude, since αDA1(x) = αDA0(x) + rK(θ, u). Proof of Proposition 15. (i) is essentially well-known [see 10], and (ii) is straightforward to prove.  Appendix C. Properties of augmented kernels and ergodicity For measurable functions V:X→[1,∞) and f:X→R, we set kνkV:= sup f:|f|≤V ν(f),and kfkV:= sup x∈X |f(x)| V(x) for any finite signed measure νon X. Definition 4. Aµ-invariant Markov chain Kon Xis said to be (i) V-geometrically ergodic if there is a function V:X→[1,∞) such that kKn(x, ·)−µ(·)kV≤RV (x)ρn for all n≥1, where R < ∞and ρ∈(0,1) are constants. (ii) uniformly ergodic if Kis 1-geometrically ergodic. Lemma 24. Let Kθy(dθ0,dy0) = ˙ Kθ(dθ0)Qθ0(dy0)be an augmented kernel on T× Y. (i) The invariant measures of Kand ˙ Ksatisfy (µK =µ=⇒µ∗˙ K=µ∗), and ( ˙µ˙ K= ˙µ=⇒µK =µ),where µ(dθ, dy):= ˙µ(dθ)Qθ(dy).These implications hold with invariance replaced with reversibility. (ii) Kis µ-Harris ergodic ⇐⇒ ˙ Kis ˙µ-Harris ergodic. (iii) For all f∈L1(µ)and n≥1,Knf(θ, y) = ˙ Kn(Qf)(θ). (iv) Kis aperiodic ⇐⇒ ˙ Kis aperiodic. Kis positive ⇐⇒ ˙ Kis positive. (v) Kis geometrically ergodic ⇐⇒ ˙ Kis geometrically ergodic. (vi) Kis uniformly ergodic ⇐⇒ ˙ Kis uniformly ergodic. Proof. (i–iii) are [51, Lem. 21]. Proof of (iv) is straightforward. For (v), consider first the case that ˙ Kis ˙ V-geometrically ergodic: sup |f|≤ ˙ V|˙ Kn(f)(θ)−˙µ(f)| ≤ R˙ V(θ)ρn, n ≥1, with ˙ V:T→[1,∞) and constants Rand ρ. Define V(θ, y):=˙ V(θ). By (iii), sup |f|≤V|Knf(θ, y)−µ(f)|= sup |f|≤V|˙ Kn(Qf)(θ)−˙µ(Qf)|.(40) Since Qf(θ, y)≤QV (θ, y) = ˙ V(θ), we get that Kis V-geometrically ergodic. Assume now that Kis V-geometrically ergodic. Using (40), we have, sup |f|≤V|Knf(θ, y)−µ(f)|= sup g=Qf:|f|≤V|˙ Kng(θ)−˙µ(g)|,(41) for n≥1. Define ˙ V(θ):= infyV(θ, y).For all gsuch that |g(θ)| ≤ ˙ V(θ), set f(θ, y):=g(θ). Then |f| ≤ Vand Qf =g. By (41), ˙ Kis ˙ V-geometrically ergodic. This proves (v), and (vi) follows from the form of ˙ Vand V. IMPORTANCE SAMPLING VERSUS STANDARD AVERAGES 23 Figure 1. Two versions and two behaviours 20 1 ν∗µ∗ (a) ‘PM/DA better’ case 1 20 ν∗µ∗ν∗ (b) ‘IS better’ case Proposition 25. Consider the PM parent kernel (30) and the DA0 kernel KDA0 (27), with Kas in (28). If ζ(1) is not bounded, then PM parent and KDA0 are not V-geometrically ergodic. Proof. This is [6, Thm. 8] for PM chains. To prove that result for PM chains, or in particular for the PM parent chain (30), [6] show that for all  > 0, ν1{αPMP ≤}>0.(42) By [45, Thm. 5.1], one concludes that the PM parent is not V-geometrically ergodic [6]. Moreover, from min{1, r(U)(x, x0)}min{1, w(x0)/w(x)} ≤ min{1, r(V)(x, x0)},(43) it follows that αDA0(x)≤αPMP(x). By (42), one concludes that KDA0 also is not V-geometrically ergodic.  Appendix D. Toy examples of two extremes Let X:={0,1,2}and consider the two mass allocations for probabilities µ and νon Xand function f∈L2 0(ν) given pictorially in Figure 1 and precisely in Figure 3. Denote by q(r)the (reflected) random walk proposal on X, given by Figure 3. Mass allocations for µ,ν, and fon X={0,1,2},a∈[1 2,1). µ= ( 1−a 2 1−a 2a) ν= ( 1/2 1/2 0 ) f= ( 1 −1 0 ) (a) ‘MH/DA better’ case µ= ( 1/3 1/3 1/3 ) ν= ( a 2 1−a 21/2 ) f=√2 √a+a2( 1 0 −a) (b) ‘IS better’ case q(r) 0(x) = δ1(x), q(r) 1(x) = 1 2[δ0(x) + δ2(x)], and q(r) 2(x) = δ1(x), and by q(u) x(x0) the uniform proposal on X. We set K:=MH(q→µ) and let Lbe the MH or DA0 kernels, using proposals q(r)or q(u), and targeting ν. We use a parameter a∈[1 2,1) to allow for continuous intensity shifts in the mass allocations in our examples. Because µis constant on the support of ν, one can check that the MH and DA0 kernels coincide for a∈[1 2,1). The resulting IS and MH/DA asymptotic variances, var(K, wf) and var(L, f), can be computed by linear algebra using [see 29, Cor. 1.5]. They are listed in Table 1, and plotted in Figure 5. Here, UBa(f):= max(w)var(L, f) + ν(f2[max(w)−w]).(44) 24 JORDAN FRANKS AND MATTI VIHOLA Table 1. Asymptotic variance as a function of a∈[1/2,1) Proposal var(L, f)≤var(K, wf) var(L, f)≥var(K, wf) RW q(r)11 1−a−1+8a+a2 a2−1 9a 1+a uniform q(u)21 1−a−1+10a−a2 (1+a)215a 4(1+a) var(L, f)≤var(K, wf) var(L, f)≥var(K, wf) 0.6 0.7 0.8 0.9 1.0 5 10 15 0.6 0.7 0.8 0.9 1.0 20 40 60 80 0.6 0.7 0.8 0.9 1.0 5 10 15 20 25 0.6 0.7 0.8 0.9 1.0 1.5 2.0 2.5 3.0 Figure 5. Plots from Table 1: var(K, wf) ‘—’, var(L, f) ‘−−’, and UBa(f) ‘···’, vs. a∈[1 2,1). Here, in the top left, UBa(f) exactly coincides with var(K, wf). is the upper bound on var(K, wf) from Corollary 2. References [1] C. Andrieu. On randomand systematic-scan samplers. Biometrika, 103(3):719–726, 2016. [2] C. Andrieu, A. Doucet, and R. Holenstein. Particle Markov chain Monte Carlo methods. J. R. Stat. Soc. Ser. B Stat. Methodol., 72(3):269–342, 2010. (with discussion). [3] C. Andrieu, A. Doucet, S. Yıldırım, and N. Chopin. On the utility of Metropolis-Hastings with asymmetric acceptance ratio. Preprint arXiv:1803.09527, 2018. [4] C. Andrieu, A. Lee, and M. Vihola. Uniform ergodicity of the iterated conditional SMC and geometric ergodicity of particle Gibbs samplers. Bernoulli, 24(2), 2018. [5] C. Andrieu and ´ E. Moulines. On the ergodicity properties of some adaptive MCMC algorithms. J. Appl. Probab., 16(3):1462–1505, 2006.