Concentration of measure and mixing for Markov chains

Malwina Luczak

doi:10.46298/dmtcs.3558

Malwina Luczak - Concentration of measure and mixing for Markov chains

dmtcs:3558 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3558

Concentration of measure and mixing for Markov chainsConference paper

Authors: Malwina Luczak ¹

1 Department of Mathematics London School of Economics

We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution. We illustrate our results with applications to some known chains from computer science and statistical mechanics.

https://doi.org/10.46298/dmtcs.3558

Source: HAL:hal-01194679v1

Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science

Section: Proceedings

Published on: January 1, 2008

Imported on: May 10, 2017

Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] Markov chains, concentration of measure, rapid mixing

Bibliographic References

12 Documents citing this article

Matthew Jenssen;Will Perkins;Aditya Potukuchi;Michael Simkin, 2024, Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 151-165, 10.1109/focs61266.2024.00020.

Gesine Reinert;Nathan Ross, 2019, Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs, arXiv (Cornell University), 29, 5, 10.1214/19-aap1478, http://arxiv.org/abs/1712.05736.

Radosław Adamczak;Michał Kotowski;Bartłomiej Polaczyk;Michał Strzelecki, 2019, A note on concentration for polynomials in the Ising model, Electronic Journal of Probability, 24, none, 10.1214/19-ejp280, https://doi.org/10.1214/19-ejp280.

Graham Brightwell;Marianne Fairthorne;Malwina J. Luczak, 2018, The Supermarket Model with Bounded Queue Lengths in Equilibrium, Journal of Statistical Physics, 173, 3-4, pp. 1149-1194, 10.1007/s10955-018-2044-7, https://doi.org/10.1007/s10955-018-2044-7.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Statistical Mechanical Models and Glauber Dynamics, SpringerBriefs in probability and mathematical statistics, pp. 23-36, 10.1007/978-3-319-77019-2_2.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Aggregate Path Coupling: Higher Dimensional Theory, SpringerBriefs in probability and mathematical statistics, pp. 65-79, 10.1007/978-3-319-77019-2_6.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Aggregate Path Coupling: Beyond Kn, SpringerBriefs in probability and mathematical statistics, pp. 81-90, 10.1007/978-3-319-77019-2_7.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Large Deviations and Equilibrium Macrostate Phase Transitions, SpringerBriefs in probability and mathematical statistics, pp. 37-51, 10.1007/978-3-319-77019-2_3.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Aggregate Path Coupling: One-Dimensional Theory, SpringerBriefs in probability and mathematical statistics, pp. 55-64, 10.1007/978-3-319-77019-2_5.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Path Coupling for Curie-Weiss Model, SpringerBriefs in probability and mathematical statistics, pp. 53-54, 10.1007/978-3-319-77019-2_4.

Yevgeniy Kovchegov;Peter T. Otto, 2018, Coupling, Path Coupling, and Mixing Times, SpringerBriefs in probability and mathematical statistics, pp. 1-22, 10.1007/978-3-319-77019-2_1.

Yevgeniy Kovchegov;Peter T. Otto, 2015, Rapid Mixing of Glauber Dynamics of Gibbs Ensembles via Aggregate Path Coupling and Large Deviations Methods, arXiv (Cornell University), 161, 3, pp. 553-576, 10.1007/s10955-015-1345-3, http://arxiv.org/abs/1312.6728.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 363 times.

This article's PDF has been downloaded 1261 times.