2026-07-22T11:38:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13850 2024-03-06T10:52:52Z ddc:004 open_access

Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast Laddha, Aditi Vempala, Santosh S. Gibbs Sampler Coordinate Hit and run Mixing time of Markov Chain The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditi Laddha and Santosh S. Vempala 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.51 urn:nbn:de:0030-drops-138503 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.51 eng https://creativecommons.org/licenses/by/4.0/legalcode