Thumbnail - No thumbnail

Mixing time and expansion of non-negatively curved Markov chains

Münch, Florentin; Salez, Justin (2023), Mixing time and expansion of non-negatively curved Markov chains, Journal de l'école Polytechnique. Mathématiques, 10, p. 575-590. 10.5802/jep.226

View/Open
Type
Article accepté pour publication ou publié
Date
2023
Journal name
Journal de l'école Polytechnique. Mathématiques
Volume
10
Pages
575-590
Publication identifier
Metadata
Show full item record
Author(s)
Münch, Florentin
Max Planck Institute for Mathematics [MPIM]
Salez, Justin
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (FR)
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.
Abstract (EN)
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 and 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.
Subjects / Keywords
Chaînes de Markov; marches aléatoires; expansion; courbure discrète; temps de mélange; phénomène de cutoff