Second-order perturbation bounds for Gibbs samplers under strong spatial mixing
Abstract
The basic question in perturbation analysis of Markov chains is how small changes in their transition kernels affect their stationary distributions. Classical perturbation bounds typically require the kernel error to be much smaller than 1/τ, where τ is a mixing or relaxation time. Although this scaling is sharp for Markov chains in general, we investigate a general "square-rooting" phenomenon in which one-step errors of order roughly 1/√τ can be sufficient for local updates. We proved a form of this phenomenon in Lin, Liu and Smith (2025) under strong assumptions. Here we substantially weaken these assumptions, and prove this phenomenon occurs using three distinct approaches. First, block factorization applies under structural assumptions on the stationary measures of both chains. Second, approximate block-update arguments extend the result to statistically relevant Markov chain Monte Carlo (MCMC) settings, where structural guarantees are available for the exact posterior and its associated sampler, but not for the perturbed posterior. Third, we use direct calculations for a class of models with hard constraints where neither general result is directly available. We illustrate these results in three MCMC settings and show how they directly inform the tuning of approximate MCMC algorithms.
Related
- Rényi mixing bounds for kinetic samplers via L2 hypocoercivity
- M-Eigenpairs of Partially Symmetric Tensors: Exact Reformulation and Perturbation Bounds
- A low-rank decoder bottleneck bounds reliability in foundation-model perturbation prediction
- Regional Stability and New Eigenvalue Perturbation Bounds
- The second type of power mean bounds for the hypergeometric mean
BibTeX
@misc{lin2026secondorder,
title = {{Second-order perturbation bounds for Gibbs samplers under strong spatial mixing}},
author = {Na Lin and Aaron Smith and Yiqiang Q. Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.13495},
eprint = {2609.13495},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13495},
}
RIS
TY - UNPB
TI - Second-order perturbation bounds for Gibbs samplers under strong spatial mixing
AU - Na Lin
AU - Aaron Smith
AU - Yiqiang Q. Zhao
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2609.13495
UR - https://arxiv.org/abs/2609.13495
AB - The basic question in perturbation analysis of Markov chains is how small changes in their transition kernels affect their stationary distributions. Classical perturbation bounds typically require the kernel error to be much smaller than 1/τ, where τ is a mixing or relaxation time. Although this scaling is sharp for Markov chains in general, we investigate a general "square-rooting" phenomenon in which one-step errors of order roughly 1/√τ can be sufficient for local updates. We proved a form of this phenomenon in Lin, Liu and Smith (2025) under strong assumptions. Here we substantially weaken these assumptions, and prove this phenomenon occurs using three distinct approaches. First, block factorization applies under structural assumptions on the stationary measures of both chains. Second, approximate block-update arguments extend the result to statistically relevant Markov chain Monte Carlo (MCMC) settings, where structural guarantees are available for the exact posterior and its associated sampler, but not for the perturbed posterior. Third, we use direct calculations for a class of models with hard constraints where neither general result is directly available. We illustrate these results in three MCMC settings and show how they directly inform the tuning of approximate MCMC algorithms.
ER -