Mixing time and expansion of non-negatively curved Markov chains

Florentin Münch; Justin Salez

doi:10.5802/jep.226

Mixing time and expansion of non-negatively curved Markov chains
[Temps de mélange et expansion des chaînes de Markov en courbure positive]

Florentin Münch ¹ ; Justin Salez ²

¹ Max-Planck-Institut für Mathematik in den Naturwissenschaften Inselstr. 22, 04103 Leipzig, Germany
² Université Paris-Dauphine & PSL, CEREMADE Place du Maréchal de Lattre de Tassigny, F-75775 Paris Cedex 16, France

Journal de l’École polytechnique — Mathématiques, Tome 10 (2023), pp. 575-590.

Résumé
Abstract

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.

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.

Reçu le : 2022-09-07
Accepté le : 2023-03-20
Publié le : 2023-03-24

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

Affiliations des auteurs :

Florentin Münch ¹ ; Justin Salez ²

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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, Tome 10 (2023), pp. 575-590. doi : 10.5802/jep.226. https://jep.centre-mersenne.org/articles/10.5802/jep.226/

Bibliographie
Cité par

[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 $C D (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

Cité par Sources :