• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
2206.08294.pdf (383.7Kb)
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
10.5802/jep.226
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

Related items

Showing items related by title and author.

  • Thumbnail
    Cutoff for non-negatively curved Markov chains 
    Salez, Justin (2021) Document de travail / Working paper
  • Thumbnail
    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é
  • Thumbnail
    Bounds on Regeneration Times and Limit Theorems for Subgeometric Markov Chains 
    Moulines, Eric; Guillin, Arnaud; Douc, Randal (2008) Article accepté pour publication ou publié
  • Thumbnail
    Mixing Time and Stationary Expected Social Welfare of Logit Dynamics 
    Auletta, Vincenzo; Ferraioli, Diodato; Pasquale, Francesco; Persiano, Giuseppe (2013) Article accepté pour publication ou publié
  • Thumbnail
    Upgrading MLSI to LSI for reversible Markov chains 
    Salez, Justin; Tikhomirov, Konstantin; Youssef, Pierre (2023) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo