pith. sign in

arxiv: 2401.03937 · v3 · submitted 2024-01-08 · 🧮 math.PR

Cutoff for mixtures of permuted Markov chains: reversible case

Bastien Dubail This is my paper

Pith reviewed 2026-05-24 04:10 UTC · model grok-4.3

classification 🧮 math.PR
keywords cutoffMarkov chain mixingrandom permutationentropy rateconcentration inequalitysymmetric groupreversible chainsrandom environment
0
0 comments X

The pith

Mixtures of permuted Markov chains exhibit cutoff at the entropic time log n/h with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that reversible Markov chains formed by mixing a deterministic chain with one whose vertices are randomly permuted display the cutoff phenomenon at time log n divided by the entropy rate h. This holds with high probability under mild assumptions on the base chains. A reader would care because this describes a sharp transition in how quickly the chain forgets its starting point in a random environment, generalizing known results for graphs with added random matchings. The argument uses a new concentration inequality for low-degree functions on the symmetric group.

Core claim

Under mild assumptions on the base Markov chains, the resulting mixture chain exhibits the cutoff phenomenon at entropic time log n/h with high probability, where h is a constant related to the entropy of the chain. The results are a consequence of work on a more general non-reversible model, and the proofs mostly do not require reversibility.

What carries the argument

A novel concentration result for low-degree functions on the symmetric group, used to control the random permutation's effect on mixing.

If this is right

  • The simple random walk on a graph with an added uniform random matching exhibits cutoff at entropic time.
  • The cutoff holds for superpositions of deterministic graphs with randomly permuted second graphs.
  • The mixing time is determined by the entropy rate of the chain.
  • Similar cutoff results are expected for non-reversible versions in a companion paper.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This low-degree concentration inequality on the symmetric group may apply to other problems involving random permutations of chain states.
  • Explicit computation of h for concrete chains would yield exact cutoff times for specific randomized models.
  • The approach could extend to studying cutoff in other disordered or random media Markov chains.

Load-bearing premise

The base Markov chains have a well-defined positive entropy rate and satisfy the conditions needed for the low-degree concentration inequality to bound the effect of the random permutation.

What would settle it

A concrete counterexample where the total variation distance fails to exhibit a sharp cutoff around time log n/h for base chains meeting the mild assumptions would disprove the result.

Figures

Figures reproduced from arXiv: 2401.03937 by Bastien Dubail.

Figure 1
Figure 1. Figure 1: Argument of the proof of Lemma 5.3 endpoints. If ι(η(x)) ∈ S1 there exists y ′ ∈ V such that P(ι(y), ι(y ′ )) > 0, as in [PITH_FULL_IMAGE:figures/full_fig_p039_1.png] view at source ↗
read the original abstract

We investigate the mixing properties of a model of reversible Markov chains in random environment, which notably contains the simple random walk on the superposition of a deterministic graph and a second graph whose vertex set has been permuted uniformly at random. It generalizes in particular a result of Hermon, Sly and Sousi, who proved the cutoff phenomenon at entropic time for the simple random walk on a graph with an added uniform matching. Under mild assumptions on the base Markov chains, we prove that with high probability the resulting chain exhibits the cutoff phenomenon at entropic time log n/h, h being some constant related to the entropy of the chain. We note that the results presented here are the consequence of a work conducted for a more general model that does not assume reversibility, which will be the object of a companion paper. Thus, most of our proofs do not actually require reversibility, which constitutes an important technical contribution. Finally, our argument relies on a novel concentration result for "low-degree" functions on the symmetric group, established specifically for our purpose but which could be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the mixing time of a reversible Markov chain formed as a mixture of two base chains, one of which is defined on a uniformly random permutation of the vertices of the second graph. Under mild assumptions ensuring a positive entropy rate h, the authors prove that the mixture exhibits cutoff at time (log n)/h with high probability. The argument relies on a new concentration inequality for low-degree functions on the symmetric group S_n; reversibility is used only in a few steps and the non-reversible case is deferred to a companion paper. The result generalizes the Hermon–Sly–Sousi theorem on graphs with an added uniform matching.

Significance. The central claim, if correct, extends cutoff results from specific random-graph models to a broader class of permuted mixtures while isolating the entropy calculation from the permutation analysis. The novel concentration bound for low-degree functions on S_n is presented as potentially of independent interest and is the main technical tool. The observation that reversibility is not essential for most of the argument is a useful technical clarification.

minor comments (3)
  1. §1.2: the statement of the mild assumptions on the base chains could be collected in a single numbered assumption block rather than scattered across the introduction and the entropy section.
  2. The dependence of the high-probability statement on the random permutation is stated in the abstract but the precise probability space (over the choice of permutation) should be recalled explicitly in the statement of the main theorem.
  3. Notation for the entropy rate h is introduced in the abstract and §2 but the precise definition (in terms of the transition probabilities of the base chains) appears only later; a forward reference would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report and recommendation of minor revision. The summary and significance assessment accurately capture the main results, including the cutoff at entropic time for reversible mixtures of permuted Markov chains, the generalization of the Hermon-Sly-Sousi theorem, and the novel concentration inequality for low-degree functions on S_n. We also appreciate the note that reversibility is used only in a few steps. No specific major comments are listed in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via new concentration inequality

full rationale

The paper defines the random-permutation mixture model explicitly, computes the entropy rate h from the base chains under stated assumptions, and applies a newly derived concentration bound on low-degree functions of S_n to establish the cutoff at (log n)/h w.h.p. No step reduces a claimed prediction to a fitted parameter or prior result by construction; the concentration inequality is introduced as original technical content (with potential independent interest) rather than imported via self-citation. The generalization of Hermon-Sly-Sousi is cited as motivation but the proof chain does not rely on it for the central claim. The companion-paper note is incidental and does not create a load-bearing loop. The derivation therefore stands on independent probabilistic arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard Markov chain theory (existence of stationary measures and entropy rates) and the uniform random permutation model. No free parameters are fitted to data; h is defined from the base chain entropy. No new entities are postulated.

axioms (1)
  • standard math Standard axioms of probability and Markov chain theory, including existence of stationary distributions and positive entropy rates under mild assumptions
    Invoked to define the entropic time log n / h and to apply concentration tools.

pith-pipeline@v0.9.0 · 5711 in / 1205 out tokens · 31108 ms · 2026-05-24T04:10:11.141719+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · 2 internal anchors

  1. [1]

    Random walks on finite groups and rapidly mixing markov chains

    David Aldous. Random walks on finite groups and rapidly mixing markov chains. pages 243– 297, 1983. URL: https://doi.org/10.1007%2Fbfb0068322, doi:10.1007/bfb0068322. 7

    work page doi:10.1007/bfb0068322 1983

  2. [2]

    Shuffling cards and stopping times.The American Math- ematical Monthly, 93(5):333–348, 1986

    David Aldous and Persi Diaconis. Shuffling cards and stopping times.The American Math- ematical Monthly, 93(5):333–348, 1986. URL:http://www.jstor.org/stable/2323590. 7

    work page arXiv 1986

  3. [3]

    Random walks on dynamic configuration models: A trichotomy.Stochastic Processes and their Applications, 129(9):3360–3375, sep 2019

    Luca Avena, Hakan Güldaş, Remco van der Hofstad, and Frank den Hollander. Random walks on dynamic configuration models: A trichotomy.Stochastic Processes and their Applications, 129(9):3360–3375, sep 2019. URL:https://doi.org/10.1016%2Fj.spa.2018.09.010, doi: 10.1016/j.spa.2018.09.010. 8

    work page doi:10.1016/j.spa.2018.09.010 2019

  4. [4]

    Phase transition for random walks on graphs with added weighted random matching

    Zsuzsanna Baran, Jonathan Hermon, Anđela Šarković, and Perla Sousi. Phase transition for random walks on graphs with added weighted random matching. 2023.arXiv:2306.13077. 7, 9

    work page arXiv 2023

  5. [5]

    A threshold for cutoff in two-community random graphs.The Annals of Applied Probability, 30(4):1824 – 1846, 2020.doi:10.1214/19-AAP1544

    Anna Ben-Hamou. A threshold for cutoff in two-community random graphs.The Annals of Applied Probability, 30(4):1824 – 1846, 2020.doi:10.1214/19-AAP1544. 7

    work page doi:10.1214/19-aap1544 2020

  6. [6]

    Comparing mixing times on sparse random graphs.Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55(2):1116 – 1130, 2019.doi:10.1214/18-AIHP911

    Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Comparing mixing times on sparse random graphs.Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55(2):1116 – 1130, 2019.doi:10.1214/18-AIHP911. 7

    work page doi:10.1214/18-aihp911 2019

  7. [7]

    Cutoff for permuted Markov chains

    Anna Ben-Hamou and Yuval Peres. Cutoff for permuted Markov chains. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 59(1):230 – 243, 2023.doi:10.1214/ 22-AIHP1248. 7, 8

    work page 2023

  8. [8]

    Cutoff for nonbacktracking random walks on sparse random graphs

    Anna Ben-Hamou and Justin Salez. Cutoff for nonbacktracking random walks on sparse random graphs. The Annals of Probability, 45(3):1752–1770, 2017. 3, 4, 7, 9, 10, 50

    work page 2017

  9. [9]

    The mixing time of the gi- ant component of a random graph

    Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of the gi- ant component of a random graph. Random Structures & Algorithms , 45(3):383– 407, 2014. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20539, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20539, doi:https:// doi.org/10.1002/rsa.20539. 4, 7

    work page doi:10.1002/rsa.20539 2014

  10. [10]

    Random walks on the ran- dom graph.The Annals of Probability, 46(1):456–490, 2018.doi:doi:10.1214/17-AOP1189

    Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, and Allan Sly. Random walks on the ran- dom graph.The Annals of Probability, 46(1):456–490, 2018.doi:doi:10.1214/17-AOP1189. 4, 7, 25

    work page doi:10.1214/17-aop1189 2018

  11. [11]

    Bolthausen

    E. Bolthausen. An estimate of the remainder in a combinatorial central limit theorem.Prob- ability Theory and Related Fields, 66(3):379–386, 1984.doi:10.1007/BF00533704. 8 69

    work page doi:10.1007/bf00533704 1984

  12. [12]

    The rate of convergence for multivariate sampling statistics

    Erwin Bolthausen and Friedrich Götze. The rate of convergence for multivariate sampling statistics. Ann. Stat., 21(4):1692–1710, 1993.doi:10.1214/aos/1176349393. 8

    work page doi:10.1214/aos/1176349393 1993

  13. [13]

    A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts

    Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Ann. Sci. Éc. Norm. Supér. (4), 53(6):1393–1439, 2020.doi:10.24033/ asens.2450. 8

    work page 2020

  14. [14]

    Random walk on sparse ran- dom digraphs

    Charles Bordenave, Pietro Caputo, and Justin Salez. Random walk on sparse ran- dom digraphs. Probab. Theory Relat. Fields, 170(3-4):933–960, 2018. doi:10.1007/ s00440-017-0796-7. 3, 4, 7, 8, 9, 10, 45, 50

    work page 2018

  15. [15]

    entropic time

    Charles Bordenave, Pietro Caputo, and Justin Salez. Cutoff at the “entropic time” for sparse Markov chains.Probability Theory and Related Fields, 173(1):261–292, February 2019.doi: 10.1007/s00440-018-0834-0. 3, 7, 8, 9, 10, 11, 45

    work page doi:10.1007/s00440-018-0834-0 2019

  16. [16]

    Cutoff at the entropic time for random walks on covered expander graphs

    Charles Bordenave and Hubert Lacoin. Cutoff at the entropic time for random walks on covered expander graphs. J. Inst. Math. Jussieu, 21(5):1571–1616, 2022. doi:10.1017/ S1474748020000663. 8, 34

    work page 2022

  17. [17]

    On concentration of self-bounding functions

    Stéphane Boucheron, Gábor Lugosi, and Pacal Massart. On concentration of self-bounding functions. Electron. J. Probab., 14:no. 64, 1884–1899, 2009.doi:10.1214/EJP.v14-690. 63

    work page doi:10.1214/ejp.v14-690 2009

  18. [18]

    Liesen, Z

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.doi:10.1093/acprof:oso/9780199535255.001.0001. 65

    work page doi:10.1093/acprof:oso/9780199535255.001.0001 2013

  19. [19]

    Mixing time of PageRank surfers on sparse random digraphs

    Pietro Caputo and Matteo Quattropani. Mixing time of PageRank surfers on sparse random digraphs. Random Structures & Algorithms, 59(3):376–406, apr 2021. URL:https://doi. org/10.1002%2Frsa.21009, doi:10.1002/rsa.21009. 8

    work page doi:10.1002/rsa.21009 2021

  20. [20]

    Mixing time trichotomy in regenerating dynamic digraphs

    Pietro Caputo and Matteo Quattropani. Mixing time trichotomy in regenerating dynamic digraphs. Stochastic Processes and their Applications, 137:222–251, jul 2021. URL:https: //doi.org/10.1016%2Fj.spa.2021.03.003, doi:10.1016/j.spa.2021.03.003. 8

    work page doi:10.1016/j.spa.2021.03.003 2021

  21. [21]

    Concentration inequalities with exchangeable pairs (Ph.D. thesis)

    Sourav Chatterjee.Concentration inequalities with exchangeable pairs. PhD thesis, Stanford University, 2005. arXiv:math/0507526. 4, 8, 62, 63, 64, 65, 66

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  22. [22]

    Concentration of Haar measures, with an application to random matrices

    Sourav Chatterjee. Concentration of Haar measures, with an application to random matrices. J. Funct. Anal., 245(2):379–389, 2007.doi:10.1016/j.jfa.2007.01.003. 8, 63, 66

    work page doi:10.1016/j.jfa.2007.01.003 2007

  23. [23]

    Stein’s method for concentration inequalities.Probab

    Sourav Chatterjee. Stein’s method for concentration inequalities.Probab. Theory Related Fields, 138(1-2):305–321, 2007.doi:10.1007/s00440-006-0029-y. 4, 8, 63

    work page doi:10.1007/s00440-006-0029-y 2007

  24. [24]

    A short survey of Stein's method

    Sourav Chatterjee. A short survey of Stein’s method, 2014.arXiv:1404.1392. 8

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  25. [25]

    Speeding up Markov chains with deterministic jumps

    Sourav Chatterjee and Persi Diaconis. Speeding up Markov chains with deterministic jumps. Probab. Theory Related Fields, 181(1-3):377–400, 2021.doi:10.1007/s00440-021-01049-1. 7 70

    work page doi:10.1007/s00440-021-01049-1 2021

  26. [26]

    Exchangeable pairs and Poisson approximation

    Sourav Chatterjee, Persi Diaconis, and Elizabeth Meckes. Exchangeable pairs and Poisson approximation. Probability Surveys, 2(none):64 – 106, 2005. doi:10.1214/ 154957805100000096. 8

    work page 2005

  27. [27]

    Cutoff for random lifts of weighted graphs

    Guillaume Conchon-Kerjan. Cutoff for random lifts of weighted graphs. The Annals of Probability, 50(1):304 – 338, 2022.doi:10.1214/21-AOP1534. 7

    work page doi:10.1214/21-aop1534 2022

  28. [28]

    The cutoff phenomenon in finite Markov chains.Proc

    Persi Diaconis. The cutoff phenomenon in finite Markov chains.Proc. Natl. Acad. Sci. USA, 93(4):1659–1664, 1996.doi:10.1073/pnas.93.4.1659. 7

    work page doi:10.1073/pnas.93.4.1659 1996

  29. [29]

    Generating a random permutation with random transpositions

    Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57(2):159–179, 1981.doi:10.1007/BF00535487. 7, 63, 66

    work page doi:10.1007/bf00535487 1981

  30. [30]

    Cutoff for mixtures of permuted markov chains: general case, 2024.arXiv: 2402.03415

    Bastien Dubail. Cutoff for mixtures of permuted markov chains: general case, 2024.arXiv: 2402.03415. 3

    work page arXiv 2024

  31. [31]

    Sean Eberhard and Péter P. Varjú. Mixing time of the Chung–Diaconis–Graham random process. Probability Theory and Related Fields, 179(1):317–344, February 2021. doi:10. 1007/s00440-020-01009-1. 8

    work page 2021

  32. [32]

    Intersecting families of permutations.J

    David Ellis, Ehud Friedgut, and Haran Pilpel. Intersecting families of permutations.J. Amer. Math. Soc., 24(3):649–682, 2011.doi:10.1090/S0894-0347-2011-00690-5. 6

    work page doi:10.1090/s0894-0347-2011-00690-5 2011

  33. [33]

    An Introduction to Probability Theory and Its Applications, Volume I

    William Feller. An Introduction to Probability Theory and Its Applications, Volume I. 1967. 31

    work page 1967

  34. [34]

    Fountoulakis and B.A

    N. Fountoulakis and B.A. Reed. The evolution of the mixing rate of a sim- ple random walk on the giant component of a random graph. Random Structures & Algorithms, 33(1):68–86, 2008. URL: https://onlinelibrary.wiley.com/doi/abs/ 10.1002/rsa.20210, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa. 20210, doi:https://doi.org/10.1002/rsa.20210. 4, 7

    work page doi:10.1002/rsa.20210 2008

  35. [35]

    Freedman

    David A. Freedman. On tail probabilities for martingales.The Annals of Probability, 3:100– 118, 1975. doi:doi:10.1214/aop/1176996452. 52

    work page doi:10.1214/aop/1176996452 1975

  36. [36]

    A proof of alon’s second eigenvalue conjecture and related problems.Memoirs of the American Mathematical Society, 195(910):0–0, 2008

    Joel Friedman. A proof of alon’s second eigenvalue conjecture and related problems.Memoirs of the American Mathematical Society, 195(910):0–0, 2008. URL: https://doi.org/10. 1090%2Fmemo%2F0910, doi:10.1090/memo/0910. 8

    work page doi:10.1090/memo/0910 2008

  37. [37]

    Cutoff for almost all random walks on abelian groups, 2021

    Jonathan Hermon and Sam Olesker-Taylor. Cutoff for almost all random walks on abelian groups, 2021. arXiv:2102.02809. 7

    work page arXiv 2021

  38. [38]

    Cutoff for random walks on upper triangular matrices, 2021

    Jonathan Hermon and Sam Olesker-Taylor. Cutoff for random walks on upper triangular matrices, 2021. arXiv:1911.02974. 7

    work page arXiv 2021

  39. [39]

    Universality of cutoff for graphs with an added random matching.The Annals of Probability, 50(1), Jan 2022

    Jonathan Hermon, Allan Sly, and Perla Sousi. Universality of cutoff for graphs with an added random matching.The Annals of Probability, 50(1), Jan 2022. URL:https://doi.org/10. 1214%2F21-aop1532, doi:10.1214/21-aop1532. 1, 3, 7, 9, 12, 13, 25, 37, 40, 42 71

    work page doi:10.1214/21-aop1532 2022

  40. [40]

    Cutoff for random walk on random graphs with a community structure

    Jonathan Hermon, Anđela Šarković, and Perla Sousi. Cutoff for random walk on random graphs with a community structure. 2022.arXiv:2212.04469. 7, 9

    work page arXiv 2022

  41. [41]

    On Information and Sufficiency

    Wassily Hoeffding. A combinatorial central limit theorem. The Annals of Mathematical Statistics, 22(4):558–566, 1951.doi:doi:10.1214/aoms/1177729545. 8

    work page doi:10.1214/aoms/1177729545 1951

  42. [42]

    V. A. Kaimanovich and A. M. Vershik. Random walks on discrete groups: Boundary and entropy. The Annals of Probability, 11:457–490, 1983.doi:doi:10.1214/aop/1176993497. 42

    work page doi:10.1214/aop/1176993497 1983

  43. [43]

    Coupling from the past

    David A. Levin and Yuval Peres.Markov chains and mixing times. American Mathematical Society, Providence, RI, 2017. Second edition of [ MR2466937], With contributions by Eliza- beth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. doi:10.1090/mbk/107. 34

    work page doi:10.1090/mbk/107 2017

  44. [44]

    Lectures on the coupling method

    Torgny Lindvall. Lectures on the coupling method. Dover Publications, Inc., Mineola, NY,

    work page

  45. [45]

    Torgny Lindvall and L. C. G. Rogers. On coupling of random walks and renewal processes. Journal of Applied Probability, 33:122–126, 1996. 30

    work page 1996

  46. [46]

    Cutoff on all Ramanujan graphs.Geometric and Functional Analysis, 26(4):1190–1216, July 2016.doi:10.1007/s00039-016-0382-7

    Eyal Lubetzky and Yuval Peres. Cutoff on all Ramanujan graphs.Geometric and Functional Analysis, 26(4):1190–1216, July 2016.doi:10.1007/s00039-016-0382-7. 8

    work page doi:10.1007/s00039-016-0382-7 2016

  47. [47]

    Cutoff phenomena for random walks on random regular graphs

    Eyal Lubetzky and Allan Sly. Cutoff phenomena for random walks on random regular graphs. Duke Mathematical Journal, 153(3):475 – 510, 2010.doi:10.1215/00127094-2010-029. 7

    work page doi:10.1215/00127094-2010-029 2010

  48. [48]

    Russell Lyons, Robin Pemantle, and Yuval Peres. Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure.Ergodic Theory and Dynamical Systems, 15(3):593–619, 1995.doi:10.1017/S0143385700008543. 42

    work page doi:10.1017/s0143385700008543 1995

  49. [49]

    Cambridge University Press, New York,

    Russell Lyons and Yuval Peres.Probability on trees and networks, volume 42 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York,

    work page

  50. [50]

    2, 25, 26

    doi:10.1017/9781316672815. 2, 25, 26

    work page doi:10.1017/9781316672815

  51. [51]

    Construction de suites symétriques

    Bernard Maurey. Construction de suites symétriques. CR Acad. Sci. Paris Sér. AB, 288(14):A679–A681, 1979. 4

    work page 1979

  52. [52]

    An entropic proof of cutoff on Ramanujan graphs.Electronic Communica- tions in Probability, 25:1 – 8, 2020.doi:10.1214/20-ECP358

    Narutaka Ozawa. An entropic proof of cutoff on Ramanujan graphs.Electronic Communica- tions in Probability, 25:1 – 8, 2020.doi:10.1214/20-ECP358. 8

    work page doi:10.1214/20-ecp358 2020

  53. [53]

    Concentration inequalities for Markov chains by Marton couplings and spectral methods

    Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electron. J. Probab., 20:no. 79, 32, 2015.doi:10.1214/EJP.v20-4039. 34, 35

    work page doi:10.1214/ejp.v20-4039 2015

  54. [54]

    Cutoff for non-negatively curved markov chains

    Justin Salez. Cutoff for non-negatively curved markov chains. Journal of the European Mathematical Society, May 2023. URL: https://doi.org/10.4171%2Fjems%2F1348, doi: 10.4171/jems/1348. 7, 8

    work page doi:10.4171/jems/1348 2023

  55. [55]

    Random walks on finite groups

    Laurent Saloff-Coste. Random walks on finite groups. In Probability on Discrete Struc- tures, pages 263–346. Springer Berlin Heidelberg, 2004. URL:https://doi.org/10.1007% 2F978-3-662-09444-0_5, doi:10.1007/978-3-662-09444-0_5. 7 72

    work page doi:10.1007/978-3-662-09444-0_5 2004

  56. [56]

    A bound for the error in the normal approximation to the distribution of a sum of dependent random variables

    Charles Stein. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Berkeley Symposium on Mathematical Statistics and Probability, 1972, 1972. URL:http://projecteuclid.org/euclid.bsmsp/1200514239. 8

    work page arXiv 1972

  57. [57]

    Approximate computation of expectations.Lecture Notes-Monograph Series, 7:i–164, 1986

    Charles Stein. Approximate computation of expectations.Lecture Notes-Monograph Series, 7:i–164, 1986. URL:http://www.jstor.org/stable/4355512. 8

    work page arXiv 1986

  58. [58]

    Concentration of measure and isoperimetric inequalities in product spaces

    Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications mathématiques de l'IHÉS, 81(1):73–205, Dec 1995. URL:https://doi.org/10. 1007%2Fbf02699376, doi:10.1007/bf02699376. 4 73

    work page doi:10.1007/bf02699376 1995