Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Concentration of mea ...
Conference paper

Concentration of measure and mixing for Markov chains

Malwina Luczak (1)
(1) Department of Mathematics London School of Economics
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Proceedings
DOI
10.46298/dmtcs.3558
License
https://about.hal.science/hal-authorisation-v1
Indicators
559
Views
1605
Downloads

Concentration of measure and mixing for Markov chains

Malwina Luczak (1)
(1) Department of Mathematics London School of Economics
Abstract
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.
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]
  • Markov chains
  • concentration of measure
  • rapid mixing
Cited by

Source: OpenCitations

  • A note on concentration for polynomials in the Ising model

    Electronic Journal of Probability

    Authors : Radosław Adamczak, Michał Kotowski, Bartłomiej Polaczyk, Michał Strzelecki

    Journal reference : Volume 24, 2019, pp.

    DOI : 10.1214/19-ejp280
  • Coupling, Path Coupling, and Mixing Times

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 1-22

    DOI : 10.1007/978-3-319-77019-2_1
  • Statistical Mechanical Models and Glauber Dynamics

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 23-36

    DOI : 10.1007/978-3-319-77019-2_2
  • Concentration inequalities for polynomials of contracting Ising models

    Electronic Communications in Probability

    Authors : Reza Gheissari ORCID, Eyal Lubetzky ORCID, Yuval Peres ORCID

    Journal reference : Volume 23, 2018, pp.

    DOI : 10.1214/18-ecp173
  • Aggregate Path Coupling: One-Dimensional Theory

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 55-64

    DOI : 10.1007/978-3-319-77019-2_5
  • Aggregate Path Coupling: Higher Dimensional Theory

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 65-79

    DOI : 10.1007/978-3-319-77019-2_6
  • Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)

    Authors : Matthew Jenssen ORCID, Will Perkins ORCID, Aditya Potukuchi, Michael Simkin

    Journal reference : Volume , 2024, pp. 151-165

    DOI : 10.1109/focs61266.2024.00020
  • The Supermarket Model with Bounded Queue Lengths in Equilibrium

    Journal of Statistical Physics

    Authors : Graham Brightwell ORCID, Marianne Fairthorne, Malwina J. Luczak ORCID

    Journal reference : Volume 173, 2018, pp. 1149-1194

    DOI : 10.1007/s10955-018-2044-7
  • Rapid Mixing of Glauber Dynamics of Gibbs Ensembles via Aggregate Path Coupling and Large Deviations Methods

    arXiv (Cornell University)

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume 161, 2015, pp. 553-576

    DOI : 10.1007/s10955-015-1345-3
  • Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs

    The Annals of Applied Probability

    Authors : Gesine Reinert ORCID, Nathan Ross ORCID

    Journal reference : Volume 29, 2019, pp.

    DOI : 10.1214/19-aap1478
  • Aggregate Path Coupling: Beyond Kn

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 81-90

    DOI : 10.1007/978-3-319-77019-2_7
  • Path Coupling for Curie-Weiss Model

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 53-54

    DOI : 10.1007/978-3-319-77019-2_4
  • Large Deviations and Equilibrium Macrostate Phase Transitions

    SpringerBriefs in probability and mathematical statistics

    Authors : Yevgeniy Kovchegov ORCID, Peter T. Otto ORCID

    Journal reference : Volume , 2018, pp. 37-51

    DOI : 10.1007/978-3-319-77019-2_3
Preview
Loading PDF preview...