[Temps de mélange et expansion des chaînes de Markov en courbure positive]
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.
Accepté le :
Publié le :
Keywords: Markov chains, random walks, expansion, discrete curvature, mixing times, cutoff phenomenon
Mots-clés : Chaînes de Markov, marches aléatoires, expansion, courbure discrète, temps de mélange, phénomène de cutoff
Münch, Florentin 1 ; Salez, Justin 2
CC-BY 4.0
@article{JEP_2023__10__575_0,
author = {M\"unch, Florentin and Salez, Justin},
title = {Mixing time and expansion of non-negatively~curved {Markov} chains},
journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
pages = {575--590},
year = {2023},
publisher = {Ecole polytechnique},
volume = {10},
doi = {10.5802/jep.226},
language = {en},
url = {https://www.numdam.org/articles/10.5802/jep.226/}
}
TY - JOUR AU - Münch, Florentin AU - Salez, Justin 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 - Ecole polytechnique UR - https://www.numdam.org/articles/10.5802/jep.226/ DO - 10.5802/jep.226 LA - en ID - JEP_2023__10__575_0 ER -
%0 Journal Article %A Münch, Florentin %A Salez, Justin %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 Ecole polytechnique %U https://www.numdam.org/articles/10.5802/jep.226/ %R 10.5802/jep.226 %G en %F JEP_2023__10__575_0
Münch, Florentin; Salez, Justin. 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
[1] Random Cayley graphs and expanders, Random Structures Algorithms, Volume 5 (1994) no. 2, pp. 271-284 | DOI | MR | Zbl
[2] Li-Yau inequality on graphs, J. Differential Geom., Volume 99 (2015) no. 3, pp. 359-405 http://projecteuclid.org/euclid.jdg/1424880980 | Zbl | MR
[3] Cutoff for conjugacy-invariant random walks on the permutation group, Probab. Theory Relat. Fields, Volume 173 (2019) no. 3-4, pp. 1197-1241 | DOI | Zbl | MR
[4] Path coupling without contraction, J. Discrete Algorithms, Volume 5 (2007) no. 2, pp. 280-292 | Zbl | MR | DOI
[5] Nilprogressions and groups with moderate growth, Adv. Math., Volume 289 (2016), pp. 1008-1055 | MR | Zbl | DOI
[6] Moderate growth and random walk on finite groups, Geom. Funct. Anal., Volume 4 (1994) no. 1, pp. 1-36 | Zbl | MR | DOI
[7] Ollivier ricci curvature of directed hypergraphs, Sci. Rep., Volume 10 (2020) no. 1, 12466, pp. 1-14 | DOI
[8] Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Rational Mech. Anal., Volume 206 (2012) no. 3, pp. 997-1038 | Zbl | MR | DOI
[9] Bochner’s method for cell complexes and combinatorial Ricci curvature, Discrete Comput. Geom., Volume 29 (2003) no. 3, pp. 323-374 | Zbl | MR | DOI
[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., Volume 41 (2013) no. 5, pp. 3392-3419 | MR | Zbl | DOI
[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., Volume 17 (2010) no. 2, pp. 343-356 | Zbl | MR | DOI
[16] Mathematical aspects of mixing times in Markov chains, Found. Trends Theor. Comput. Sci., Volume 1 (2006) no. 3, p. x+121 | MR | DOI
[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., Volume 356 (2019), 106759, 45 pages | Zbl | MR | DOI
[20] Modern approaches to discrete curvature (Najman, Laurent; Romon, Pascal, eds.), Lect. Notes in Math., 2184, Springer, Cham, 2017 | Zbl | DOI
[21] Ricci curvature of Markov chains on metric spaces, J. Functional Analysis, Volume 256 (2009) no. 3, pp. 810-864 | Zbl | MR | DOI
[22] A survey of Ricci curvature for metric spaces and Markov chains, Probabilistic approach to geometry (Adv. Stud. Pure Math.), Volume 57, Math. Soc. Japan, Tokyo, 2010, pp. 343-381 | MR | Zbl | DOI
[23] Geometric and spectral properties of directed graphs under a lower Ricci curvature bound, Calc. Var. Partial Differential Equations, Volume 59 (2020) no. 4, 142, 39 pages | Zbl | MR | DOI
[24] Heat flow and concentration of measure on directed graphs with a lower Ricci curvature bound, Potential Anal. (2022), pp. 1-15 | DOI
[25] Cutoff for non-negatively curved Markov chains, 2021 | arXiv
[26] Sparse expanders have negative curvature, Geom. Funct. Anal., Volume 32 (2022) no. 6, pp. 1486-1513 | Zbl | MR | DOI
[27] Curvature of nonlocal Markov generators, Convex geometric analysis (Berkeley, CA, 1996) (Math. Sci. Res. Inst. Publ.), Volume 34, Cambridge Univ. Press, Cambridge, 1999, pp. 189-197 | Zbl | MR
[28] A finitary structure theorem for vertex-transitive graphs of polynomial growth, Combinatorica, Volume 41 (2021) no. 2, pp. 263-298 | Zbl | MR | DOI
[29] Optimal transport: old and new, Grundlehren Math. Wiss., 338, Springer-Verlag, Berlin, 2009 | DOI
[30] The Ricci curvature on directed graphs, 2016 | arXiv
Cité par Sources :
