Mixing time and expansion of non-negatively curved Markov chains
Journal de l’École polytechnique — Mathématiques, Volume 10 (2023), pp. 575-590.

We establish three remarkable consequences of non-negative curvature for sparse Markov chains. First, their conductance decreases logarithmically with the number of states. Second, their displacement is at least diffusive until the mixing time. Third, they never exhibit the cutoff phenomenon. The first result provides a nearly sharp quantitative answer to a classical question of Ollivier, Milman & Naor. The second settles a conjecture of Lee and Peres for graphs with non-negative curvature. The third offers a striking counterpoint to the recently established cutoff for non-negatively curved chains with uniform expansion.

Nous établissons trois conséquences remarquables de la courbure positive pour les chaînes de Markov. D’abord, la conductance de ces chaînes décroît logarithmiquement avec la taille de l’espace. Ensuite, leur déplacement est diffusif jusqu’au temps de mélange. Enfin, le phénomène de cutoff ne peut pas se produire. Le premier résultat fournit une réponse quantitative presqu’optimale à une question classique d’Ollivier, Milman et Naor. Le second confirme une conjecture de Lee et Peres, dans le cas particulier des graphes à courbure positive. Le troisième offre un contraste frappant avec les résultats positifs récents concernant le cutoff pour les chaînes de Markov ayant à la fois une courbure positive et une expansion uniforme.

Received:
Accepted:
Published online:
DOI: 10.5802/jep.226
Classification: 60J10
Keywords: Markov chains, random walks, expansion, discrete curvature, mixing times, cutoff phenomenon
Mot clés : Chaînes de Markov, marches aléatoires, expansion, courbure discrète, temps de mélange, phénomène de cutoff
Florentin Münch 1; Justin Salez 2

1 Max-Planck-Institut für Mathematik in den Naturwissenschaften Inselstr. 22, 04103 Leipzig, Germany
2 Université Paris-Dauphine & PSL, CEREMADE Place du Maréchal de Lattre de Tassigny, F-75775 Paris Cedex 16, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{JEP_2023__10__575_0,
     author = {Florentin M\"unch and Justin Salez},
     title = {Mixing time and expansion of non-negatively~curved {Markov} chains},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
     pages = {575--590},
     publisher = {\'Ecole polytechnique},
     volume = {10},
     year = {2023},
     doi = {10.5802/jep.226},
     language = {en},
     url = {https://jep.centre-mersenne.org/articles/10.5802/jep.226/}
}
TY  - JOUR
AU  - Florentin Münch
AU  - Justin Salez
TI  - Mixing time and expansion of non-negatively curved Markov chains
JO  - Journal de l’École polytechnique — Mathématiques
PY  - 2023
SP  - 575
EP  - 590
VL  - 10
PB  - École polytechnique
UR  - https://jep.centre-mersenne.org/articles/10.5802/jep.226/
DO  - 10.5802/jep.226
LA  - en
ID  - JEP_2023__10__575_0
ER  - 
%0 Journal Article
%A Florentin Münch
%A Justin Salez
%T Mixing time and expansion of non-negatively curved Markov chains
%J Journal de l’École polytechnique — Mathématiques
%D 2023
%P 575-590
%V 10
%I École polytechnique
%U https://jep.centre-mersenne.org/articles/10.5802/jep.226/
%R 10.5802/jep.226
%G en
%F JEP_2023__10__575_0
Florentin Münch; Justin Salez. Mixing time and expansion of non-negatively curved Markov chains. Journal de l’École polytechnique — Mathématiques, Volume 10 (2023), pp. 575-590. doi : 10.5802/jep.226. https://jep.centre-mersenne.org/articles/10.5802/jep.226/

[1] N. Alon & Y. Roichman - “Random Cayley graphs and expanders”, Random Structures Algorithms 5 (1994) no. 2, p. 271-284 | DOI | MR | Zbl

[2] F. Bauer, P. Horn, Y. Lin, G. Lippner, D. Mangoubi & S.-T. Yau - “Li-Yau inequality on graphs”, J. Differential Geom. 99 (2015) no. 3, p. 359-405 | MR | Zbl

[3] N. Berestycki & B. Şengül - “Cutoff for conjugacy-invariant random walks on the permutation group”, Probab. Theory Relat. Fields 173 (2019) no. 3-4, p. 1197-1241 | DOI | MR | Zbl

[4] M. Bordewich & M. Dyer - “Path coupling without contraction”, J. Discrete Algorithms 5 (2007) no. 2, p. 280-292 | DOI | MR | Zbl

[5] E. Breuillard & M. C. H. Tointon - “Nilprogressions and groups with moderate growth”, Adv. Math. 289 (2016), p. 1008-1055 | DOI | MR | Zbl

[6] P. Diaconis & L. Saloff-Coste - “Moderate growth and random walk on finite groups”, Geom. Funct. Anal. 4 (1994) no. 1, p. 1-36 | DOI | MR | Zbl

[7] M. Eidi & J. Jost - “Ollivier ricci curvature of directed hypergraphs”, Sci. Rep. 10 (2020) no. 1, article ID 12466, p. 1-14 | DOI

[8] M. Erbar & J. Maas - “Ricci curvature of finite Markov chains via convexity of the entropy”, Arch. Rational Mech. Anal. 206 (2012) no. 3, p. 997-1038 | DOI | MR | Zbl

[9] R. Forman - “Bochner’s method for cell complexes and combinatorial Ricci curvature”, Discrete Comput. Geom. 29 (2003) no. 3, p. 323-374 | DOI | MR | Zbl

[10] J. Jost - Riemannian geometry and geometric analysis, Universitext, Springer, Cham, 2017 | DOI

[11] J. Jost & F. Münch - “Characterizations of Forman curvature”, 2021 | arXiv

[12] J. R. Lee & Y. Peres - “Harmonic maps on amenable groups and a diffusive lower bound for random walks”, Ann. Probab. 41 (2013) no. 5, p. 3392-3419 | DOI | MR | Zbl

[13] D. A. Levin & Y. Peres - Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017 | DOI

[14] Y. Lin & S. Liu - “Equivalent properties of CD inequality on graph”, 2015 | arXiv

[15] Y. Lin & S.-T. Yau - “Ricci curvature and eigenvalue estimate on locally finite graphs”, Math. Res. Lett. 17 (2010) no. 2, p. 343-356 | DOI | MR | Zbl

[16] R. Montenegro & P. Tetali - “Mathematical aspects of mixing times in Markov chains”, Found. Trends Theor. Comput. Sci. 1 (2006) no. 3, p. x+121 | DOI | MR

[17] F. Münch - “Li-Yau inequality under CD(0,n) on graphs”, 2019 | arXiv

[18] F. Münch - “Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates”, 2019 | arXiv

[19] F. Münch & R. K. Wojciechowski - “Ollivier Ricci curvature for general graph Laplacians: Heat equation, Laplacian comparison, non-explosion and diameter bounds”, Adv. Math. 356 (2019), article ID 106759, 45 pages | DOI | MR | Zbl

[20] - Modern approaches to discrete curvature (L. Najman & P. Romon, eds.), Lect. Notes in Math., vol. 2184, Springer, Cham, 2017 | DOI | Zbl

[21] Y. Ollivier - “Ricci curvature of Markov chains on metric spaces”, J. Functional Analysis 256 (2009) no. 3, p. 810-864 | DOI | MR | Zbl

[22] Y. Ollivier - “A survey of Ricci curvature for metric spaces and Markov chains”, in Probabilistic approach to geometry, Adv. Stud. Pure Math., vol. 57, Math. Soc. Japan, Tokyo, 2010, p. 343-381 | DOI | MR | Zbl

[23] R. Ozawa, Y. Sakurai & T. Yamada - “Geometric and spectral properties of directed graphs under a lower Ricci curvature bound”, Calc. Var. Partial Differential Equations 59 (2020) no. 4, article ID 142, 39 pages | DOI | MR | Zbl

[24] R. Ozawa, Y. Sakurai & T. Yamada - “Heat flow and concentration of measure on directed graphs with a lower Ricci curvature bound”, Potential Anal. (2022), p. 1-15 | DOI

[25] J. Salez - “Cutoff for non-negatively curved Markov chains”, 2021 | arXiv

[26] J. Salez - “Sparse expanders have negative curvature”, Geom. Funct. Anal. 32 (2022) no. 6, p. 1486-1513 | DOI | MR | Zbl

[27] M. Schmuckenschläger - “Curvature of nonlocal Markov generators”, in Convex geometric analysis (Berkeley, CA, 1996), Math. Sci. Res. Inst. Publ., vol. 34, Cambridge Univ. Press, Cambridge, 1999, p. 189-197 | MR | Zbl

[28] R. Tessera & M. C. H. Tointon - “A finitary structure theorem for vertex-transitive graphs of polynomial growth”, Combinatorica 41 (2021) no. 2, p. 263-298 | DOI | MR | Zbl

[29] C. Villani - Optimal transport: old and new, Grundlehren Math. Wiss., vol. 338, Springer-Verlag, Berlin, 2009 | DOI

[30] T. Yamada - “The Ricci curvature on directed graphs”, 2016 | arXiv

Cited by Sources: