Metraipolis › archive › dc_9902e563ed75
Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains — arXiv:2610.01121
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.01121
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T15:52:23.161Z
- SHA-256 of the archived text
a0df673337e0ed8985f4a71fbfc3eb196af8a2d08619b00c9ca20fa4a9deafea- Stable URL of this page
https://metraipolis.com/documento/dc_9902e563ed75
How to cite
Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains — arXiv:2610.01121 — arXiv (en), https://arxiv.org/abs/2610.01121 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9902e563ed75 (Metraipolis archive dc_9902e563ed75, sha256 a0df673337e0ed8985f4a71fbfc3eb196af8a2d08619b00c9ca20fa4a9deafea)
BibTeX
@misc{dc9902e563ed75,
title = {Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains — arXiv:2610.01121},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.01121},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9902e563ed75; sha256 a0df673337e0ed8985f4a71fbfc3eb196af8a2d08619b00c9ca20fa4a9deafea},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01121. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 \lambda_0<1$ for $j=1,\ldots,d$, then the cost of random scan is at most $2/(1-\lambda_0)$ times that of deterministic scan, while the reverse cost ratio is of order at most $d^2/(1-\lambda_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-\lambda_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.
Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-10-02 in stat.CO).
Categorie arXiv: Statistics Theory (math.ST) ; Computation (stat.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.01121 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:14:21.433Z dalla pagina https://arxiv.org/catchup/stat.CO/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).