[52] Amir Dembo, Nina Gantert, Yuval Peres, and Ofer Zeitouni. Large deviations for random walks on Galton-Watson trees: averaging and uncertainty. *Probab. Theory Related Fields*, 122(2):241–288, 2002. doi:10.1007/s004400100162. 149, 178, 179

[53] Yves Derriennic. Marche aléatoire sur le groupe libre et frontière de Martin. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 32(4):261–276, December 1975. doi:10.1007/BF00535840. 62

[54] Yves Derriennic. Quelques applications du théoreme ergodique sous-additif. *Astérisque*, 74:183–201, 1980. 14, 15, 26, 27, 53

[55] P. Diaconis and L. Saloff-Coste. What do we know about the metropoli-
lis algorithm ? *Journal of Computer and System Sciences*, 57(1):20-
36, 1998. URL: https://www.sciencedirect.com/science/article/pii/
S0022000098915768, doi:https://doi.org/10.1006/jcss.1998.1576. 18, 30

[56] Persi Diaconis. *Group representations in probability and statistics*, volume 11 of *Institute of Mathematical Statistics Lecture Notes—Monograph Series*. Institute of Mathematical Statistics, Hayward, CA, 1988. URL: https://www.jstor.org/stable/4355560. 75

[57] 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. 22, 33, 118

[58] Persi Diaconis. Some things we've learned (about Markov chain Monte Carlo). *Bernoulli*, 19(4):1294 – 1305, 2013. doi:10.3150/12-BEJSP09. 18, 30

[59] Persi Diaconis and Ron Graham. An affine walk on the hypercube. *J. Comput. Appl. Math.*, 41(1-2):215-235, 1992. Asymptotic methods in analysis and combinatorics. doi:10.1016/0377-0427(92)90251-R. 70

[60] Persi Diaconis, Susan Holmes, and Radford M. Neal. Analysis of a nonreversible Markov chain sampler. *Ann. Appl. Probab.*, 10(3):726–752, 2000. doi:10.1214/aoap/1019487508. 18, 30

[61] 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. 21, 22, 33, 104, 108

[62] Persi Diaconis and Mehrdad Shahshahani. Time to Reach Stationarity in the Bernoulli-Laplace Diffusion Model. *SIAM Journal on Mathematical Anal-
ysis, 18(1):208–218, 1987. arXiv:https://doi.org/10.1137/0518016, doi: 10.1137/0518016. 22, 33

[63] Jian Ding, Eyal Lubetzky, and Yuval Peres. Total variation cutoff in birth-and-death chains. *Probability Theory and Related Fields*, 146(1):61, November 2008. doi:10.1007/s00440-008-0185-3. 22, 33

[64] Jian Ding, Eyal Lubetzky, and Yuval Peres. The Mixing Time Evolution of Glauber Dynamics for the Mean-Field Ising Model. *Communications in Mathematical Physics*, 289(2):725–764, July 2009. doi:10.1007/s00220-009-0781-9. 22, 33

[65] Bastien Dubail and Laurent Massoulié. Accelerating Abelian Random Walks with Hyperbolic Dynamics. *Probability Theory and Related Fields*, 04 2022. doi: 10.1007/s00440-022-01128-x. 13, 25, 67

[66] Richard Durrett. *Essentials of stochastic processes*. Springer-Verlag Inc, Berlin; New York, 1999. 13, 25

[67] Ken Dykema. Symmetric random walks on certain amalgamated free product groups. In *Topological and asymptotic aspects of group theory*, volume 394 of *Contemp. Math.*, pages 87–99. Amer. Math. Soc., Providence, RI, 2006. doi: 10.1090/conm/394/07436. 46

[68] Sean Eberhard and Péter P. Varjú. Mixing time of the Chung–Dionis–Graham random process. *Probability Theory and Related Fields*, 179(1):317–344, February 2021. doi:10.1007/s00440-020-01009-1. 70, 74, 119

[69] 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. 99

[70] Alexandros Eskenazis and Evita Nestoridi. Cutoff for the Bernoulli–Laplace urn model with $o(n)$ swaps. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 56(4):2621–2639, 2020. doi:10.1214/20-AIHP1052. 22, 33

[71] William Feller. An Introduction to Probability Theory and Its Applications, Volume I. 1967. 169

[72] Behrang Forghani. Asymptotic entropy of transformed random walks. *Ergodic Theory and Dynamical Systems*, 37(5):1480–1491, Jan 2016. URL: https://doi.org/10.1017%2Fetds.2015.90, doi:10.1017/etds.2015.90. 44
[73] N. Fountoulakis and B.A. Reed. The evolution of the mixing rate of a simple 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. 115, 118

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

[75] 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. 119

[76] Harry Furstenberg. Noncommuting random products. *Transactions of the American Mathematical Society*, 108(3):377–428, 1963. URL: https://doi.org/10.1090/2Fs0002-9947-1963-0163345-0, doi:10.1090/s0002-9947-1963-0163345-0. 14, 26, 42, 60

[77] Lorenz Gilch. Asymptotic Entropy of Random Walks on Free Products. *Electronic Journal of Probability*, 16(none):76 – 105, 2011. doi:10.1214/EJP.v16-841. 41, 53, 60

[78] Lorenz A. Gilch. Rate of escape of random walks on free products. *J. Aust. Math. Soc.*, 83(1):31–54, 2007. doi:10.1017/S1446788700036375. 41, 53, 60

[79] Lorenz A Gilch and François Ledrappier. Regularity of the drift and entropy of random walks on groups. *arXiv preprint arXiv:1512.03552*, 2015. 46

[80] Sébastien Gouëzel. Analyticity of the entropy and the escape rate of random walks in hyperbolic groups. *Discrete Anal.*, pages Paper No. 7, 37, 2017. doi:10.19086/da.1639. 46

[81] Geoffrey Grimett and Harry Kesten. Random Electrical Networks on Complete Graphs II: Proofs. 08 2001. 149

[82] Yves Guivarc'h. Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire. In *Journées sur les marches aléatoires*, number 74 in Astérisque. Société mathématique de France, 1980. URL: http://www.numdam.org/item/AST_1980_74__47_0/. 14, 26

[83] Uffe Haagerup and Steen Thorbjørnsen. A new application of random matrices: $\text{Ext}(C_{\text{red}}^*(F_2))$ is not a group. *Annals of Mathematics*, 162(2):711–
775, Sep 2005. URL: https://doi.org/10.4007/2Fannals.2005.162.711, doi: 10.4007/annals.2005.162.711. 15, 27, 38

[84] Robert H Haring-Smith. Groups and simple languages. *Transactions of the American Mathematical Society*, 279(1):337–356, 1983. 42

[85] Yair Hartman, Yuri Lima, and Omer Tamuz. An abramov formula for stationary spaces of discrete groups. *Ergodic Theory and Dynamical Systems*, 34(3):837–853, jan 2013. URL: https://doi.org/10.1017%2Fetds.2012.167, doi:10.1017/etds.2012.167. 44

[86] W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. *Biometrika*, 57:97–109, 1970. 18, 30

[87] Jimmy He. Markov chains on finite fields with deterministic jumps. *Electronic Journal of Probability*, 27, Jan 2022. URL: https://doi.org/10.1214%2F22-ejp757, doi:10.1214/22-ejp757. 67, 71

[88] Jimmy He, Huy Tuan Pham, and Max Wenqiang Xu. Mixing time of fractional random walk on finite fields. *Electronic Journal of Probability*, 27, Jan 2022. URL: https://doi.org/10.1214%2F22-ejp858, doi:10.1214/22-ejp858. 67, 71, 72, 74

[89] J. William Helton, Tobias Mai, and Roland Speicher. Applications of realizations (aka linearizations) to free probability. *J. Funct. Anal.*, 274(1):1–79, 2018. doi: 10.1016/j.jfa.2017.10.003. 15, 27, 37, 41, 46

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

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

[92] 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. 23, 34, 113, 115, 118, 119, 120, 121, 125, 127, 146, 148, 176

[93] Jonathan Hermon, Anđela Šarković, and Perla Sousi. Cutoff for random walk on random graphs with a community structure. 2022. arXiv:2212.04469. 119, 120, 121
[94] Martin Hildebrand. Random processes of the form $x_{n+1} = a_n x_n + b_n \pmod p$. *Ann. Probab.*, 21(2):710–720, 04 1993. doi:10.1214/aop/1176989264. 69, 70, 71

[95] Martin Hildebrand. Random processes of the form $X_{n+1} = a_n X_n + b_n \pmod p$ where $b_n$ takes on a single value. In *Random discrete structures (Minneapolis, MN, 1993)*, volume 76 of *IMA Vol. Math. Appl.*, pages 153–174. Springer, New York, 1996. doi:10.1007/978-1-4612-0719-1_10. 69, 70, 88

[96] Martin Hildebrand. On the Chung-Diaconis-Graham random process. *Electron. Comm. Probab.*, 11:347–356, 2006. doi:10.1214/ECP.v11-1237. 70

[97] Martin Hildebrand. A lower bound for the Chung-Diaconis-Graham random process. *Proc. Amer. Math. Soc.*, 137(4):1479–1487, 2009. doi:10.1090/S0002-9939-08-09687-1. 70

[98] Martin Hildebrand. On a lower bound for the Chung-Diaconis-Graham random process. *Statist. Probab. Lett.*, 152:121–125, 2019. doi:10.1016/j.spl.2019.04.020. 70

[99] Martin Hildebrand. A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process. *Journal of Theoretical Probability*, 2021. doi:10.1007/s10959-021-01088-3. 70, 71

[100] Martin Hildebrand and Joseph McCollum. Generating random vectors in $(\mathbb{Z}/p\mathbb{Z})^d$ via an affine random process. *J. Theoret. Probab.*, 21(4):802–811, 2008. doi:10.1007/s10959-007-0135-5. 19, 31, 67, 68, 70

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

[102] 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. 14, 15, 26, 27, 41, 44, 53, 60, 192

[103] Vadim Kaimanovich. The poisson boundary of covering markov operators. *Israel Journal of Mathematics*, 89(1-3):77–134, 1995. 39, 43

[104] Vadim A Kaimanovich. "Münchhausen trick" and amenability of self-similar groups. *International Journal of Algebra and Computation*, 15(05n06):907–937, 2005. 39, 44
[105] Vadim A. Kaimanovich. Self-similarity and random walks. pages 45–70, 2009. URL: https://doi.org/10.1007/2F978-3-0346-0030-9_2, doi:10.1007/978-3-0346-0030-9_2. 39, 44

[106] Kseniya Klyachko. *Random Processes of the Form $X_N + 1 = AX_N + B_N \pmod p$*. PhD thesis, State University of New York at Albany, 2020. 19, 31, 67, 70, 91

[107] András Krámli and Domokos Szász. Random walks with internal degrees of freedom. *Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete*, 63(1):85-95, 1983. 39

[108] Hubert Lacoin. Mixing time and cutoff for one dimensional particle systems, 2021. arXiv:2111.06436. 22, 33

[109] Steven P Lalley. Finite range random walk on free groups and homogeneous trees. *The Annals of Probability*, pages 2087–2130, 1993. 46, 62, 64

[110] Serge Lang. *Algebra*. Springer New York, 2002. 68, 73, 81

[111] Michel Ledoux. *The concentration of measure phenomenon*. American Mathematical Society, Providence, 2001. 20, 31

[112] François Ledrappier. Analyticity of the entropy for some random walks. *Groups Geom. Dyn.*, 6(2):317–333, 2012. doi:10.4171/GGD/159. 46

[113] François Ledrappier. Regularity of the entropy for random walks on hyperbolic groups. *Ann. Probab.*, 41(5):3582–3605, 2013. doi:10.1214/12-AOP748. 46

[114] François Ledrappier. Some asymptotic properties of random walks on free groups. *Topics in probability and Lie groups: boundary theory*, 28:117–152, 2001. 15, 27, 41, 46, 53, 55, 56, 59, 60, 61

[115] Franz Lehner. Computing norms of free operators with matrix coefficients. *American Journal of Mathematics*, 121(3):453–486, 1999. 46, 60

[116] David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. *Probability Theory and Related Fields*, 146(1):223, December 2008. doi: 10.1007/s00440-008-0189-z. 22, 33

[117] David A. Levin and Yuval Peres. *Markov chains and mixing times*. American Mathematical Society, Providence, RI, 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. doi:10.1090/mbk/107. 13, 17, 18, 23, 25, 29, 30, 34, 172

[118] Elon Lindenstrauss and Péter P. Varjú. Spectral gap in the group of affine transformations over prime fields. *Ann. Fac. Sci. Toulouse Math. (6)*, 25(5):969–993, 2016. doi:10.5802/afst.1518. 72

[119] Torgny Lindvall. *Lectures on the coupling method*. Dover Publications, Inc., Mineola, NY, 2002. 167

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

[121] 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. 119

[122] 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. 23, 34, 118

[123] Eyal Lubetzky and Allan Sly. Cutoff for general spin systems with arbitrary boundary conditions. *Communications on Pure and Applied Mathematics*, 67(6):982–1027, 2014. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21489, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/cpa.21489, doi:https://doi.org/10.1002/cpa.21489. 22, 33

[124] Eyal Lubetzky and Allan Sly. Universality of cutoff for the Ising model. *The Annals of Probability*, 45(6A):3664 – 3696, 2017. doi:10.1214/16-AOP1146. 22, 33

[125] Alexander Lubotzky and Igor Pak. The product replacement algorithm and Kazhdan's property (T). *J. Amer. Math. Soc.*, 14(2):347–363, 2001. doi:10.1090/S0894-0347-00-00356-8. 73

[126] 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. 192

[127] Russell Lyons, Robin Pemantle, and Yuval Peres. Biased random walks on Galton-Watson trees. *Probab. Theory Relat. Fields*, 106(2):249–264, 1996. doi:10.1007/s004400050064. 175
[128] Russell Lyons and Yuval Peres. *Probability on trees and networks*, volume 42 of *Cambridge Series in Statistical and Probabilistic Mathematics*. Cambridge University Press, New York, 2016. doi:10.1017/9781316672815. 13, 25, 53, 116, 151, 152

[129] Jean Mairesse. Random walks on groups and monoids with a Markovian harmonic measure. *Electron. J. Probab.*, 10:1417–1441, 2005. Id/No 43. 41, 42, 43, 46, 54, 56, 60

[130] Jean Mairesse and Frédéric Mathéus. Random walks on free products of cyclic groups. *J. Lond. Math. Soc., II. Ser.*, 75(1):47–66, 2007. doi:10.1112/jlms/jd1006. 41, 53, 56, 60, 61

[131] Fabio Martinelli. *Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures*, pages 175–262. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. doi:10.1007/978-3-662-09444-0_4. 18, 29

[132] P. Mathieu. Differentiating the entropy of random walks on hyperbolic groups. *Ann. Probab.*, 43(1):166–187, 2015. doi:10.1214/13-AOP901. 46

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

[134] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augustus H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. *The Journal of Chemical Physics*, 21(6):1087–1092, jun 1953. URL: https://doi.org/10.1063/2F1.1699114, doi:10.1063/1.1699114. 18, 30

[135] James A. Mingo and Roland Speicher. *Free probability and random matrices*, volume 35 of *Fields Institute Monographs*. Springer, New York; Fields Institute for Research in Mathematical Sciences, Toronto, ON, 2017. doi:10.1007/978-1-4939-6942-5. 38

[136] Ravi Montenegro and Prasad Tetali. Mathematical aspects of mixing times in markov chains. *Foundations and Trends® in Theoretical Computer Science*, 1(3):237–354, 2006. URL: http://dx.doi.org/10.1561/0400000003, doi:10.1561/0400000003. 17, 29

[137] Arunava Mukherjea and Nicolas A. Tserpes. *Measures on topological semigroups: convolution products and random walks*. Lecture Notes in Mathematics, Vol. 547. Springer-Verlag, Berlin-New York, 1976. 86
[138] Tatiana Nagnibeda and Wolfgang Woess. Random walks on trees with finitely many cone types. *J. Theoret. Probab.*, 15(2):383–422, 2002. doi:10.1023/A:1014810827031. 60

[139] Radford M. Neal. *Bayesian learning for neural networks*. Springer-Verlag Inc, Berlin; New York, 1996. 18, 29

[140] Radford M. Neal. MCMC using Hamiltonian dynamics. In *Handbook of Markov chain Monte Carlo*, Chapman & Hall/CRC Handb. Mod. Stat. Methods, pages 113–162. CRC Press, Boca Raton, FL, 2011. 18, 30

[141] Richard Neville III. *On lower bounds of the Chung-Diaconis-Graham random process*. PhD thesis, State University of New York at Albany, 2011. 70

[142] J. R. Norris. *Markov chains*, volume 2 of *Cambridge Series in Statistical and Probabilistic Mathematics*. Cambridge University Press, Cambridge, 1998. Reprint of 1997 original. 13, 25

[143] Narutaka Ozawa et al. An entropic proof of cutoff on ramanujan graphs. *Electronic Communications in Probability*, 25, 2020. 119

[144] Igor Pak. What do we know about the product replacement algorithm? In *Groups and computation, III (Columbus, OH, 1999)*, volume 8 of *Ohio State Univ. Math. Res. Inst. Publ.*, pages 301–347. de Gruyter, Berlin, 2001. 73

[145] 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. 172, 173

[146] Patrick Rebeschini and Sekhar C Tatikonda. Accelerated consensus via min-sum splitting. *Advances in Neural Information Processing Systems*, 30, 2017. 18, 30

[147] Christian Robert and George Casella. A short history of Markov Chain Monte Carlo: Subjective recollections from incomplete data. *Statistical Science*, 26(1):102–115, 2011. doi:doi:10.1214/10-STS351. 18, 29

[148] Christian P. Robert and George Casella. *Monte Carlo statistical methods*. Springer-Verlag Inc, Berlin; New York, 1999. 18, 29

[149] 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. 23, 34, 118, 119
[150] Laurent Saloff-Coste. Random walks on finite groups. In *Probability on Discrete Structures*, 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. 22, 33, 118

[151] Dominik Schmid. *Mixing times and limit theorems for exclusion processes*. PhD thesis, Technische Universität München, 2021. 22, 33

[152] Eugene Seneta. *Non-negative matrices and Markov chains*. Springer Science & Business Media, 2006. 61, 62

[153] Nikita Sidorov. Arithmetic dynamics. In *Topics in dynamics and ergodic theory*, volume 310 of *London Math. Soc. Lecture Note Ser.*, pages 145–189. Cambridge Univ. Press, Cambridge, 2003. doi:10.1017/CB09780511546716.010. 90

[154] 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. 101

[155] Charles Stein. Approximate computation of expectations. *Lecture Notes-Monograph Series*, 7:i-164, 1986. URL: http://www.jstor.org/stable/4355512. 101

[156] 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. 97

[157] Terence Tao. *Expansion in finite simple groups of Lie type*, volume 164 of *Graduate Studies in Mathematics*. American Mathematical Society, Providence, RI, 2015. doi:10.1090/gsm/164. 72

[158] A. M. Vershik. Arithmetic isomorphism of hyperbolic automorphisms of a torus and of sofic shifts. *Funktsional. Anal. i Prilozhen.*, 26(3):22-27, 1992. doi: 10.1007/BF01075629. 90

[159] Wolfgang Woess. *Random walks on infinite graphs and groups*, volume 138 of *Cambridge Tracts in Mathematics*. Cambridge University Press, Cambridge, 2000. doi:10.1017/CB09780511470967. 42, 154
## RÉSUMÉ

Cette thèse aborde trois sujets principaux liés aux marches aléatoires et aux chaînes de Markov. Le premier concerne l'introduction d'une technique appelée "linéarisation" pour simplifier l'étude des marches aléatoires dans des groupes discrets, en les réduisant à des marches aux plus proches voisins dans un espace d'états élargi. Ensuite, elle étudie un mécanisme d'accélération des dynamiques markoviennes par l'intégration d'étapes de dynamique déterministe, où l'effet accélérateur est attribué au caractère chaotique de cette dynamique. Enfin, elle explore le phénomène de cutoff en démontrant un phénomène de cutoff au temps entropique pour un modèle général de chaînes de Markov en environnement aléatoire. Un nouveau résultat de concentration de la mesure pour le groupe symétrique est développé à cet effet.

## MOTS CLÉS

Temps de mélange, chaîne de Markov, cutoff, environnement aléatoire, accélération, linéarisation, marche aléatoire

## ABSTRACT

This thesis covers three main topics related to random walks and Markov chains. The first involves the introduction of a technique called "linearization" to simplify the study of random walks in discrete groups, by reducing them to nearest-neighbor walks in an expanded state space. Next, it investigates a mechanism to accelerate Markovian dynamics by incorporating deterministic steps, where the acceleration effect is attributed to the chaotic nature of this dynamic. Finally, it explores the "cutoff" phenomenon, demonstrating a cutoff phenomenon at the entropic time for a general model of Markov chains in random environment. A new measure concentration result for the symmetric group is developed for this purpose.

## KEYWORDS

Mixing times, Markov chains, cutoff, random environment, acceleration, linearization, random walks