[Temps de mélange et expansion des chaînes de Markov en courbure positive]
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.
Accepté le :
Publié le :
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
CC-BY 4.0
@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/
[1] - “Random Cayley graphs and expanders”, Random Structures Algorithms 5 (1994) no. 2, p. 271-284 | DOI | MR | Zbl
[2] - “Li-Yau inequality on graphs”, J. Differential Geom. 99 (2015) no. 3, p. 359-405 | MR | Zbl
[3] - “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] - “Path coupling without contraction”, J. Discrete Algorithms 5 (2007) no. 2, p. 280-292 | DOI | MR | Zbl
[5] - “Nilprogressions and groups with moderate growth”, Adv. Math. 289 (2016), p. 1008-1055 | DOI | MR | Zbl
[6] - “Moderate growth and random walk on finite groups”, Geom. Funct. Anal. 4 (1994) no. 1, p. 1-36 | DOI | MR | Zbl
[7] - “Ollivier ricci curvature of directed hypergraphs”, Sci. Rep. 10 (2020) no. 1, article ID 12466, p. 1-14 | DOI
[8] - “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] - “Bochner’s method for cell complexes and combinatorial Ricci curvature”, Discrete Comput. Geom. 29 (2003) no. 3, p. 323-374 | DOI | MR | Zbl
[10] - Riemannian geometry and geometric analysis, Universitext, Springer, Cham, 2017 | DOI
[11] - “Characterizations of Forman curvature”, 2021 | arXiv
[12] - “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] - Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017 | DOI
[14] - “Equivalent properties of CD inequality on graph”, 2015 | arXiv
[15] - “Ricci curvature and eigenvalue estimate on locally finite graphs”, Math. Res. Lett. 17 (2010) no. 2, p. 343-356 | DOI | MR | Zbl
[16] - “Mathematical aspects of mixing times in Markov chains”, Found. Trends Theor. Comput. Sci. 1 (2006) no. 3, p. x+121 | DOI | MR
[17] - “Li-Yau inequality under on graphs”, 2019 | arXiv
[18] - “Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates”, 2019 | arXiv
[19] - “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] - “Ricci curvature of Markov chains on metric spaces”, J. Functional Analysis 256 (2009) no. 3, p. 810-864 | DOI | MR | Zbl
[22] - “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] - “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] - “Heat flow and concentration of measure on directed graphs with a lower Ricci curvature bound”, Potential Anal. (2022), p. 1-15 | DOI
[25] - “Cutoff for non-negatively curved Markov chains”, 2021 | arXiv
[26] - “Sparse expanders have negative curvature”, Geom. Funct. Anal. 32 (2022) no. 6, p. 1486-1513 | DOI | MR | Zbl
[27] - “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] - “A finitary structure theorem for vertex-transitive graphs of polynomial growth”, Combinatorica 41 (2021) no. 2, p. 263-298 | DOI | MR | Zbl
[29] - Optimal transport: old and new, Grundlehren Math. Wiss., vol. 338, Springer-Verlag, Berlin, 2009 | DOI
[30] - “The Ricci curvature on directed graphs”, 2016 | arXiv
Cité par Sources :