Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains
Youngwoo Kwon
math.ST
Oct 1, 2026 · v1
stat.CO
TL;DR
Generative AI assisted in formally verifying the paper's spectral-gap comparison results in Lean; the provided text gives no further detail on the Lean artifact.
Abstract
Gibbs samplers, and more generally component-wise Markov chain Monte Carlo algorithms such as Metropolis-within-Gibbs, can be implemented using either random-scan or deterministic-scan updates. How much convergence can depend on this choice of scanning rule has been a longstanding question. We study this problem through $L^2$ spectral gaps, measuring computational cost in units of component updates. For a $d$-block Gibbs sampler, the cost of random scan is at most twice that of any fixed deterministic scan, while the reverse cost ratio is at most of order $d^2$. We extend these comparisons to general reversible component-wise updates under the global block-wise contraction condition. If $K_j$ denotes the update of block $j$ and $P_j$ its Gibbs counterpart, and $\|K_j-P_j\|\leq λ_0<1$ for $j=1,\ldots,d$, then the cost of random scan is at most $2/(1-λ_0)$ times that of deterministic scan, while the reverse cost ratio is of order at most $d^2/(1-λ_0)$. Examples show that the cost bounds for random scan relative to deterministic scan are asymptotically sharp and that the joint dependence on $d$ and $(1-λ_0)^{-1}$ in the reverse comparison cannot be improved uniformly. This work was assisted by generative AI, including for formal verification of mathematical results in Lean. The human author reviewed and verified the mathematical content and takes full responsibility for the results.
Problem
Component-wise MCMC algorithms such as Gibbs samplers and Metropolis-within-Gibbs can use random-scan or deterministic-scan updates. How much convergence, measured by the L^2 spectral gap per component update, depends on this choice has been a longstanding question.
Approach
Costs are compared through L^2(Π) norm spectral gaps, measured in units of component updates. The analysis uses self-adjointness, spectral decompositions of the local updates, and telescoping squared-norm losses along a sweep. Gibbs results are extended to general reversible updates under a global block-wise contraction condition ||K_j − P_j|| ≤ λ0 < 1. The abstract states that the mathematical results were formally verified in Lean with generative-AI assistance.
Results
For d-block Gibbs samplers, random scan costs at most twice as much as any fixed deterministic scan, while the reverse ratio is O(d^2). For general updates the bounds become 2/(1−λ0) and O(d^2/(1−λ0)). Gaussian overrelaxation and Metropolis pyramid examples show the first bound is asymptotically sharp and the joint parameter dependence in the reverse bound cannot be improved uniformly.
