Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains
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 L2 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 d2. We extend these comparisons to general reversible component-wise updates under the global block-wise contraction condition. If Kj denotes the update of block j and Pj its Gibbs counterpart, and |Kj−Pj|≤ λ0<1 for j=1,…,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 d2/(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.
Related
BibTeX
@misc{kwon2026cost,
title = {{Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains}},
author = {Youngwoo Kwon},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01121},
eprint = {2610.01121},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01121},
}
RIS
TY - UNPB
TI - Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains
AU - Youngwoo Kwon
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01121
UR - https://arxiv.org/abs/2610.01121
AB - 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|≤ λ_0<1 for j=1,…,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.
ER -