Geodesic
Mixing time and expansion of non-negatively curved Markov chains
[Temps de mélange et expansion des chaînes de Markov en courbure positive]
Münch, Florentin1 ; Salez, Justin2
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
Journal de l’École polytechnique — Mathématiques, Tome 10 (2023), pp. 575-590

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/jep.226
Classification : 60J10
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

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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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},
     publisher = {\'Ecole polytechnique},
     volume = {10},
     year = {2023},
     doi = {10.5802/jep.226},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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  - École polytechnique
UR  - http://geodesic.mathdoc.fr/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 École polytechnique
%U http://geodesic.mathdoc.fr/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

Cité par Sources :