Approximations of Geometrically Ergodic Reversible Markov Chains

1 Introduction

• Approximate transition dynamics address computationally expensive or intractable exact MCMC kernels, but require analysis of stability and reliability.The motivating approximations include deterministic low-rank Gaussian approximations and stochastic noisy Metropolis–Hastings.Source: §1 · p. 1
• The paper extends perturbation-error bounds from uniformly ergodic chains to reversible geometrically ergodic chains using L2 distances and L2(π)-geometric ergodicity.This relaxes the uniform contraction condition while retaining a quantitative framework for approximate Markov chains.Source: §1 · p. 1

1.1 Geometric Ergodicity

• Geometric ergodicity makes transient error decay exponentially and is less restrictive than uniform ergodicity, which often fails on nonfinite or noncompact state spaces.The paper uses this property as the relevant convergence guarantee for approximate chains.Source: §1.1 · p. 2

1.2 Outline of the Paper

• Theoretical results provide stationary-distribution distance bounds, sufficient conditions and rates for perturbed-chain geometric ergodicity, autocorrelation bounds, and Monte Carlo mean-squared-error bounds.These results are developed for several geometric-ergodicity definitions and metrics.Source: §1.2 · p. 2
• Applications supply checkable conditions for noisy and approximate Metropolis–Hastings, including deterministic target-density approximations and Monte Carlo within Metropolis.The applications illustrate how the general perturbation results can be used in practice.Source: §1.2 · p. 2

2 Related Work

• Johndrow et al. [18] obtain total-variation perturbation bounds under uniform contractivity and small operator-norm perturbations, including stationary, finite-time, and MSE guarantees.Their results cover approximate MCMC applications such as low-rank Gaussian-process and subsampling approximations.Source: §2 · pp. 2–3
• Mitrophanov derives finite-time and stationary total-variation bounds for uniformly ergodic chains without assuming kernel proximity, although error scales with total-variation kernel distance.Source: §2 · p. 3
• Rounding-error analyses by Roberts et al. use Lyapunov drift, V-norm closeness, uniformly small round-off error, and regularity of log V to preserve geometric ergodicity and control stationary distributions.These results also address settings where perturbed and original finite-time distributions can be mutually singular.Source: §2 · p. 3
• Wasserstein approaches bound stationary-distribution, finite-time, bias, variance, and mixing errors under drift-like, curvature, eccentricity, or perturbation-norm assumptions.Pillai and Smith [28] and Rudolf and Schweizer [35] apply such frameworks to approximate MCMC, including subsampling, autoregressive processes, and stochastic Langevin algorithms.Source: §2 · pp. 3–4
• Ferré et al. and Hervé and Ledoux establish perturbation results for V-geometrically ergodic or finite-rank approximating kernels, but depend on shared drift conditions.The paper notes that shared drift conditions may be difficult to verify or may fail for noisy or approximate MCMC.Source: §2 · p. 4
• The paper’s related-work gap is extending the simpler assumptions of uniform-ergodicity perturbation results to geometrically ergodic reversible chains.The authors avoid identifying Lyapunov drift conditions by expressing assumptions directly through transition kernels.Source: §2 · pp. 2, 4

3.1 Definitions and Notation

• For π-reversible chains, L2(π)-GE is equivalent to π-a.e.-TV-GE, with the optimal L2(π) rate equal to the spectral-radius characterization.The section formalizes norms on signed measures and geometric ergodicity definitions before exploiting self-adjoint spectral theory in L2(π).Source: §3.1 · p. 5

3.2 Assumptions

• The original kernel P is reversible, irreducible, aperiodic, and L2(π)-geometrically ergodic, while Pǫ is irreducible, aperiodic, maps L2(π) into itself, and satisfies ∥P −Pǫ∥L2(π) ≤ǫ.For Metropolis–Hastings constructions, finite ∥J∥L2(π) ensures the mapping and boundedness conditions, but verifying a sufficiently small perturbation norm remains the main analytic burden.Source: §3.2 · p. 6

3.3 Convergence Rates and Closeness of Stationary Distributions

• If ǫ < α, Pǫ has stationary distribution πǫ ∈L2(π) and is L2(π)-geometrically ergodic with factor 1 −(α −ǫ).The same factor also yields (L2(π), ∥·∥TV)-geometric ergodicity, and the theorem bounds πǫ's discrepancy from π in L2(π).Source: §3.3 · p. 7
• Under reversibility, L2(π)-GE, (L∞(π), ∥·∥L2(π))-GE, and (L∞(π), ∥·∥L1(π))-GE are equivalent with equal optimal rates.The perturbed chain also inherits GE in L1(πǫ), L2(πǫ), and total variation; if π ∈L∞(πǫ), its L2(πǫ) factor is ρ2 = (1 −(α −ǫ)).Source: §3.3 · pp. 8–9

3.4 Mean Squared Error Bounds for Monte Carlo Estimates

• Under ǫ < α, time-averaged marginal distributions converge with perturbation bounds, and Theorem 3.17 provides mean-squared-error bounds for estimates from a πǫ-reversible perturbed chain.The MSE result assumes ρ2 = (1−(α−ǫ)); drift-and-minorization alternatives may cover functions beyond the theorem's L2-based class.Source: §3.3 · p. 10, §3.4 · p. 11
• The richness of 4(πǫ) keeps the perturbation bound useful.Source: §3.4 · p. 11
• The MSE bound’s function class and value depend only on intrinsic features of the Markov chains.Source: §3.4 · p. 11
• Drift/minorization bounds instead depend on user-introduced features such as the drift function V, whose choices can change the function classes and bounds.Source: §3.4 · p. 11

4 Applications Markov Chain Monte Carlo

• The applications target noisy and approximate MCMC schemes whose transition kernels perturb Metropolis–Hastings through numerical, deterministic, or stochastic likelihood and acceptance-ratio approximations.Such perturbations arise when likelihoods involve numerical integration or Monte Carlo estimates, including generalized linear mixed models.Source: §4 · pp. 11–12, §4.1 · p. 12

4.1 Noisy and Approximate MCMC

• If the exact MH kernel is reversible and L2(π)-geometrically ergodic with contraction factor 1 − α, nMH remains geometrically ergodic when R(1 + ∥Q∥L2(π)) < α.The resulting L2(π) contraction factor is 1 − (α − R(1 + ∥Q∥L2(π))); if reversible, the perturbed chain is also L2(bπ)-geometrically ergodic.Source: §4.1 · p. 13

4.2 Application to Fixed Deterministic Approximations

• For fixed deterministic target approximations with θ-bounded relative error, geometric ergodicity transfers when θ < α, and the approximating chain is reversible.The perturbed chain has L2(bπ)-geometric contraction factor 1 − α + 2θ(1 + ∥Q∥L2(π)), with corresponding mean-squared-error bounds available.Source: §4.2 · pp. 13–14
• Laplace approximations for compactly supported GLMM parameters have constant relative error whose magnitude decreases with sample size, allowing geometric-ergodicity guarantees to transfer for sufficiently large samples.The transfer applies when the exact posterior MH procedure is geometrically ergodic and the proposal operator has finite L2(π) norm.Source: §4.2 · p. 14
• Uniform coreset guarantees imply that, with sufficiently large coreset size M, the relative-error conditions hold with high probability, so the approximate chain is geometrically ergodic with high probability.The framework also provides quantitative bounds for Monte Carlo estimates based on the approximating chain.Source: §4.2 · pp. 14–15

4.3 Application to Monte Carlo Within Metropolis

• For Monte Carlo within Metropolis, uniform boundedness assumptions on the approximation quantities yield a reversible perturbed chain that is L2(π)-geometrically ergodic when N exceeds the stated threshold.The same theory gives L2(bπ_N)-geometric ergodicity and mean-squared-error bounds, while the paper does not address the alternative case where uniform boundedness is dropped and the perturbed kernel is restricted to a bounded region.Source: §4.3 · pp. 16–17

Geometric ergodicity

• Equivalent L2(π)-geometric-ergodicity definitions for reversible chains permit the coefficient function C(μ) = ∥μ − π∥L2(π).This simplification is specific to reversible kernels and does not hold for non-reversible chains.Source: §A.1 · p. 20

Stationary distribution

• Under ε < α, P_ε has a unique stationary distribution π_ε ∈ L2(π) satisfying ∥π_ε − π∥L2(π) ≤ ε.The proof constructs an L2(π)-Cauchy sequence and uses completeness, stationarity, and continuity of norm.Source: §A.1 · pp. 21–22
• The perturbation expansion groups noncommuting P and Q_ε terms by leading P factors, enabling cancellation and an L2(π)-Cauchy bound.Here Q_ε = P_ε − P, and the norm decreases monotonically with the number of leading P factors.Source: §A.1 · pp. 21–22

Geometric ergodicity

• Under ε < α, P_ε is L2(π)-geometrically ergodic with contraction factor at most 1 − (α − ε).The bound follows by combining the perturbation error ε with the original chain’s contraction factor 1 − α.Source: §A.1 · p. 22

Theorem 3.4

• Lemmas A.4–A.6 combine with the triangle inequality to yield Theorem 3.4.The theorem therefore follows from stationary-distribution existence, an L2(π) distance bound, and perturbed-chain geometric ergodicity.Source: §A.1 · pp. 21–23

Theorem 3.12

• Hyper-small-set characterizations provide the route from π_ε-irreducibility to π_ε-a.e. total-variation geometric ergodicity for P_ε.Positive-measure sets contain hyper-small subsets on the countably generated state space, and convergence to such a set characterizes geometric ergodicity.Source: §A.2 · p. 23
• Theorem 3.12 establishes π_ε-a.e.-TV geometric ergodicity for P_ε with some factor ρTV ∈ (0, 1).The proof constructs a measure supported on a hyper-small set, shows it lies in L2(π), and applies the relevant convergence bounds.Source: §A.2 · pp. 23–24

Theorem 3.14

• Because P_ε is reversible and has an L1-geometric bound with factor at most 1 − (α − ε), it is also L2(π_ε)-geometrically ergodic with the same factor.The transfer uses the reversible-kernel relation between the L1 and L2 geometric-ergodicity statements.Source: §A.2 · p. 24

Corollary 3.15

• If ∥P − P_ε∥L2(π_ε) < ϕ, reversing the roles of P and P_ε yields the corresponding perturbation results.The proof also bounds the relevant one-step and stationary-distribution terms using Theorem 3.12 and Eq. (A.7).Source: §A.2 · pp. 24–25

A.3.1 Time-Averaging of Marginal Distributions

• The first time-averaging result follows from the triangle inequality and Theorem 3.4.This transfers the stationary-distribution and kernel-perturbation bounds into a bound for averaged marginals.Source: §A.3.1 · p. 25
• The remaining time-averaging results follow similarly from Theorems 3.12 and 3.14 and Corollary 3.15.Their derivations reuse the total-variation, L2(π_ε), and reverse-perturbation controls established earlier.Source: §A.3.1 · p. 25

Covariance Bounds

• Covariance bounds are developed through an isometric measure–function correspondence and the self-adjointness of reversible kernels.The restricted operator on centered L2 measures is identified with the adjoint of P, which equals P under reversibility.Source: §A.3.2 · pp. 25–26
• Corollary A.10 gives covariance bounds for stationary initialization and for the perturbed reversible chain with factor ρ2 = 1 − (α − ε).The perturbed-chain result uses its L2(π_ε) geometric ergodicity and reversibility.Source: §A.3.2 · pp. 25–26
• The covariance is symmetric, so the shifted and symmetrized bound holds for any f and g in the relevant function space.This extends the displayed covariance result beyond the initially ordered function pair.Source: §A.3.2 · p. 26
• The covariance expression for arbitrary initialization is decomposed into stationary-run integrals so Corollary A.10 can be applied.The proof bounds the resulting terms using operator norms, Cauchy–Schwarz, and the geometric-ergodicity estimates.Source: §A.3.2 · pp. 26–27
• Corollary A.13 sums the covariance bounds to control the variance component of mean-squared error for dependent sample means.The summation uses geometric series and applies to both original and perturbed chains under the stated assumptions.Source: §A.3.2 · pp. 29–30

• Theorem A.14 establishes the appendix’s mean-squared-error results under the assumptions of Section 3.2 for X0 ∼µ ∈L2(π).Source: §A.3.3 · p. 31
• The proofs partition MSE through bias-variance decomposition and cancel a variance expression against a bias term.The second bias term is bounded using Lemma A.5 and Theorem 3.16, while covariance bounds produce further exact cancellations.Source: §A.3.3 · pp. 31–33
• Alternative L2, L4, and essential-supremum norm bounds may be substituted when they make the theorem’s bounds more tractable.The norm inequalities apply directly when f is π-essentially bounded.Source: §A.3.3 · p. 31
• Compared with the L1 results of [18] for uniformly ergodic chains, the L2 and L1 bounds differ only by a time-independent factor depending on the initial distribution.For mean-squared error, the norm used in [18] is based on the midrange-centred infinity norm, which upper-bounds the norm here.Source: §A.3.3 · p. 31
• The combined bounds yield the first, third, second, and fourth results of the theorem.The derivation uses Corollaries A.12 and A.13 to control covariance and variance contributions.Source: §A.3.3 · pp. 31–33

• The transition-measure formulas for the exact and noisy Metropolis–Hastings kernels are obtained from fixed-point transitions and integration over an initial distribution.The noisy formulas involve the proposal q and noisy acceptance probability ˆa, with auxiliary-density factors integrated out.Source: B Proof of Theorem 4.1 · pp. 33–34
• Fubini’s theorem and related changes of integration order simplify the transition-measure differences used in the proof.The same Fubini argument is applied to both exact and approximating expressions.Source: B Proof of Theorem 4.1 · p. 34
• A uniformly bounded error ratio |r(y|x)| ≤R permits application of the preceding lemma under the theorem’s stated assumptions.Source: B Proof of Theorem 4.1 · p. 34
• For the countable-state example with aj = 2^-j-1, the stationary distribution satisfies π = a.The transition probabilities are defined on X = N ∪ {0}.Source: B Proof of Theorem 4.1 · p. 35
• For any initial probability mass function µ, the example establishes the stated convergence conclusions, including convergence rate α and an L2(π)-GE optimal-rate lower bound.Source: B Proof of Theorem 4.1 · pp. 35–36

• The optimal geometric-ergodicity rate ρ⋆ is defined as the infimum of rates admitting a ν-dependent finite constant for all n.Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 37
• The proof that ˆρ ≥ρ⋆ uses the eventual bound on |||µP^n −π||| and constructs a finite constant Cε(µ).Taking ε arbitrarily small yields the claimed comparison.Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 37
• Lemma 3.10 links geometric-ergodicity formulations through inclusion of L∞(π) in L2(π), Cauchy–Schwarz, and the cited equivalence theorem [30, Theorem 2.1].Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 37
• For reversible P, the L2 geometric-ergodicity rate ρ2 equals the spectral radius r(P|L2,0(π)).This characterization is attributed to [30, Theorem 2.1], while the almost-everywhere geometric-ergodicity result is attributed to Roberts and Tweedie [32, Theorem 1].Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 37
• The spectral-measure contradiction argument proves ρ2 ≤ρ by assuming ρ2 >ρ and deriving a contradiction from the spectral decomposition.The proof uses a nonzero signed measure in the spectral range and approximation by bounded mean-zero functions.Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 37
• The final comparison obtains ρ2 −2ε ≤ρ and, since ε is arbitrary, concludes ρ2 ≤ρ.Source: D Proof of Lemma 3.10 and Lemma 3.8 · p. 38