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
2023Journal name
Journal de l'école Polytechnique. MathématiquesVolume
10Pages
575-590
Publication identifier
Metadata
Show full item recordAuthor(s)
Münch, FlorentinMax 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 cutoffRelated items
Showing items related by title and author.
-
Salez, Justin (2021) Document de travail / Working paper
-
Reversible jump, birth-and-death and more general continuous time Markov chain Monte Carlo samplers Cappé, Olivier; Robert, Christian P.; Ryden, Tobias (2003) Article accepté pour publication ou publié
-
Moulines, Eric; Guillin, Arnaud; Douc, Randal (2008) Article accepté pour publication ou publié
-
Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Persiano, Giuseppe (2013) Article accepté pour publication ou publié
-
Salez, Justin; Tikhomirov, Konstantin; Youssef, Pierre (2023) Article accepté pour publication ou publié