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 chains
Authors: Malwina Luczak 1
NULL
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.
Adamczak, Radosław; Kotowski, Michał; Polaczyk, Bartłomiej; Strzelecki, Michał, 2019, A Note On Concentration For Polynomials In The Ising Model, Electronic Journal Of Probability, 24, none, 10.1214/19-ejp280.
Brightwell, Graham; Fairthorne, Marianne; Luczak, Malwina, 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.
Gheissari, Reza; Lubetzky, Eyal; Peres, Yuval, 2018, Concentration Inequalities For Polynomials Of Contracting Ising Models, Electronic Communications In Probability, 23, none, 10.1214/18-ecp173.
Kovchegov, Yevgeniy; Otto, Peter T., 2015, Rapid Mixing Of Glauber Dynamics Of Gibbs Ensembles Via Aggregate Path Coupling And Large Deviations Methods, Journal Of Statistical Physics, 161, 3, pp. 553-576, 10.1007/s10955-015-1345-3.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Aggregate Path Coupling: Beyond Kn, Path Coupling And Aggregate Path Coupling, pp. 81-90, 10.1007/978-3-319-77019-2_7.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Aggregate Path Coupling: Higher Dimensional Theory, Path Coupling And Aggregate Path Coupling, pp. 65-79, 10.1007/978-3-319-77019-2_6.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Aggregate Path Coupling: One-Dimensional Theory, Path Coupling And Aggregate Path Coupling, pp. 55-64, 10.1007/978-3-319-77019-2_5.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Coupling, Path Coupling, And Mixing Times, Path Coupling And Aggregate Path Coupling, pp. 1-22, 10.1007/978-3-319-77019-2_1.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Large Deviations And Equilibrium Macrostate Phase Transitions, Path Coupling And Aggregate Path Coupling, pp. 37-51, 10.1007/978-3-319-77019-2_3.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Path Coupling For Curie-Weiss Model, Path Coupling And Aggregate Path Coupling, pp. 53-54, 10.1007/978-3-319-77019-2_4.
Kovchegov, Yevgeniy; Otto, Peter T., 2018, Statistical Mechanical Models And Glauber Dynamics, Path Coupling And Aggregate Path Coupling, pp. 23-36, 10.1007/978-3-319-77019-2_2.
Reinert, Gesine; Ross, Nathan, 2019, Approximating Stationary Distributions Of Fast Mixing Glauber Dynamics, With Applications To Exponential Random Graphs, The Annals Of Applied Probability, 29, 5, 10.1214/19-aap1478.