The varentropy criterion is sharp on expanders
[Optimalité du critère varentropique sur les expanseurs]
Salez, Justin1
1Université Paris-Dauphine – CEREMADE, Place du Maréchal de Lattre de Tassigny, F-75775 Paris Cedex 16 (France)
Annales Henri Lebesgue, Tome 7 (2024), pp. 239-250

The cutoff phenomenon is an abrupt transition from out of equilibrium to equilibrium undergone by certain Markov processes in the limit where the size of the state space tends to infinity: instead of decaying gradually over time, their distance to equilibrium remains close to the maximal value for a while and suddenly drops to zero as the time parameter reaches a critical threshold. Despite the accumulation of many examples, this phenomenon is still far from being understood, and identifying the general conditions that trigger it has become one of the biggest challenges in the quantitative analysis of finite Markov chains. Very recently, the author proposed a general sufficient condition for the occurrence of a cutoff, based on a certain information-theoretical statistics called varentropy. In the present paper, we demonstrate the sharpness of this approach by showing that the cutoff phenomenon is actually equivalent to the varentropy criterion for all sparse, fast-mixing chains. Reversibility is not required.

Le cutoff désigne une transition abrupte dans la convergence à l’équilibre de certains processus de Markov, dans la limite où le nombre d’états tend vers l’infini  : au lieu de décroître graduellement au cours du temps, la distance à l’équilibre reste longtemps proche de sa valeur initiale, puis chute brutalement à zéro lorsque le paramètre temporel atteint un seuil critique. Malgré l’accumulation de nombreux exemples, ce phénomène est toujours largement incompris, et l’identification des mécanismes généraux qui le sous-tendent constitue l’un des défis majeurs dans l’analyse quantitative des chaînes de Markov. Récemment, l’auteur a proposé une condition suffisante générale pour le cutoff, basée sur une quantité informationelle appelée varentropie. Dans cet article, nous démontrons l’optimalité de ce critère en montrant qu’il est en réalité équivalent au cutoff pour toutes les chaînes rapides et parcimonieuses. La réversibilité en temps n’est pas requise.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/ahl.199
Classification : 60J27
Keywords: Cutoff phenomenon, varentropy, expanders

Salez, Justin  1

1 Université Paris-Dauphine – 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{AHL_2024__7__239_0,
     author = {Salez, Justin},
     title = {The varentropy criterion is sharp on expanders},
     journal = {Annales Henri Lebesgue},
     pages = {239--250},
     year = {2024},
     publisher = {\'ENS Rennes},
     volume = {7},
     doi = {10.5802/ahl.199},
     mrnumber = {4765357},
     zbl = {1544.60080},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ahl.199/}
}
TY  - JOUR
AU  - Salez, Justin
TI  - The varentropy criterion is sharp on expanders
JO  - Annales Henri Lebesgue
PY  - 2024
SP  - 239
EP  - 250
VL  - 7
PB  - ÉNS Rennes
UR  - https://www.numdam.org/articles/10.5802/ahl.199/
DO  - 10.5802/ahl.199
LA  - en
ID  - AHL_2024__7__239_0
ER  - 
%0 Journal Article
%A Salez, Justin
%T The varentropy criterion is sharp on expanders
%J Annales Henri Lebesgue
%D 2024
%P 239-250
%V 7
%I ÉNS Rennes
%U https://www.numdam.org/articles/10.5802/ahl.199/
%R 10.5802/ahl.199
%G en
%F AHL_2024__7__239_0
Salez, Justin. The varentropy criterion is sharp on expanders. Annales Henri Lebesgue, Tome 7 (2024), pp. 239-250. doi: 10.5802/ahl.199

[AD86] Aldous, David; Diaconis, Persi Shuffling cards and stopping times, Am. Math. Mon., Volume 93 (1986), pp. 333-348 | MR | DOI | Zbl

[Ald83] Aldous, David Random walks on finite groups and rapidly mixing Markov chains, Seminar on probability, XVII (Lecture Notes in Mathematics), Volume 986, Springer, 1983, pp. 243-297 | Numdam | MR | Zbl

[Ald89] Aldous, David Hitting times for random walks on vertex-transitive graphs, Math. Proc. Camb. Philos. Soc., Volume 106 (1989) no. 1, pp. 179-191 | DOI | MR | Zbl

[BCS18] Bordenave, Charles; Caputo, Pietro; Salez, Justin Random walk on sparse random digraphs, Probab. Theory Relat. Fields, Volume 170 (2018) no. 3-4, pp. 933-960 | DOI | MR | Zbl

[BCS19] Bordenave, Charles; Caputo, Pietro; Salez, Justin Cutoff at the “entropic time” for sparse Markov chains, Probab. Theory Relat. Fields, Volume 173 (2019) no. 1-2, pp. 261-292 | DOI | MR | Zbl

[BH20] Ben-Hamou, Anna A threshold for cutoff in two-community random graphs, Ann. Appl. Probab., Volume 30 (2020) no. 4, pp. 1824-1846 | DOI | MR | Zbl

[BHS17] Ben-Hamou, Anna; Salez, Justin Cutoff for nonbacktracking random walks on sparse random graphs, Ann. Probab., Volume 45 (2017) no. 3, pp. 1752-1770 | DOI | MR | Zbl

[BL22] Bordenave, Charles; Lacoin, Hubert Cutoff at the entropic time for random walks on covered expander graphs, J. Inst. Math. Jussieu, Volume 21 (2022) no. 5, pp. 1571-1616 | DOI | MR | Zbl

[BLPS18] Berestycki, Nathanaël; Lubetzky, Eyal; Peres, Yuval; Sly, Allan Random walks on the random graph, Ann. Probab., Volume 46 (2018) no. 1, pp. 456-490 | DOI | MR | Zbl

[BT06] Bobkov, Sergey G.; Tetali, Prasad Modified logarithmic Sobolev inequalities in discrete settings, J. Theor. Probab., Volume 19 (2006) no. 2, pp. 289-336 | DOI | MR | Zbl

[Dia96] Diaconis, Persi The cutoff phenomenon in finite Markov chains, Proc. Natl. Acad. Sci. USA, Volume 93 (1996) no. 4, pp. 1659-1664 | DOI | MR | Zbl

[DS81] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 57 (1981) no. 2, pp. 159-179 | DOI | MR | Zbl

[DSC96] Diaconis, Persi; Saloff-Coste, Laurent Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., Volume 6 (1996) no. 3, pp. 695-750 | DOI | MR | Zbl

[Her17] Hermon, Jonathan Cutoff for Ramanujan graphs via degree inflation, Electron. Commun. Probab., Volume 22 (2017), 45 | DOI | MR | Zbl

[HLW06] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi Expander graphs and their applications, Bull. Am. Math. Soc., Volume 43 (2006) no. 4, pp. 439-561 | DOI | MR | Zbl

[HSS22b] Hermon, Jonathan; Sly, Allan; Sousi, Perla Universality of cutoff for graphs with an added random matching, Ann. Probab., Volume 50 (2022) no. 1, pp. 203-240 | DOI | MR | Zbl

[HŠS22a] Hermon, Jonathan; Šarković, Anđela; Sousi, Perla Cutoff for random walk on random graphs with a community structure (2022) | arXiv | DOI

[KV13] Kontoyiannis, Ioannis; Verdu, Sergio Optimal lossless compression: Source varentropy and dispersion, 2013 IEEE International Symposium on Information Theory (IEEE International Symposium on Information Theory - Proceedings), IEEE (2013), pp. 1739-1743 | DOI

[LP16] Lubetzky, Eyal; Peres, Yuval Cutoff on all Ramanujan graphs, Geom. Funct. Anal., Volume 26 (2016) no. 4, pp. 1190-1216 | DOI | MR | Zbl

[LP17] Levin, David A.; Peres, Yuval Markov chains and mixing times, American Mathematical Society, 2017 (Second edition of [ MR2466937], with contributions by Elizabeth L. Wilmer, with a chapter on “Coupling from the past” by James G. Propp and David B. Wilson) | Zbl | DOI | MR

[LS10] Lubetzky, Eyal; Sly, Allan Cutoff phenomena for random walks on random regular graphs, Duke Math. J., Volume 153 (2010) no. 3, pp. 475-510 | MR | DOI | Zbl

[LS11] Lubetzky, Eyal; Sly, Allan Explicit expanders with cutoff phenomena, Electron. J. Probab., Volume 16 (2011), 15, pp. 419-435 | DOI | MR | Zbl

[MT06] Montenegro, Ravi; Tetali, Prasad Mathematical aspects of mixing times in Markov chains, Found. Trends Theor. Comput. Sci., Volume 1 (2006) no. 3 | MR | Zbl

[Oza20] Ozawa, Narutaka An entropic proof of cutoff on Ramanujan graphs, Electron. Commun. Probab., Volume 25 (2020), 77 | MR | Zbl | DOI

[Per04] Peres, Yuval AIM Research Workshop on Sharp Thresholds for Mixing Times, 2004 http://www.aimath.org/wwn/mixingtimes.html

[Sal21] Salez, Justin Cutoff for non-negatively curved Markov chains (2021) (to appear in J. Eur. Math. Soc.) | arXiv | DOI

[TT20] Tessera, Romain; Tointon, Matthew C. H. Sharp relations between volume growth, isoperimetry and resistance in vertex-transitive graphs (2020) | arXiv | DOI

[TT21] Tessera, Romain; Tointon, Matthew C. H. A finitary structure theorem for vertex-transitive graphs of polynomial growth, Combinatorica, Volume 41 (2021) no. 2, pp. 263-298 | MR | DOI | Zbl

Cité par Sources :