Entropy and curvature: Beyond the Peres-Tetali conjecture

Caputo, Pietro; Münch, Florentin; Salez, Justin

doi:10.1090/tran/9395

Entropy and curvature: Beyond the Peres-Tetali conjecture
HTML articles powered by AMS MathViewer

by Pietro Caputo, Florentin Münch and Justin Salez;

Trans. Amer. Math. Soc. 378 (2025), 3551-3571

DOI: https://doi.org/10.1090/tran/9395

Published electronically: January 22, 2025

HTML | PDF | Request permission

Abstract:

We study Markov chains with non-negative sectional curvature on finite metric spaces. Neither reversibility, nor the restriction to a particular combinatorial distance is imposed. In this level of generality, we prove that a 1-step contraction in the Wasserstein distance implies a 1-step contraction in relative entropy, by the same amount. Our result substantially strengthens a recent breakthrough of the second author, and has the advantage of being applicable to arbitrary scales. This leads to a time-varying refinement of the standard Modified Log-Sobolev Inequality (MLSI), which allows us to leverage the well-acknowledged fact that curvature improves at large scales. We illustrate this principle with several applications, including birth and death chains, colored exclusion processes, permutation walks, Gibbs samplers for high-temperature spin systems, and attractive zero-range dynamics. In particular, we prove an MLSI with constant equal to the minimal rate increment for the mean-field zero-range process, thereby answering a long-standing question.

References

Gil Alon and Gady Kozma, Comparing with octopi, Ann. Inst. Henri Poincaré Probab. Stat. 56 (2020), no. 4, 2672–2685 (English, with English and French summaries). MR 4164852, DOI 10.1214/20-AIHP1054
Gil Alon, Gady Kozma, and Doron Puder, On the Aldous-Caputo spectral gap conjecture for hypergraphs, arXiv:2311.02505, 2023.
D. Bakry and Michel Émery, Diffusions hypercontractives, Séminaire de probabilités, XIX, 1983/84, Lecture Notes in Math., vol. 1123, Springer, Berlin, 1985, pp. 177–206 (French). MR 889476, DOI 10.1007/BFb0075847
Frank Bauer, Paul Horn, Yong Lin, Gabor Lippner, Dan Mangoubi, and Shing-Tung Yau, Li-Yau inequality on graphs, J. Differential Geom. 99 (2015), no. 3, 359–405. MR 3316971
Roland Bauerschmidt and Thierry Bodineau, A very simple proof of the LSI for high temperature spin systems, J. Funct. Anal. 276 (2019), no. 8, 2582–2588. MR 3926125, DOI 10.1016/j.jfa.2019.01.007
Nathanaël Berestycki and BatıŞengül, Cutoff for conjugacy-invariant random walks on the permutation group, Probab. Theory Related Fields 173 (2019), no. 3-4, 1197–1241. MR 3936154, DOI 10.1007/s00440-018-0844-y
Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda, On mixing of Markov chains: coupling, spectral independence, and entropy factorization, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022, pp. 3670–3692. MR 4415182, DOI 10.1137/1.9781611977073.145
Sergey Bobkov and Prasad Tetali, Modified log-Sobolev inequalities, mixing and hypercontractivity, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 287–296. MR 2120475, DOI 10.1145/780542.780586
Magnus Bordewich and Martin Dyer, Path coupling without contraction, J. Discrete Algorithms 5 (2007), no. 2, 280–292. MR 2316551, DOI 10.1016/j.jda.2006.04.001
Alexandre Bristiel and Pietro Caputo, Entropy inequalities for random walks and permutations, Ann. Inst. Henri Poincaré Probab. Stat. 60 (2024), no. 1, 54–81 (English, with English and French summaries). MR 4718374, DOI 10.1214/22-aihp1267
R. Bubley and M. Dyer, Path coupling: a technique for proving rapid mixing in Markov chains, Proceedings 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 223–231.
Pietro Caputo, Lecture notes on entropy and Markov chains, http://www.mat.uniroma3.it/users/caputo/entropy.pdf, 2022.
Pietro Caputo, Paolo Dai Pra, and Gustavo Posta, Convex entropy decay via the Bochner-Bakry-Emery approach, Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), no. 3, 734–753 (English, with English and French summaries). MR 2548501, DOI 10.1214/08-AIHP183
Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer, Proof of Aldous’ spectral gap conjecture, J. Amer. Math. Soc. 23 (2010), no. 3, 831–851. MR 2629990, DOI 10.1090/S0894-0347-10-00659-4
Pietro Caputo, Georg Menz, and Prasad Tetali, Approximate tensorization of entropy at high temperature, Ann. Fac. Sci. Toulouse Math. (6) 24 (2015), no. 4, 691–716 (English, with English and French summaries). MR 3434252, DOI 10.5802/afst.1460
Pietro Caputo and Gustavo Posta, Entropy dissipation estimates in a zero-range dynamics, Probab. Theory Related Fields 139 (2007), no. 1-2, 65–87. MR 2322692, DOI 10.1007/s00440-006-0039-9
Filippo Cesi, Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields, Probab. Theory Related Fields 120 (2001), no. 4, 569–584. MR 1853483, DOI 10.1007/PL00008792
Filippo Cesi, A few remarks on the octopus inequality and Aldous’ spectral gap conjecture, Comm. Algebra 44 (2016), no. 1, 279–302. MR 3413687, DOI 10.1080/00927872.2014.975349
Yuansi Chen and Ronen Eldan, Localization schemes: a framework for proving mixing bounds for Markov chains, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 110–122. MR 4537195
Giovanni Conforti, A probabilistic approach to convex ($\phi$)-entropy decay for Markov chains, Ann. Appl. Probab. 32 (2022), no. 2, 932–973. MR 4414692, DOI 10.1214/21-aap1700
Stephen B. Connor and Richard J. Pymar, Mixing times for exclusion processes on hypergraphs, Electron. J. Probab. 24 (2019), Paper No. 73, 48. MR 3978223, DOI 10.1214/19-EJP332
Karel Devriendt and Renaud Lambiotte, Discrete curvature on graphs from the effective resistance, Journal of Physics: Complexity, 3 (2022), no. 2, 025008.
Persi Diaconis, The Markov chain Monte Carlo revolution, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 2, 179–205. MR 2476411, DOI 10.1090/S0273-0979-08-01238-X
Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
A. B. Dieker, Interlacings for random walks on weighted graphs and the interchange process, SIAM J. Discrete Math. 24 (2010), no. 1, 191–206. MR 2600660, DOI 10.1137/090775361
Dominik Dier, Moritz Kassmann, and Rico Zacher, Discrete versions of the Li-Yau gradient estimate, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 22 (2021), no. 2, 691–744. MR 4288669
R. L. Dobrushin and S. B. Shlosman, Constructive criterion for the uniqueness of Gibbs field, Statistical physics and dynamical systems (Köszeg, 1984) Progr. Phys., vol. 10, Birkhäuser Boston, Boston, MA, 1985, pp. 347–370. MR 821306
Ronen Eldan, James R. Lee, and Joseph Lehec, Transport-entropy inequalities and curvature in discrete-space Markov chains, A journey through discrete mathematics, Springer, Cham, 2017, pp. 391–406. MR 3726607
K. D. Elworthy, Manifolds and graphs with mostly positive curvatures, Stochastic analysis and applications (Lisbon, 1989) Progr. Probab., vol. 26, Birkhäuser Boston, Boston, MA, 1991, pp. 96–110. MR 1168070
Matthias Erbar and Max Fathi, Poincaré, modified logarithmic Sobolev and isoperimetric inequalities for Markov chains with non-negative Ricci curvature, J. Funct. Anal. 274 (2018), no. 11, 3056–3089. MR 3782987, DOI 10.1016/j.jfa.2018.03.011
Matthias Erbar, Max Fathi, and André Schlichting, Entropic curvature and convergence to equilibrium for mean-field dynamics on discrete spaces, ALEA Lat. Am. J. Probab. Math. Stat. 17 (2020), no. 1, 445–471. MR 4105926, DOI 10.30757/alea.v17-18
Matthias Erbar, Christopher Henderson, Georg Menz, and Prasad Tetali, Ricci curvature bounds for weakly interacting Markov chains, Electron. J. Probab. 22 (2017), Paper No. 40, 23. MR 3646066, DOI 10.1214/17-EJP49
Matthias Erbar and Jan Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Ration. Mech. Anal. 206 (2012), no. 3, 997–1038. MR 2989449, DOI 10.1007/s00205-012-0554-z
Max Fathi and Jan Maas, Entropic Ricci curvature bounds for discrete interacting systems, Ann. Appl. Probab. 26 (2016), no. 3, 1774–1806. MR 3513606, DOI 10.1214/15-AAP1133
Robin Forman, Bochner’s method for cell complexes and combinatorial Ricci curvature, Discrete Comput. Geom. 29 (2003), no. 3, 323–374. MR 1961004, DOI 10.1007/s00454-002-0743-x
Fuqing Gao and Jeremy Quastel, Exponential decay of entropy in the random transposition and Bernoulli-Laplace models, Ann. Appl. Probab. 13 (2003), no. 4, 1591–1600. MR 2023890, DOI 10.1214/aoap/1069786512
Sharad Goel, Modified logarithmic Sobolev inequalities for some models of random walk, Stochastic Process. Appl. 114 (2004), no. 1, 51–79. MR 2094147, DOI 10.1016/j.spa.2004.06.001
W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57 (1970), no. 1, 97–109. MR 3363437, DOI 10.1093/biomet/57.1.97
Jonathan Hermon and Yuval Peres, A characterization of $L_2$ mixing and hypercontractivity via hitting times and maximal inequalities, Probab. Theory Related Fields 170 (2018), no. 3-4, 769–800. MR 3773799, DOI 10.1007/s00440-017-0769-x
Jonathan Hermon and Justin Salez, Entropy dissipation estimates for inhomogeneous zero-range processes, Ann. Appl. Probab. 31 (2021), no. 5, 2275–2283. MR 4332696, DOI 10.1214/20-aap1646
Jonathan Hermon and Justin Salez, The interchange process on high-dimensional products, Ann. Appl. Probab. 31 (2021), no. 1, 84–98. MR 4254474, DOI 10.1214/20-aap1583
Jürgen Jost and Florentin Münch, Characterizations of Forman curvature, arXiv:2110.04554, 2021.
Jürgen Jost, Florentin Münch, and Christian Rose, Liouville property and non-negative Ollivier curvature on graphs, arXiv:1903.10796, 2019.
Aldéric Joulin, Poisson-type deviation inequalities for curved continuous-time Markov chains, Bernoulli 13 (2007), no. 3, 782–798. MR 2348750, DOI 10.3150/07-BEJ6039
Aldéric Joulin and Yann Ollivier, Curvature, concentration and error estimates for Markov chain Monte Carlo, Ann. Probab. 38 (2010), no. 6, 2418–2442. MR 2683634, DOI 10.1214/10-AOP541
Mark Kempton, Gabor Lippner, and Florentin Münch, Large scale Ricci curvature on graphs, Calc. Var. Partial Differential Equations 59 (2020), no. 5, Paper No. 166, 17. MR 4149342, DOI 10.1007/s00526-020-01829-y
David A. Levin and Yuval Peres, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017. Second edition of [ MR2466937]; With contributions by Elizabeth L. Wilmer; With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. MR 3726904, DOI 10.1090/mbk/107
Yong Lin and Shing-Tung Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), no. 2, 343–356. MR 2644381, DOI 10.4310/MRL.2010.v17.n2.a13
Kuikui Liu, From coupling to spectral independence and blackbox comparison with the down-up walk, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, LIPIcs. Leibniz Int. Proc. Inform., vol. 207, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 32, 21. MR 4366587
Sheng Lin Lu and Horng-Tzer Yau, Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics, Comm. Math. Phys. 156 (1993), no. 2, 399–433. MR 1233852, DOI 10.1007/BF02098489
Fabio Martinelli, Lectures on Glauber dynamics for discrete spin models, Lectures on probability theory and statistics (Saint-Flour, 1997) Lecture Notes in Math., vol. 1717, Springer, Berlin, 1999, pp. 93–191. MR 1746301, DOI 10.1007/978-3-540-48115-7_{2}
Katalin Marton, Logarithmic Sobolev inequalities in discrete product spaces, Combin. Probab. Comput. 28 (2019), no. 6, 919–935. MR 4015662, DOI 10.1017/s0963548319000099
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller, Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21 (1953), no. 6, 1087–1092.
Florentin Münch, Li-Yau inequality on finite graphs via non-linear curvature dimension conditions, J. Math. Pures Appl. (9) 120 (2018), 130–164. MR 3906157, DOI 10.1016/j.matpur.2018.10.006
Florentin Münch, Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates, J. Math. Pures Appl. (9) 170 (2023), 231–257 (English, with English and French summaries). MR 4532964, DOI 10.1016/j.matpur.2022.12.007
Florentin Münch, Ollivier curvature, isoperimetry, concentration, and log-Sobolev inequalitiy, 2023.
Florentin Münch and Justin Salez, Mixing time and expansion of non-negatively curved Markov chains, J. Éc. polytech. Math. 10 (2023), 575–590 (English, with English and French summaries). MR 4567745, DOI 10.5802/jep.226
Florentin Münch, Melchior Wirth, and Haonan Zhang, Intertwining curvature bounds for graphs and quantum Markov semigroups, arXiv:2401.05179, 2024.
Roberto Imbuzeiro Oliveira, Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk, Ann. Probab. 41 (2013), no. 2, 871–913. MR 3077529, DOI 10.1214/11-AOP714
Yann Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal. 256 (2009), no. 3, 810–864. MR 2484937, DOI 10.1016/j.jfa.2008.11.001
Yann Ollivier, A survey of Ricci curvature for metric spaces and Markov chains, Probabilistic approach to geometry, Adv. Stud. Pure Math., vol. 57, Math. Soc. Japan, Tokyo, 2010, pp. 343–381. MR 2648269, DOI 10.2969/aspm/05710343
Francesco Pedrotti, Contractive coupling rates and curvature lower bounds for Markov chains, 2023.
Matteo Quattropani and Federico Sau, Mixing of the averaging process and its discrete dual on finite-dimensional geometries, Ann. Appl. Probab. 33 (2023), no. 2, 936–971. MR 4564423, DOI 10.1214/22-aap1838
Martin Rapaport and Paul-Marie Samson, Criteria for entropic curvature on graph spaces, arXiv:2303.15874, 2023.
Justin Salez, Sparse expanders have negative curvature, Geom. Funct. Anal. 32 (2022), no. 6, 1486–1513. MR 4536468, DOI 10.1007/s00039-022-00618-3
Justin Salez, Universality of cutoff for exclusion with reservoirs, Ann. Probab. 51 (2023), no. 2, 478–494. MR 4546624, DOI 10.1214/22-aop1600
Justin Salez, Cutoff for non-negatively curved Markov chains, J. Eur. Math. Soc. (JEMS) 26 (2024), no. 11, 4375–4392. MR 4780485, DOI 10.4171/jems/1348
Justin Salez, Spectral gap and curvature of monotone Markov chains, Ann. Probab. 52 (2024), no. 3, 1153–1161. MR 4736702, DOI 10.1214/24-aop1688
Michael Schmuckenschläger, Curvature of nonlocal Markov generators, Convex geometric analysis (Berkeley, CA, 1996), vol 34, 1998, pp. 189–197.
Frank Spitzer, Interaction of Markov processes, Advances in Math. 5 (1970), 246–290 (1970). MR 268959, DOI 10.1016/0001-8708(70)90034-4
Stefan Steinerberger, Curvature on graphs via equilibrium measures, J. Graph Theory 103 (2023), no. 3, 415–436. MR 4596504, DOI 10.1002/jgt.22925
Philip Tee and C. A. Trugenberger, Enhanced Forman curvature and its relation to Ollivier curvature, Europhysics Letters, 133 (2021), no. 6, 60006.
Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
Frederic Weber and Rico Zacher, The entropy method under curvature-dimension conditions in the spirit of Bakry-Émery in the discrete setting of Markov chains, J. Funct. Anal. 281 (2021), no. 5, Paper No. 109061, 81. MR 4253929, DOI 10.1016/j.jfa.2021.109061
Xi Xu, Wang Shen, and Linfeng Wang, The $\textrm {CD}_p$ curvature condition on a graph, Front. Math. 19 (2024), no. 1, 181–192. MR 4688313, DOI 10.1007/s11464-021-0488-6
Bogusław Zegarliński, Dobrushin uniqueness theorem and logarithmic Sobolev inequalities, J. Funct. Anal. 105 (1992), no. 1, 77–111. MR 1156671, DOI 10.1016/0022-1236(92)90073-R

AMS Website Down

Transactions of the American Mathematical Society

Entropy and curvature: Beyond the Peres-Tetali conjecture
HTML articles powered by AMS MathViewer

Abstract: