<figure><img src="image_1.png" /></figure>

HAL
open science

# Mixing times of Markov chains: acceleration and cutoff in random environment

Bastien Dubail

<figure><img src="image_2.png" /></figure>

## To cite this version:

Bastien Dubail. Mixing times of Markov chains: acceleration and cutoff in random environment. Probability [math.PR]. Ecole Normale Superieure, 2023. English. NNT: tel-04434707

HAL Id: tel-04434707

https://inria.hal.science/tel-04434707

Submitted on 2 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
## THÈSE DE DOCTORAT
DE L'UNIVERSITÉ PSL

Préparée à l'École Normale Supérieure et l'Université d'Aix-Marseille

# Temps de mélange de chaînes de Markov : accélération et cutoff en environnement aléatoire

## Soutenue par

Bastien Dubail

Le 13/10/2023

## École doctorale n° 386

Sciences Mathématiques de
Paris Centre

## Spécialité

Mathématiques

## Composition du jury :

Alexandre PROUTIERE
Professor,
KTH Royal Institute of Technology
Président

Perla SOUSI
Professor, University of Cambridge
Rapporteuse

Sourav CHATTERJEE
Professor, Stanford University
Rapporteur

Anna BEN HAMOU
Maître de Conférences,
Sorbonne Université
Examinatrice

Justin SALEZ
Professeur, Université Paris-Dauphine
Examinateur

Charles BORDENAVE
Directeur de recherche,
Aix-Marseille Université
Co-directeur
de thèse

Laurent MASSOULIE
Directeur de recherche,
INRIA
Directeur de thèse

<figure><img src="image_4.png" /></figure>
# Temps de mélange de chaînes de Markov :
accélération et cutoff en environnement
aléatoire

Bastien Dubail

École Normale Supérieure, Département d'Informatique, INRIA

PSL Research University, Paris, France

Aix-Marseille Université, Marseille, France

Thèse réalisée sous la supervision de Laurent Massoulié et Charles Bordenave
# Résumé

Cette dissertation a pour objet l'étude de différentes questions reliées aux marches aléatoires et aux temps de mélange de chaînes de Markov.

Notre première contribution est l'introduction d'une nouvelle technique, appelée linéarisation, dans l'étude d'une marche aléatoire sur un groupe discret. Inspirée par des approches de linéarisation similaires utilisée pour l'étude des algèbres d'opérateurs et des matrices aléatoires, cette méthode se voit ici proposée un tout nouveau champ d'applications. Lorsqu'un groupe est donné par un ensemble fini de générateurs, nous montrons comment la linéarisation peut simplifier l'étude des marches aléatoires à support fini en les réduisant à des marches aux plus proches voisins, moyennant la considération d'un espace d'états élargi. Nous démontrons l'efficacité de cette technique en établissant des formules explicites pour des quantités asymptotiques telles que la vitesse et l'entropie de la marche, dans le cas des groupes libres et des produits libres de groupes finis.

Notre deuxième contribution porte sur un mécanisme d'accélération de dynamiques markoviennes, consistant à intercaler des étapes de dynamique déterministe entre les étapes aléatoires d'une chaîne de Markov. Lorsque la dynamique déterministe est elle-même choisie de façon aléatoire, il a été prouvé que le temps de mélange devient logarithmique en la taille de l'espace d'états avec grande probabilité, ce qui pour de nombreuses chaînes de Markov équivaut à une accélération exponentielle. Notre travail tente de "dérandomiser" ce résultat en étudiant une version multi-dimensionnelle de l'exemple historique pour lequel cette accélération a été étudiée pour la première fois. Dans cet exemple explicite, nous suggérons ainsi que l'accélération est l'effet du caractère chaotique de la dynamique déterministe appliquée.

La troisième partie de notre travail porte sur le phénomène de cutoff, qui est la convergence abrupte vers l'équilibre d'une chaîne de Markov. Nous étudions un phénomène de cutoff pour une chaîne en environnement aléatoire qui est un cadre propice à l'apparition du phénomène. Le modèle étudié consiste à superposer deux chaînes de Markov sur un même espace d'états, après avoir permuté les états de l'une de façon uniforme. Sous des hypothèses peu contraignantes, nous prouvons un phénomène de
cutoff au temps dit entropique. En particulier nous ne faisons aucune hypothèse de réversibilité ou d'irréversibilité, c'est-à-dire que nous autorisons la chaîne à revenir sur ses pas. Jusqu'à présent, l'une ou l'autre de ces hypothèses devait généralement être faite pour pouvoir établir le phénomène de cutoff. Nous proposons ainsi une stratégie de preuve unique faisant le pont entre ces deux cas opposés. L'argument repose en grande partie sur un nouveau résultat de concentration de la mesure pour le groupe symétrique, développé spécifiquement pour ce problème, et qui constitue ainsi une autre contribution de cette thèse.
Abstract

The aim of this dissertation is to explore various aspects concerning random walks and mixing times of Markov chains.

First, our research introduces a novel technique called "linearization" in the analysis of random walks on discrete groups. Drawing inspiration from similar linearization approaches in operator algebras and random matrices, this opens up a whole new field of applications of this method. When a group is given by a finite set of generators, we show how linearization can simplify the study of finitely supported random walks by reducing to nearest-neighbour walks, at the cost of considering a slightly more general state space. We demonstrate the effectiveness of this technique by providing explicit formulas for asymptotic quantities like the speed and entropy of the walk, in the case of free groups and free products of finite groups.

Our second contribution concerns a mechanism for accelerating Markov dynamics, consisting in inserting deterministic dynamics steps between the random steps of a Markov chain. When the deterministic dynamics is itself chosen randomly, it was proved that the mixing time becomes logarithmic in the size of the state space with high probability, which for many Markov chains implies an exponential speed-up. Our work attempts to "derandomize" this result by studying a multi-dimensional version of the historical example where such acceleration was first observed. In this explicit example, we thus suggest that the acceleration is the effect of the chaotic aspect of the applied deterministic dynamics.

The third part of our work deals with the cutoff phenomenon, which is the abrupt convergence of a Markov chain towards equilibrium. We study a cutoff phenomenon for a chain in a random environment, a setting known to favor the phenomenon's appearance. The model studied consists in superposing two Markov chains on the same state space, one being subject to a uniform permutation of the states. Under mild assumptions we prove such chains exhibit a cutoff phenomenon at the so-called entropic time. In particular we do not assume reversibility or non-backtrackingness, which can be thought of as the opposite of reversibility. Until now, one or other of these assumptions was generally made in order to establish the cutoff phenomenon.
We propose a unified proof strategy that bridges these opposing cases. This relies heavily on a novel measure concentration result for the symmetric group, developed explicitly for this problem, thereby making another contribution of this thesis.
Remerciements

Mes premiers remerciements vont à Charles et Laurent, pour m'avoir encadré pendant
ma thèse et les stages qui l'ont précédée. Je les remercie pour leur soutien sans faille
tout au long de cette odyssée, pour leur enseignement, qui va bien au delà du seul plan
scientifique, ainsi que pour leur humour et leur permanente bienveillance. Je leur suis
également très reconnaissant pour leurs conseils avisés en terme de stratégie et l'aide
apportée durant la recherche de post-doc. Je sais que j'ai encore beaucoup à apprendre
et que je peux compter sur eux.

Je remercie Perla Sousi, Anna Ben Hamou, Sourav Chatterjee, Justin Salez et
Alexandre Proutière qui me font un véritable honneur en ayant accepté de faire partie de
mon jury. Leurs travaux ont été et continuent d'être une immense source d'inspiration
pour moi. Je remercie particulièrement Perla Sousi et Sourav Chatterjee d'avoir accepté
la lourde tâche de rapporteurs et apporté leur expertise, en plein été, à la lecture de ce
manuscrit. Je tiens à remercier également Alexandre Proutière d'avoir accepté de me
prendre en tant que post-doctorant à KTH. L'aperçu que j'en ai eu me fait entrevoir
de belles perspectives et je me réjouis déjà des défis à venir.

Il me paraît tout naturel d'exprimer ensuite ma reconnaissance envers toutes les
personnes qui ont été directement auprès de moi durant ce périple. Je remercie mes ca-
marades doctorants et post-docs, dont la chaleureuse compagnie aura été déterminante
dans la préparation de cette thèse. Merci au «groupe le plus calé en bombardement» (de
papiers), j'ai nommé Luca, Eric, Mathieu, Matthieu et Jakob, mes très chers com-
pagnons de bureau, qui ne cessent de m'étonner de par leurs multiples talents. Merci
pour tous les échanges scientifiques, les moments de franche rigolade, les discussions lors
des moments de doute... autant d'ingrédients qui m'auront aidé à effectuer ma thèse
dans les meilleures conditions. Merci aux doctorants Claire, Romain, Vianey, David,
Lucas, Thomas, Amaury, Batiste, Antoine, avec qui j'ai aimé conversé de maths, de
musique, de sport... autour d'une bière ou d'un repas à l'AGRAF, et mené des opéra-
tions de «team-building», séminaire ou groupe de lecture. Je remercie le grand homme
de culture qu'est le docteur Shilov, présent à mes côtés depuis le début, avec qui on
arrête assez vite de compter les anectodes mémorables tant il y en a. Спасибо, Илья!
Merci à Bertille pour ses fréquentes visites depuis les étages supérieurs, apportant tou-
jours du réconfort aux moments opportuns. Merci à Adam, Sarah, Jeffrey, Juan, Yanis,
Yenni, Anaïs, Antoine que je n'ai pas manqué de retrouvé à chacune de mes visites
à Marseille. Que de bons moments j'ai passé avec eux à l'I2M, au cours Ju ou dans
les Calanques. Merci à Ludovic et Simon, mes aînés de thèse que j'ai eu la chance de
cotoyer et qui ont été pour moi des modèles à suivre.

Je suis extrêmement reconnaissant envers toute l'équipe des Argonautes, dont le
dynamisme et la bonne humeur auront apporté une énergie et une motivation sans pareil
pour la réalisation de cette thèse. Un merci tout particulier à Hélène B., Argonaute
jusqu'à cet été, qui aura contribué de façon essentielle à faire de l'équipe ce qu'elle
est aujourd'hui, par son travail, son dévouement et son inébranlable enthousiasme.
Merci à notre nouvelle recrue Marina ainsi qu'à Hélène M. de nous prêter main forte
aussi souvent que nécessaire. J'addresse ma gratitude également à Lise-Marie, pour sa
disponiblité, son sourire et son accueil à chacune de mes venues au DI ENS. Merci à
Evelyne et Marie-Christine, toujours aux petits soins lors de mes visites à Marseille.
J'adresse plus généralement des remerciements à toutes les petites mains et services
grâce auxquels nous pouvons venir à bout de bien des tracasseries administratives.
Merci à Marion, Alexandre, Christine et Johanna d'égayer encore un peu plus la vie du
troisième étage par leurs sourires. Merci à l'AGOS, instigatrice de nombreuses soirées
mémorables. Merci aux impresarios de la science, Lucile et toute l'équipe de la Comm'.

Ces années studieuses se sont aussi accompagnées de quelques moments de répit
salvateurs. Je tiens ainsi à remercier quelques uns de mes amis qui sans le savoir
peut-être ont joué un rôle dans cette aventure. Merci à Emmanuel et Nicolas, éternels
compagnons de la «Stratosteam», ainsi qu'à Alexis, mon fidèle colloc de Lyon, pour
les moments partagés pendant toutes ces années, notamment celles du covid. Merci
à Cédric de m'avoir initié à l'art du slap. Merci au Jeune Kayak Parisien, véritable
petite famille qu'il m'est triste de devoir quitter aujourd'hui. Merci à Mathias et
Fred de m'avoir enseigné l'art de vivre jkpiste et fait découvrir les magnifiques rivières
du Morvan. Merci à Lara, Colas, Paul, Camille et Yannick pour tous ces moments
mémorables vécus ces deux dernières années.

Enfin, je remercie ma famille. Mes parents bien sûr, pour leur soutien indéfectible
durant toutes mes études, mais aussi le triumvirat formé par Jérôme, Pauline et Hélène,
qui y sont sans doute un peu pour quelque chose dans l'existence aujourd'hui de ce
manuscrit.
# Contents

<table><tr><td><strong>Résumé détaillé</strong></td><td><strong>13</strong></td></tr><tr><td>Marches aléatoires sur les groupes</td><td>13</td></tr><tr><td>Accélération de chaînes de Markov</td><td>16</td></tr><tr><td>Concentration sur le groupe symétrique</td><td>20</td></tr><tr><td>Le phénomène de cutoff</td><td>21</td></tr><tr><td><strong>1 Introduction</strong></td><td><strong>25</strong></td></tr><tr><td>1.1 Random walks on groups</td><td>25</td></tr><tr><td>1.2 Acceleration of Markov chains</td><td>28</td></tr><tr><td>1.3 Concentration on the symmetric group</td><td>31</td></tr><tr><td>1.4 The cutoff phenomenon</td><td>33</td></tr><tr><td><strong>2 Linearization of random walks on groups</strong></td><td><strong>37</strong></td></tr><tr><td>2.1 Introduction</td><td>37</td></tr><tr><td>2.1.1 The linearization trick and coloured random walks on groups</td><td>38</td></tr><tr><td>2.1.2 Main results</td><td>40</td></tr><tr><td>2.2 A linearization trick</td><td>47</td></tr><tr><td>2.2.1 Linearization in the non-reversible case</td><td>48</td></tr><tr><td>2.2.2 Linearization in the reversible case</td><td>51</td></tr><tr><td>2.3 Coloured random walks on free products of groups</td><td>53</td></tr><tr><td>2.3.1 The harmonic measure on the boundary</td><td>54</td></tr><tr><td>2.3.2 Markovian structure of the harmonic measure</td><td>55</td></tr><tr><td>2.3.3 Solving the traffic equations</td><td>57</td></tr><tr><td>2.4 Computing drift and entropy</td><td>60</td></tr><tr><td>2.4.1 Convergence in direction for inhomogeneous products of matrices</td><td>61</td></tr><tr><td><strong>3 Accelerating abelian random walks with hyperbolic dynamics</strong></td><td><strong>67</strong></td></tr><tr><td>3.1 Introduction</td><td>67</td></tr><tr><td>3.1.1 Main results</td><td>67</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>3.1.2 Related works</td>
      <td>70</td>
    </tr>
    <tr>
      <td>3.1.3 Discussion</td>
      <td>71</td>
    </tr>
    <tr>
      <td>3.2 A lower bound for all n</td>
      <td>74</td>
    </tr>
    <tr>
      <td>3.3 An upper bound for all n</td>
      <td>74</td>
    </tr>
    <tr>
      <td>3.3.1 Fourier analysis on the torus</td>
      <td>75</td>
    </tr>
    <tr>
      <td>3.3.2 Expansiveness</td>
      <td>76</td>
    </tr>
    <tr>
      <td>3.3.3 Symbolic Representations</td>
      <td>78</td>
    </tr>
    <tr>
      <td>3.3.4 Proof of Theorem 3.1</td>
      <td>79</td>
    </tr>
    <tr>
      <td>3.4 Irreducibility and aperiodicity</td>
      <td>86</td>
    </tr>
    <tr>
      <td>3.5 An upper bound for almost all n</td>
      <td>88</td>
    </tr>
    <tr>
      <td>3.6 Markov partitions</td>
      <td>90</td>
    </tr>
    <tr>
      <td>3.6.1 Hyperbolic dynamics</td>
      <td>91</td>
    </tr>
    <tr>
      <td>3.6.2 Markov Partitions</td>
      <td>92</td>
    </tr>
    <tr>
      <td><b>4 Concentration for low-degree functions on the symmetric group</b></td>
      <td><b>97</b></td>
    </tr>
    <tr>
      <td>4.1 Introduction</td>
      <td>97</td>
    </tr>
    <tr>
      <td>4.1.1 Main results</td>
      <td>97</td>
    </tr>
    <tr>
      <td>4.1.2 Related works</td>
      <td>100</td>
    </tr>
    <tr>
      <td>4.2 Control of the smoothness parameters</td>
      <td>101</td>
    </tr>
    <tr>
      <td>4.3 Proof of the concentration inequality</td>
      <td>103</td>
    </tr>
    <tr>
      <td>4.3.1 Induction with the method of exchangeable pairs</td>
      <td>103</td>
    </tr>
    <tr>
      <td>4.3.2 Almost sure bound on F</td>
      <td>108</td>
    </tr>
    <tr>
      <td>4.3.3 Tensor representation</td>
      <td>109</td>
    </tr>
    <tr>
      <td><b>5 Cutoff for mixtures of permuted Markov chains</b></td>
      <td><b>113</b></td>
    </tr>
    <tr>
      <td>5.1 Models and main results</td>
      <td>113</td>
    </tr>
    <tr>
      <td>5.1.1 Cutoff for mixtures of permuted Markov Chains</td>
      <td>113</td>
    </tr>
    <tr>
      <td>5.1.2 A reversible model</td>
      <td>116</td>
    </tr>
    <tr>
      <td>5.1.3 Related works</td>
      <td>118</td>
    </tr>
    <tr>
      <td>5.1.4 Proof outline</td>
      <td>120</td>
    </tr>
    <tr>
      <td>5.2 First moment argument, quasi-trees</td>
      <td>124</td>
    </tr>
    <tr>
      <td>5.2.1 Quenched vs annealed probability, first moment argument</td>
      <td>124</td>
    </tr>
    <tr>
      <td>5.2.2 The two-lift chain and half-integer time steps</td>
      <td>125</td>
    </tr>
    <tr>
      <td>5.2.3 The graph point of view</td>
      <td>126</td>
    </tr>
    <tr>
      <td>5.2.4 Quasi-trees</td>
      <td>128</td>
    </tr>
    <tr>
      <td>5.2.5 The covering quasi-tree</td>
      <td>130</td>
    </tr>
    <tr>
      <td>5.2.6 Random setting</td>
      <td>132</td>
    </tr>
    <tr>
      <td>5.2.7 Coupling and sequential generation</td>
      <td>133</td>
    </tr>
  </tbody>
</table>
<table><tbody><tr><td>5.3</td><td>The entropic method: main arguments</td><td>135</td></tr><tr><td>5.3.1</td><td>Nice trajectories</td><td>135</td></tr><tr><td>5.3.2</td><td>Concentration of drift and entropy</td><td>137</td></tr><tr><td>5.3.3</td><td>Concentration of nice paths</td><td>140</td></tr><tr><td>5.4</td><td>Counter-example to uniform entropic time</td><td>144</td></tr><tr><td>5.5</td><td>Quasi-tree I: Escape probabilities</td><td>146</td></tr><tr><td>5.5.1</td><td>Escape probabilities</td><td>147</td></tr><tr><td>5.5.2</td><td>Escape probabilities: reversible model</td><td>151</td></tr><tr><td>5.5.3</td><td>Escape probabilities: general model</td><td>154</td></tr><tr><td>5.5.4</td><td>General case: o(n) transient or close to transient states</td><td>162</td></tr><tr><td>5.6</td><td>Quasi-tree II: Markovian regeneration structure</td><td>164</td></tr><tr><td>5.6.1</td><td>Markov renewal processes</td><td>164</td></tr><tr><td>5.6.2</td><td>Regeneration structure</td><td>175</td></tr><tr><td>5.6.3</td><td>Mixing of the regeneration chain</td><td>182</td></tr><tr><td>5.7</td><td>Quasi-tree III: concentration of drift and entropy</td><td>186</td></tr><tr><td>5.7.1</td><td>Typical paths in quasi-trees</td><td>186</td></tr><tr><td>5.7.2</td><td>Concentration of the drift</td><td>189</td></tr><tr><td>5.7.3</td><td>Concentration of the entropy</td><td>192</td></tr><tr><td>5.8</td><td>First steps towards nice paths</td><td>199</td></tr><tr><td>5.8.1</td><td>The case of typical starting states</td><td>199</td></tr><tr><td>5.8.2</td><td>Bootstrapping annealed bounds with parallel chains</td><td>200</td></tr><tr><td>5.8.3</td><td>From o(1) to o(1/n) bounds</td><td>203</td></tr><tr><td>5.8.4</td><td>Nice paths from arbitrary states</td><td>204</td></tr><tr><td>5.9</td><td>Nice paths</td><td>207</td></tr><tr><td>5.9.1</td><td>Forward neighbourhood</td><td>207</td></tr><tr><td>5.9.2</td><td>Nice paths: definition</td><td>211</td></tr><tr><td>5.9.3</td><td>Nice paths are typical</td><td>213</td></tr><tr><td>5.9.4</td><td>Concentration of nice paths</td><td>216</td></tr><tr><td>5.9.5</td><td>Expectation of nice paths</td><td>221</td></tr></tbody></table>
# Résumé détaillé

Ce mémoire est la synthèse du travail réalisé lors de ma thèse. Il est basé sur trois articles qui explorent différents aspects de la théorie des chaînes de Markov : [30], réalisé avec Charles Bordenave, [65] réalisé avec Laurent Massoulié, et un troisième qui n'a pas encore été publié. Les chaînes de Markov sont des processus stochastiques qui n'ont pas de mémoire du passé. En tant que tel, ils sont le type de processus stochastique le plus simple avec une dépendance non triviale dans le temps et ont toujours été un objet central de la théorie des probabilités. Il existe de nombreuses références excellentes sur le sujet : les monographies de Durrett [66] et Norris [142] sont certainement un bon point de départ, avec de nombreux exemples et applications. Les livres de Levin, Peres et Wilmer [117] sur les temps de mélange, Aldous et Fill [6] et Lyons et Peres [128] sur les chaînes réversibles et sujets connexes sont d'autres pierres angulaires de la littérature, qui ont été largement utilisés lors de la réalisation de cette thèse. Nous considérons exclusivement des chaînes de Markov à temps discret avec un espace d'états discret. D'un point de vue général, notre étude des chaînes de Markov est motivée par la question d'identifier les mécanismes sous-jacents qui expliquent le comportement spécifique d'une chaîne. En particulier, nous essayons de comprendre les liens existant entre une chaîne de Markov et la géométrie de son espace d'états. Nos travaux tombent tous dans ce cadre général mais abordent des questions distinctes. Pour cette raison, nous essaierons ici de donner un aperçu concis de nos contributions et de donner des références générales. Chaque chapitre se verra plus tard consacré sa propre introduction ainsi qu'une revue de la littérature plus spécifiquement liée aux travaux présentés.

## Marches aléatoires sur les groupes

Le terme de marche aléatoire fait généralement référence à un type particulier de chaînes de Markov que l'on aime visualiser comme évoluant sur une structure géométrique comme un graphe. Dans cette catégorie, les marches aléatoires sur les groupes sont des chaînes de Markov qui présentent beaucoup de symétrie et qui apparaissent naturellement
ment dans divers problèmes théoriques et appliqués. La marche aléatoire simple sur une droite, peut-être la plus canonique des chaînes de Markov, est une marche aléatoire sur le groupe additif $\mathbb{Z}$. Les marches aléatoires sur les groupes sont la généralisation directe des sommes de variables aléatoires iid à des espaces plus généraux. Plus pré-cisément, étant donné un groupe $G$ équipé d'une mesure de probabilité $p$, considérons la chaîne de Markov $X = (X_t)_{t\ge0}$ sur $G$ définie par

$$ \forall g, h \in G, \forall t \ge 0: \mathbb{P}[X_{t+1} = h | X_t = g] = p(g^{-1}h). $$

De manière équivalente, $X_t$ peut être écrit comme le produit $X_t = Z_0Z_1...Z_t$ d' "increments" indépendants sur $G$ tous distribués avec la loi $p$, exceptée potentiellement $Z_0$. Une telle chaîne est appelée une marche aléatoire de convolution sur $G$, souvent abrégée simplement en marche aléatoire sur le groupe $G$.

Notre premier travail concerne plus spécifiquement le cas où le groupe $G$ est dénombrable et donné par un ensemble fini de générateurs $S$. Définissons le support de la marche aléatoire comme le support de la mesure $p$, c'est-à-dire l'ensemble des éléments qui ont une masse non nulle sous $p$. On dit que la marche aléatoire est de support fini, ou qu'elle a une portée finie, si la mesure $p$ est de support fini. C'est une marche aléatoire aux plus proches voisins si $p$ est supportée par l'ensemble des générateurs $S$.

La première contribution de cette thèse est motivée par l'observation générale que l'étude d'une marche aléatoire est souvent considérablement plus simple si elle est supposée être aux plus proches voisins. L'analyse du comportement asymptotique des marches aléatoires sur les groupes donne un bon exemple de ce que peuvent être les difficultés supplémentaires. Une grande partie de cette théorie remonte aux travaux de Furstenberg [76], Avez [12], Guivarc'h [82], Derriennic [54], Kaimanovich et Vershik [102]. L'une des caractéristiques essentielles des marches aléatoires de convolution est la transitivité : par le biais de la multiplication dans le groupe, l'état de départ de la marche aléatoire peut toujours être translaté vers l'élément neutre. Par conséquent, la loi de la marche est essentiellement indépendante du point de départ. A partir de cette observation, des théorèmes ergodiques tels que le théorème sous-additif de Kingman établissent l'existence des limites presque sûres

$$ v := \lim_{t \to \infty} \frac{|X_t|}{t}, \quad h := \lim_{t \to \infty} -\frac{\log \mathbb{P}[X'_t = X_t | X]}{t}. $$

sous condition que $\sum_{g \in G} p(g) |g| < \infty$ et où $X'$ dénote une copie indépendante de la chaîne. Étant donné $g \in G$, $|g|$ dénote ici le nombre minimal d'éléments nécessaires pour écrire $g$ comme un produit de générateurs. Cela peut être interprété comme une distance entre $g$ et l'élément d'identité. La quantité $v$ est pour cette raison appelée la vitesse, ou dérive, de la marche aléatoire. La limite $h$ est l'entropie asymptotique, ou
entropie d'Avez, nommée d'après Avez qui l'a introduite dans [12]. L'entropie asymptotique contient une grande partie de l'information sur le comportement asymptotique de la marche. Par exemple, Kaimanovich et Vershik [102] et Derriennic [54] ont prouvé que la σ-algèbre de queue de la marche aléatoire est non triviale si et seulement si $h > 0$.

Considérons maintenant le cas spécifique où $G = \mathbb{F}_d$ est le groupe libre sur $d$ générateurs. L'ensemble de générateurs considéré est celui des $d$ générateurs canoniques et de leurs inverses. Ce groupe peut être représenté par un graphe, son graphe de Cayley, qui n'est rien d'autre qu'un arbre régulier de degré $2d$. Une marche aléatoire générale peut faire des sauts arbitrairement grands dans cet arbre, une marche à support fini fait des sauts bornés, tandis qu'enfin une marche aux plus proches voisins se déplace uniquement le long des arêtes. Cette dernière propriété, couplée à la structure de l'arbre, est extrêmement utile : pour atteindre un sommet $y$ dans l'arbre à partir d'un sommet $x$, la marche doit passer par tous les sommets intermédiaires. Cela ouvre la voie à des arguments de récurrence, à partir desquels il est possible d'obtenir des formules explicites pour la vitesse et l'entropie de la marche [114]. Dans le cas général d'un support fini, de tels arguments échouent, et pour cette raison, aucune formule explicite ne semblait réalisable.

Dans notre travail, nous introduisons une nouvelle technique de "linéarisation" pour étudier les marches aléatoires sur les groupes qui permet de se ramener au cas de marches aux plus proches voisins. Le nom "linéarisation" vient de l' "astuce de linéarisation" utilisée notamment en algèbres d'opérateurs, de laquelle notre travail s'inspire [89, 83]. Le prix à payer pour ne considérer que le cas de marches aux plus proches voisins est que la chaîne de Markov résultante n'est pas une marche aléatoire sur un groupe mais une chaîne de Markov un peu plus générale que nous appelons une marche aléatoire colorée. En partant d'une marche aléatoire à support fini sur un groupe $G$, la technique de linéarisation amène à étudier une chaîne de Markov sur $G \times [r]$ pour un certain entier $r \ge 1$. Cette nouvelle chaîne hérite d'une certaine forme de transitivité dans la coordonnée du groupe, ce qui lui assure suffisamment de structure pour appliquer essentiellement les mêmes arguments que pour les marches aléatoires classiques sur les groupes. Plus précisément, une marche aléatoire colorée $Y = (Y_t)_{t \ge 0}$ sur $G \times [r]$ est définie par un ensemble de matrices $(p_g)_{g \in G}$ de taille $r \times r$ à coefficients positifs telles que $\sum_{g \in G} p_g$ est stochastique et pour tous $g, h \in G, u, v \in [r]$,

$$ \mathbb{P}[Y_{t+1} = (h, v) : | Y_t = (g, u)] = p_{g^{-1}h}(u, v). $$

Le cas $r = 1$ correspond à une marche aléatoire classique sur un groupe. Nous appelons ces chaînes des marches aléatoires colorées car nous interprétons la deuxième coordonnée comme une couleur qui change à mesure que la marche évolue sur le groupe
G. Notre contribution en ce qui concerne les chaînes de Markov colorées est double. D'abord, nous donnons des procédures explicites de linéarisation pour étudier les marches aléatoires à support fini au moyen de marches colorées aux plus proches voisins. Le principe de base est très simple : les grands sauts effectués par les marches à support fini sont divisés en plusieurs étapes individuelles. L'ajout d'une coordonnée de couleur permet ensuite de déterminer à quelle étape du grand saut se trouve la chaîne. Deuxièmement, nous donnons un exemple illustrant comment les marches aléatoires colorées peuvent être étudiées de manière similaire aux marches classiques. Cet exemple consiste en l'analyse des propriétés asymptotiques de la marche à support fini au moyen de la théorie ergodique. Nous obtenons ainsi des formules explicites pour la vitesse et l'entropie des marches à support fini sur les groupes libres et le produit libre de groupes finis, qui n'étaient disponibles jusqu'à présent que dans le cas de marches aux plus proches voisins.

## Accélération de chaînes de Markov

La théorie des temps de mélange trouve son origine dans le résultat fondamental selon lequel les chaînes de Markov, sous certaines hypothèses facilement réalisées, convergent en loi vers un état d'équilibre. Un exemple populaire est donné par les mélanges de cartes : il semble intuitif que plus un paquet de cartes est battu, mieux il sera mélangé. Mais combien de battages sont réellement nécessaires ? Les temps de mélange fournissent des réponses rigoureuses à cette question, dans un contexte beaucoup plus large. Cette question est également d'importance pratique, au cœur des méthodes dites de Monte Carlo par chaînes de Markov (MCMC).

Le cadre formel est le suivant : soit $X = (X_t)_{t \ge 0}$ une chaîne de Markov sur un espace d'états fini ou dénombrable. Supposons que $X$ est récurrente positive, irréductible et apériodique. $X_t$ converge alors en distribution vers l'unique mesure invariante de $X$. L'étude des temps de mélange vise à préciser la convergence en quantifiant le temps nécessaire pour atteindre la distribution stationnaire. Pour quantifier la convergence, une mesure doit être choisie sur l'ensemble des mesures de probabilité. La distance la plus couramment considérée est la distance en variation totale : étant donné deux mesures de probabilité $\mu, \nu$ sur un ensemble dénombrable $S$, on définit leur distance en variation totale par

$$ \|\mu - \nu\|_{\text{TV}} := \sup_{A \subseteq S} |\mu(A) - \nu(A)|. $$

La convergence peut ainsi être quantifiée par le temps nécessaire pour que la distance passe en dessous d'un certain seuil. Etant donné $P$ le noyau de transition de la chaîne,
<figure><img src="image_5.png" /><figcaption>Figure 1: Le phénomène de cutoff.</figcaption></figure>

$\epsilon \in (0, 1)$ et un état initial $x \in S$, on définit le temps de mélange $t_{\text{mix}}(x, \epsilon)$ par

$$t_{\text{mix}}(x, \epsilon) := \inf \{ t \ge 0 : \| P^t(x, \cdot) - \pi \|_{\text{TV}} \le \epsilon \}.$$

On considère souvent l'état de départ le plus défavorable qui maximise le temps de mélange, ce qui conduit à considérer

$$t_{\text{mix}}(\epsilon) := \max_{x \in S} t_{\text{mix}}(x, \epsilon).$$

Lorsqu'il est enseigné dans un cours d'introduction sur les chaînes de Markov, le théorème de convergence est souvent démontré pour les chaînes finies en établissant une convergence exponentielle vers l'équilibre : supposant que $S$ est fini, il existe $\alpha \in [0, 1)$ et $C > 0$ tels que

$$\max_{x \in S} \| P^t(x, \cdot) - \pi \|_{\text{TV}} \le C\alpha^t.$$

De cette inégalité, il peut être tentant de penser que la convergence est toujours exponentiellement rapide et que la notion de temps de mélange n'est en fin de compte pas si décisive. Ce serait une grave erreur. Alors que la convergence est en effet exponentielle asymptotiquement, elle semble souvent loin d'être exponentielle en pratique lorsque l'on se restreint à un intervalle de temps fini. Dans certains cas, la distance peut même diminuer comme une sorte de fonction seuil, comme celle illustrée dans la figure 1 : c'est le phénomène de cutoff, dont nous discuterons plus tard. Dans bien des cas, la chaîne de Markov étudiée dépend d'un paramètre qui mesure la taille ou la dimension de l'espace d'états. De telles chaînes de Markov sont par exemple la marche aléatoire simple sur un graphe à $n$ sommets, sur l'hypercube $n$-dimensionnel, le mélange d'un paquet de $n$ cartes, etc. À cet égard, il est crucial de comprendre comment les temps de mélange évoluent avec ce paramètre $n$. La question porte ainsi principalement sur l'obtention de développements asymptotiques des temps de mélange lorsque $n \to \infty$. Nous renvoyons à [117] et [136] pour des références sur les temps de mélange des chaînes de Markov finies.
Nous passons maintenant plus précisément au sujet de notre deuxième travail, qui porte sur l'accélération des chaînes de Markov. Ce sujet est motivé par des questions très pratiques dans le domaine des méthodes de Monte Carlo par chaînes de Markov (MCMC) [148, 147]. Les méthodes MCMC sont une classe de schémas d'échantillonnage basé sur la convergence des chaînes de Markov. Dans de nombreux cas pratiques, la distribution de probabilité cible est trop complexe sur le plan computationnel pour être réalisée directement. Ce problème se pose particulièrement dans le contexte de la simulation de modèles probabilistes en physique statistique [131] ou en statistiques bayésiennes [139] : dans ces contextes, les états consistent généralement en des configurations de haute dimension modélisées par des distributions de Gibbs : une configuration est dans l'état $\psi$ avec une probabilité définie à une constante de normalisation près par

$$ \mathbb{P}[\psi] \propto e^{-H(\psi)} $$

où $H(\psi)$ est l'énergie de la configuration. La probabilité d'une configuration peut donc être calculée à une constante de normalisation de près, la fonction de partition, tandis que l'estimation de celle-ci nécessite un nombre important de calculs, bien trop grand pour être réalisé numériquement. Les méthodes MCMC tentent de contourner cette difficulté en exploitant la convergence des chaînes de Markov vers une mesure stationnaire : afin d'échantillonner selon une distribution de probabilité cible $\pi$, l'idée est d'échantillonner plutôt une chaîne de Markov ayant $\pi$ comme mesure invariante et d'attendre que la chaîne converge vers son équilibre. Dans le cas des distributions de Gibbs, la nature locale des phénomènes généralement impliqués permet de concevoir des chaînes qui contournent le problème du calcul de la constante de normalisation : c'est l'échantillonneur de Gibbs, également appelé dynamique de Glauber dans le cas des systèmes de spins. Même dans des contextes plus généraux, trouver une chaîne de Markov avec une mesure invariante prescrite est en théorie résolu par l'algorithme de Metropolis-Hastings [134, 86], (voir aussi [55] et [117, Chapitre 3]). Cependant, la convergence pour de nombreux cas d'intérêt est souvent trop lente pour être utilisée en pratique. Il faut donc concevoir de nouvelles chaînes spécifiquement adaptées au problème à résoudre. Une autre option consiste à essayer d'améliorer les dynamiques déjà disponibles : c'est l'accélération des chaînes de Markov. Nous renvoyons à l'article [58] de Diaconis pour une introduction au sujet. De nombreuses méthodes d'accélération consistent à donner une certaine inertie à la chaîne, ce qui signifie en pratique considérer des chaînes non réversibles sur des espaces d'états augmentés, voir [47, 60, 7, 140] et les références qui y sont citées. Ces mécanismes d'accélération sont commun à ceux proposés pour les algorithmes d'optimisation et de passage de messages [146].

Dans notre travail, nous nous concentrons sur un mécanisme d'accélération quelque
peu étonnant, qui consiste à insérer des étapes d'une dynamique déterministe entre celles de la chaîne de Markov. L'accélération résultante est spectaculaire : pour une chaîne de Markov générale, le temps de mélange peut être réduit jusqu'à devenir logarithmique en la taille de l'espace d'états en prenant pour la dynamique déterministe une application bijective choisie... au hasard. Ce résultat est dû à Chatterjee et Diaconis [45], mais l'histoire ne commence pas là. L'accélération par une application déterministe a été identifiée pour la première fois par Chung, Diaconis et Graham [49] dont la motivation était d'étudier le temps de mélange d'un processus apparaissant dans la génération de nombres pseudo-aléatoires. Leur modèle consiste en la chaîne de Markov $X$ sur $\mathbb{Z}/n\mathbb{Z}$ définie par l'équation de récurrence : $X_{t+1} = aX_t + B_t$, avec $(B_t)$ une suite d'incréments iid uniformément distribués sur $\{-1, 0, 1\}$. Pour $a = 2$, ils ont prouvé qu'après $t = O(\log n \log \log n)$ étapes, la distribution de $X_t$ est proche de l'uniforme, ce qui montre déjà une accélération considérable par rapport à la marche aléatoire simple : cette dernière, obtenue avec $a = 1$, est connue pour mélanger en environ $n^2$ étapes. Ce n'est pas l'accélération promise en $O(\log n)$ étapes, mais Chung, Diaconis et Graham prouvent aussi que pour "la plupart des suites de $n$", le temps de mélange est en fait vraiment de l'ordre de $\log n$.

Le phénomène d'accélération de chaînes de Markov par des fonctions déterministes a été récemment remis au goût du jour. Dans [45], Chatterjee et Diaconis considèrent le modèle suivant : soit $P$ une matrice stochastique sur $[n]$ et $S$ la matrice d'une permutation de $n$ éléments uniformément distribués sur le groupe symétrique. Sous des hypothèses peu contraignantes, les auteurs prouvent que le temps de mélange de la chaîne de matrice de transition $PS$ est $O(\log n)$ avec grande probabilité. Cependant, ils notent également que des exemples explicites sont particulièrement difficiles à trouver. Dans notre travail, nous étudions un analogue multidimensionnel du processus de Chung-Diaconis-Graham : nous considérons une chaîne $X$ sur $(\mathbb{Z}/n\mathbb{Z})^d$, $d \ge 1$ définie par l'équation de récurrence :

$$X_0 := 0 \quad X_t = AX_{t-1} + B_t \quad \mod n \quad \forall t \ge 1$$

Ici $A \in \text{GL}_d(\mathbb{Z})$ est une matrice hyperbolique inversible, par quoi nous entendons que $A$ est inversible, son inverse a des coefficients entiers et $A$ n'a pas de valeur propre de module 1, tandis que les variables $B_t$ sont des variables aléatoires iid sur $\mathbb{Z}^d$ distribuées selon une loi $\mu$. De tels cas multidimensionnels ont été précédemment étudiés par Asci [8, 9], Hildebrand [100] et Klyachko [106] qui ont prouvé une accélération en $O((\log n)^2)$ étapes sous de faibles hypothèses sur $\mu$. Notre contribution est d'établir des limites similaires au cas unidimensionnel : nous obtenons un mélange en $O(\log n \log \log n)$ étapes et même $O(\log n)$ étapes pour "la plupart des suites de $n$". De plus, nous sug-
gérons une piste sur la manière de construire des applications explicites à l'origine d'une accélération : notre preuve est basée sur les propriétés de la dynamique déterministe $x \mapsto A^\top x$ sur le tore continu $(\mathbb{R}/\mathbb{Z})^d$, qui est connue pour présenter un comportement chaotique. Nous suggérons donc que l'accélération est dans ce cas à expliquer par le comportement pseudo-aléatoire de la dynamique déterministe, et que d'autres exemples pourraient potentiellement être obtenus de cette manière.

## Concentration sur le groupe symétrique

L'une des lois fondamentales de la théorie des probabilités, la loi des grands nombres, affirme que la moyenne empirique d'une famille de variables aléatoires iid converge vers son espérance. Il s'agit d'une instance du phénomène de concentration de mesure : des fonctions qui dépendent de manière régulière d'un grand nombre de variables aléatoires indépendantes ont tendance à se comporter de manière déterministe et à concentrer autour de leur moyenne. La concentration de la mesure est devenue un aspect central de la théorie des probabilités moderne, nous renvoyons aux monographies de Ledoux [111] et Boucheron, Lugosi et Massart [34] pour une introduction au sujet. Souvent, le terme de concentration de la mesure se réfère de manière plus précise à l'utilisation d'inégalités de concentration, qui quantifient à quel point une fonction donnée est proche de sa moyenne. Le phénomène de concentration de la mesure a également une forte teinte géométrique : dans le cas de variables aléatoires indépendantes, au lieu d'interpréter la concentration comme la propriété de nombreuses variables aléatoires interagissant entre elles, on peut la voir comme la propriété d'une mesure (la mesure produit) sur un espace de grande dimension (un espace produit). Le phénomène de concentration de la mesure va donc bien au-delà du monde des variables aléatoires indépendantes. Notre travail sur le phénomène de cutoff, présenté dans la section suivante, nous a amenés à considérer un tel problème de concentration de mesure pour la mesure uniforme sur le groupe symétrique. Les phénomènes de concentration pour les groupes et plus généralement pour les variables aléatoires faiblement dépendantes ont été étudiés par Chatterjee dans sa thèse de doctorat [41, 43, 42], qui a développé des techniques pour obtenir des inégalités de concentration basées sur la méthode de Stein. Parmi ces travaux, Chatterjee a établi une inégalité de type Bernstein pour la mesure uniforme sur le groupe symétrique qui peut être énoncée comme suit : soit $A \in M_n(\mathbb{R}_+)$ une matrice à coefficients positifs, $\sigma \in S_n$ une permutation uniforme et considérons la variable aléatoire

$$Z = \sum_i A_{i\sigma(i)}.$$
Pour tout $t \ge 0$

$$ \mathbb{P}[|Z - \mathbb{E}[Z]| \ge t] \le 2 \exp\left(\frac{-t^2}{2 \|A\| (t + 2\mathbb{E}[X])}\right), $$

où $\|A\| = \max_{i,j \in [n]} A_{i,j}$.

La variable aléatoire Z peut être vue comme provenant d'une fonction linéaire sur le groupe symétrique, en ce sens qu'elle est une combinaison linéaire d'indicatrices $S_{ij} := \mathbb{1}_{\sigma(i)=j}$, qui sont les coefficients de la matrice de permutation S. Dans notre travail, nous proposons une version d'ordre supérieur de ce résultat, c'est-à-dire une inégalité de concentration pour des variables aléatoires qui s'écrivent comme des polynômes réguliers et de faible degré en les entrées de S. Si notre point de départ a été la représentation des polynômes de degré supérieur comme des applications linéaires sur des produits tensoriels d'espaces vectoriels (ce qui constitue une autre astuce de linéarisation) le résultat final ne nécessite pas l'introduction d'une matrice A. Au lieu de cela, nous considérons directement des fonctions $\phi$ sur l'espace des matrices réelles $M_n(\mathbb{R})$ de taille $n \times n$. Comme les fonctions doivent être appliquées à des matrices de permutation, certaines contraintes peuvent être imposées, comme le fait que le degré est au plus un en chaque entrée. Il est cependant crucial que les coefficients du polynôme soient positifs. Pour une telle fonction polynômiale $\phi$ et S la matrice d'une permutation uniforme, le théorème 4.1 établit une inégalité de concentration qui prend la forme d'une inégalité de Bernstein similaire à l'inégalité unidimensionnelle ci-dessus. Le paramètre de régularité qui joue le rôle de $\|A\|$ ayant une expression plus complexe, nous ne tenterons pas de donner une déclaration plus précise ici. Ce paramètre de régularité fait intervenir le degré ainsi que la norme $\ell^\infty$ du gradient de $\phi$, mais nécessite également la considération de fonctions auxiliaires dont les degrés s'échelonnent jusqu'à celui de $\phi$. Il s'agit d'une conséquence de la preuve, basée sur une récurrence sur le degré. S'inspirant de la méthode de Chatterjee, la preuve consiste in fine à prouver une borne supérieure sur la fonction génératrice des moments. En utilisant une représentation tensorielle linéaire de la fonction polynomiale, la méthode de Stein des paires échangeables aboutit à une formule de récurrence sur la fonction génératrice des moments à partir de laquelle une borne supérieure est obtenue par récurrence.

## Le phénomène de cutoff

Découvert par Diaconis, Shahshahani et Aldous [61, 4, 5], le phénomène de cutoff est une caractéristique étonnante observée dans un grand nombre de chaînes de Markov, qui consiste en une convergence abrupte vers l'équilibre. La définition formelle est la suivante. Comme d'habitude lorsque l'on considère le temps de mélange d'une chaîne de Markov, on considère en réalité une famille de chaînes de Markov indexée par un
entier $n$. La chaîne présente le phénomène de cutoff si pour tout $\varepsilon \in (0, 1)$, son temps de mélange satisfait

$$ \frac{t_{\text{mix}}(\varepsilon)}{t_{\text{mix}}(1-\varepsilon)} \xrightarrow[n \to \infty]{} 1. $$

La chaîne de Markov la plus simple à présenter le phénomène de cutoff est peut-être la marche aléatoire simple sur l'hypercube $n$-dimensionnel $\{0, 1\}^n$, qui a été démontrée avoir un cutoff au temps $\frac{1}{4}n \log n$ pour sa version continue par Aldous. Des exemples historiques incluent le célèbre processus des transpositions aléatoires dont le cutoff au temps $\frac{1}{2}n \log n$ a été prouvé par Diaconis et Shahshahani [61], ou le mélange américain (riffle shuffle), modélisé par Gilbert-Shannon et Reeds. Aldous [4] a d'abord établi le cutoff au temps $\frac{3}{2}n \log n$, après quoi une analyse plus approfondie a été menée par Bayer et Diaconis [15]. De leur travail découle le résultat quelque peu informel mais immensément populaire selon lequel un jeu de 52 cartes doit être mélangé exactement 7 fois avec le battage américain pour être bien mélangé. On pense que le phénomène de cutoff est une caractéristique très courante des chaînes de Markov et aujourd'hui de nombreux exemples soutiennent cette croyance. Pour n'en nommer que quelques-uns, le cutoff a été établi pour de nombreuses marches aléatoires sur des groupe finis, pour lesquelles nous renvoyons à [57, 150, 48], les chaînes de naissance et de mort [63], le modèle de Bernoulli-Laplace [62, 70, 3], certaines dynamiques de Glauber pour des systèmes de spin, en particulier pour le modèle d'Ising à haute température [116, 64, 123, 124], certains systèmes de particules en interaction unidimensionnels, pour lesquels nous renvoyons à l'article de Lacoin [108] et à la thèse de doctorat de Schmid [151].

Cependant, toutes les chaînes de Markov ne présentent pas de cutoff : c'est le cas par exemple des chaînes de faible dimension que sont les marches aléatoires simples sur une grille ou un tore (cela peut être prouvé grâce à la condition de produit donnée après). La question centrale des recherches sur le phénomène de cutoff est ainsi celle de déterminer une caractérisation simple du cutoff. Idéalement, une bonne caractérisation devrait être assez simple pour éviter le calcul précis du temps de mélange, ne nécessitant de connaître que l'ordre du terme dominant. À ce jour, nous ne disposons pas de telle caractérisation mais d'importants progrès ont été réalisés. Une condition nécessaire connue pour les chaînes réversibles est la condition de produit. Une chaîne de matrice de transition $P$ et mesure invariante $\pi$ est réversible si elle satisfait l'équation

$$ \pi(x)P(x, y) = \pi(y)P(y, x) $$

pour tous les états $x, y$. Soit $\lambda_*$ la valeur propre de $P$ de valeur absolue maximale mais distincte de la valeur propre triviale 1. On définit le *trou spectral absolu* comme $\gamma := 1 - \lambda_*$ et le temps de relaxation $t_{\text{rel}} := \gamma^{-1}$. La condition de produit est la propriété
que pour tout $\varepsilon \in (0, 1)$,

$$ \frac{t_{\text{mix}}(\varepsilon)}{t_{\text{rel}}} \xrightarrow[n \to \infty]{} \infty. $$

La condition de produit a d'abord été conjecturée être une équivalence, mais il existe des contre-exemples, comme [117][Example 18.7]. Une autre caractérisation de cutoff a été établie par Basu, Hermon et Peres dans [14] pour les chaînes réversibles en termes de temps d'atteintes, mais elle nécessite le calcul précis du temps de mélange.

La compréhension du phénomène a fait d'importants progrès lorsque l'attention s'est portée vers le cas de chaînes génériques. Ce changement a été initié par le travail fondateur de Lubetzky et Sly [122] établissant le cutoff pour les marches aléatoires sur des graphes réguliers aléatoires. Comme ces chaînes n'ont pas de probabilités de transition fixes et connues à l'avance, la stratégie de preuve ne peut pas s'appuyer sur une connaissance explicite de la matrice de transition, comme c'était le cas pour les travaux précédemment cités. Au lieu de cela, le résultat s'appuie sur un phénomène de concentration entropique. Une heuristique peut être décrite comme suit : idéalement l'objectif est de prouver l'existence d'une constante $h > 0$ telle que $-\log P^t(X_0, X_t)$ se concentre autour de $th$, pour tous les temps $t$ jusqu'au temps de mélange. Si cela est vrai, cette propriété implique que $X_t$ est essentiellement uniformément distribuée sur un ensemble de taille $e^{th}$. À condition que la mesure invariante de $X_t$ soit suffisamment dispersée dans l'espace des états, comme c'est le cas par exemple pour la mesure uniforme, cela implique immédiatement que $\log n/h$ étapes sont nécessaires, mais aussi suffisantes pour le mélange. Depuis les travaux de Lubetzky et Sly, la méthode entropique a donné lieu à une longue lignée de papiers établissant le cutoff pour des chaînes génériques au temps entropique $\log n/h$. À partir de ces travaux, que nous présentons dans le Chapitre 5, une percée récente a été faite par Salez [149] qui a donné une condition suffisante de cutoff s'exprimant en termes de concentration entropique. Similaire à la condition de produit ci-dessus, elle peut en théorie être vérifiée sans la connaissance précise du temps de mélange. De cela, Salez déduit le cutoff pour une large famille de chaînes satisfaisant une hypothèse de courbure non négative.

La dernière de nos contributions présentées dans cette thèse s'inspire du papier de Hermon, Sly et Sousi [92] dont l'objet d'étude est la marche aléatoire simple sur les graphes auxquels sont rajoutés des arêtes aléatoires correspondant à un appariement uniforme des sommets. Sous des hypothèses faibles sur la suite de graphes, la marche aléatoire simple présente un cutoff au temps entropique. Notre travail dans le domaine du cutoff est une tentative de généraliser ce modèle à des chaînes plus générales. En partant de deux matrices stochastiques déterministes $P_1, P_2$ sur $[n]$, nous étudions les propriétés de mélange d'une combinaison aléatoire de $P_1$ et $P_2$: en notant $S$ la matrice d'une permutation uniforme $\sigma$ et $p \in (0, 1)$, nous analysons le mélange de la chaîne de
matrice de transition

$$ \mathcal{P} = pP_1 + (1-p)SP_2S^{-1}. $$

En réalité, nous étudions un modèle légèrement plus général où nous permettons à la probabilité $p$ de dépendre de l'état actuel $x$ de la chaîne et de son image $\sigma(x)$. Cette généralisation est nécessaire pour inclure le cas de marches aléatoires sur une superposition de graphes. En particulier, en prenant pour $P_1, P_2$ les matrices de la marche aléatoire simple sur un graphe et sur une famille d'arêtes respectivement, un bon choix de $p$ redonne le modèle de Hermon, Sly et Sousi. Nous prouvons un phénomène de cutoff au temps entropique dans le sens suivant : nous établissons que dans notre modèle, il existe une mesure $\pi$ telle que pour tous $\varepsilon \in (0, 1)$, $t = \log n/h + a_n\sqrt{\log n}$, pour tout point de départ $x \in [n]$, la chaîne est avec une grande probabilité à une distance au moins $1 - \varepsilon$ en variation totale de la mesure $\pi$ si $a_n \to -\infty$, et est sinon $\varepsilon$-proche de $\pi$ si $a_n \to +\infty$ et $t = O(\log n)$. Nous conjecturons que la mesure limite $\pi$ est elle-même $\varepsilon$-proche d'une vraie mesure invariante, ce qui permettrait d'en déduire des estimations de temps de mélange correspondantes. Malheureusement, au moment où cette thèse est écrite, cette conjecture fait encore l'objet de recherches actives. Le problème principal vient du fait que la propriété de mélange ne vaut que pour un point de départ typique : l'état initial de la chaîne doit être fixé avant de générer l'environnement ou peut être choisi uniformément au hasard, mais ne peut pas être choisi arbitrairement après que l'environnement a été généré.
# Chapter 1

## Introduction

This dissertation is the synthesis of the work achieved during my thesis. It is based on three papers that explore different aspects of the theory of Markov chains: [30], done jointly with Charles Bordenave, [65] done jointly with Laurent Massoulié, and a third one that has not been published yet. Markov chains are stochastic processes that have no memory of the past. As such, they are the simplest kind of stochastic processes with a non-trivial dependence in time and for this reason have always been a central object in probability theory. There exists many excellent references on the subject: the monographs of Durrett [66] and Norris [142] are certainly a good place to start, with many examples and applications. The books by Levin, Peres and Wilmer [117] on mixing times, Aldous and Fill [6] and Lyons and Peres [128] on reversible chains and related topics are other cornerstones of the literature, which have been used extensively during the realization of this thesis. We consider exclusively discrete-time Markov chains with discrete state space. From a general perspective, our study of Markov chains is motivated by the question of identifying the underlying mechanisms that account for the specific behaviour of a chain. In particular, we are especially interested in understanding the relation between the chain and the geometry of its state space. Our works all fall in that general setting but tackle distinct questions. For this reason, we will try to give here a concise overview of our contributions and give general references. Then each chapter will be dedicated a proper introduction and review of the literature more specifically related with our works.

### 1.1 Random walks on groups

The term random walks generally refers to a particular kind of Markov chains that one likes to visualize as evolving on a geometric structure like a graph. Within this category, random walks on groups are Markov chains that exhibit a lot of symmetry
and arise naturally in various theoretical and applied problems. The simple random walk on the line, perhaps the most canonical of Markov chains, is a random walk on the additive group $\mathbb{Z}$. Random walks on groups are the direct generalization of sums of iid random variables to more general spaces. Specifically, given a group $G$ equipped with a probability measure $p$, consider the Markov chain $X = (X_t)_{t \ge 0}$ on $G$ defined by

$$ \forall g, h \in G, \forall t \ge 0: \mathbb{P}[X_{t+1} = h | X_t = g] = p(g^{-1}h). $$

Equivalently, $X_t$ can be written as the product $X_t = Z_0Z_1...Z_t$ of independent "increments" on $G$ all distributed with law $p$, except potentially $Z_0$. Such a chain is called a convolution random walk on $G$, often abreviated as simply ranndom walk on the group $G$.

Our first work is concerned more specifically with the case where the group $G$ is countable and given by a finite set of generators $S$. Define the support of the random walk as the support of the measure $p$, that is the set of elements that have positive mass under $p$. The random walk is said to be finitely supported, or to have finite range, if the measure $p$ is finitely supported. It is a nearest-neighbour random walk if $p$ is supported on the set of generators $S$.

The first contribution of this thesis is motivated by the general observation that the study of a random walk is often considerably simpler if it is supposed to be nearest-neighbour. The analysis of the asymptotic behaviour of random walks on groups gives good example of what the difficulties can be. A large part of this theory can be traced back to the work of Furstenberg [76], Avez [12], Guivarc'h [82], Derriennic [54], Kaimanovich and Vershik [102]. One of the essential features of convolution random walks is transitivity: by means of group multiplication, the starting state of the random walk can always be translated to the identity element. Consequently, the law of the walk is essentially independent of the starting point. From this observation, ergodic theorems such as Kingman's subadditive theorems establish the existence of the almost sure limits

$$ v := \lim_{t \to \infty} \frac{|X_t|}{t}, \quad h := \lim_{t \to \infty} -\frac{\log \mathbb{P}[X'_t = X_t] X}{t}. $$

provided $\sum_{g \in G} p(g) |g| < \infty$ and where $X'$ denotes an independent copy of the chain. Given $g \in G$, $|g|$ denotes here the minimal number of elements that are needed to write $g$ as a product of generators. This can be interpreted as a distance between $g$ and the identity element. The quantity $v$ is for this reason called the speed, or drift, of the random walk. The limit $h$ is the asymptotic entropy, or Avez entropy, named after Avez who introduced it in [12]. The asymptotic entropy contains much of the information about the asymptotic behaviour of the walk. For instance Kaimanovich and Vershik
[102] and Derriennic [54] proved that the tail $\sigma$-algebra of the random walk is non-trivial if and only $h > 0$.

Consider now the specific case where $G = \mathbb{F}_d$ is the free group on $d$ generators. The generating set considered is that of the $d$ canonical generators and their inverses. This group can be represented by a graph (its Cayley graph), which is nothing but a $2d$-regular tree. A general random walk can make arbitrarily large jumps in this tree, a walk with finite support makes bounded jumps, while finally a nearest-neighbour moves along the edges only. This last property coupled with the tree structure is extremely useful: to reach a vertex $y$ in the tree from a vertex $x$, the walk has to go through all vertices in between. This paves the way for recurrence arguments, from which it is possible to get explicit formulas for the drift and entropy of the walk [114]. In the finite support case, such arguments fail, and for this reason no explicit formulas seemed achievable.

In our work we introduce a novel technique to study random walks on groups which allows to reduce to the nearest-neighbour case. The name "linearization" comes from the so-called "linearization trick" used notably in operator algebras, where our works finds its inspiration [89, 83]. The price to pay for considering only the nearest-neighbour case is that the resulting Markov chain is not a random walk on a group but a slightly more general Markov chain which we call a colored random walk. Basically, starting from a random walk with finite support on a group $G$, we will be left to study a Markov chain on $G \times [r]$, for some integer $r \ge 1$. The new Markov chains inherits some transitivity property in the group coordinate from the starting walk, so it keeps sufficient structure to apply the arguments for classical random walks on groups. Namely, a colored random walk $Y = (Y_t)_{t \ge 0}$ on $G \times [r]$ is defined by a set of $r \times r$ matrices $(p_g)_{g \in G}$ with non-negative entries such that $\sum_{g \in G} p_g$ is stochastic and for all $g, h \in G, u, v \in [r]$,

$$ \mathbb{P}[Y_{t+1} = (h, v) | Y_t = (g, u)] = p_{g^{-1}h}(u, v). $$

The case $r = 1$ corresponds to a classical random walk on a group. We call such chains colored random walks because we interpret the second coordinate as a color that changes as the walk evolves on the group $G$. Our contribution in regard to colored Markov chains are twofold. First we give explicit procedures to study finitely supported random walks by means of nearest-neighbour colored walks. The basic principle is very simple: large jumps made by finitely supported walks are splitted into several individual steps. The addition of a color coordinate then allows to determine what stage of a large jump the chain is at. Secondly we give an example of how colored random walks can be studied in essentially the same manner as classical walks. This example consists in the
analysis of asymptotic properties of finitely supported walk by means of ergodic theory. From this we obtain explicit formulas for the drift and entropy of finitely supported walks on free groups and free product of finite groups, which were so far only available in the nearest-neighbour case.

## 1.2 Acceleration of Markov chains

The theory of mixing times originates from the fundamental result that Markov chains, under mild assumptions, converge in distribution to an equilibrium state. A popular example of this is given by card shuffles: it seems intuitive that the more shuffles are performed, the better mixed the deck will be. But how many shuffles are really needed? Mixing times provide rigorous answers this question, in a much broader context. This question is also of practical importance, at the core of the so-called Markov Chain Monte Carlo (MCMC) methods.

The formal setting is as follows: let $X = (X_t)_{t \ge 0}$ be a Markov chain on a finite or countable state space. Assume $X$ is positive recurrent, irreducible and aperiodic. Then $X_t$ converges in distribution towards the unique invariant measure of $X$. The study of mixing times aims to make the convergence more precise by quantifying the time needed to reach the stationary distribution. To quantify the convergence, a metric needs to be chosen on the set of probability measures. The metric most commonly considered is the total variation distance: given two probability measures $\mu, \nu$ on a countable set $S$, define their total variation distance as

$$ \|\mu - \nu\|_{\text{TV}} := \sup_{A \subseteq S} |\mu(A) - \nu(A)|. $$

Convergence can thus be quantified by the time necessary for the distance to pass below a given threshold. Letting $P$ denote the transition kernel of the chain, $\varepsilon \in (0, 1)$ and a starting state $x \in S$, define the mixing time $t_{\text{mix}}(x, \varepsilon)$ as

$$ t_{\text{mix}}(x, \varepsilon) := \inf\{t \ge 0 : \|P^t(x, \cdot) - \pi\|_{\text{TV}} \le \varepsilon\}. $$

One often considers the worst possible starting state which maximizes the mixing time, leading to the consideration of

$$ t_{\text{mix}}(\varepsilon) := \max_{x \in S} t_{\text{mix}}(x, \varepsilon). $$

When taught in an introductory course about chains, the convergence theorem is often prouved for finite chains by establishing uniform ergodicity, which asserts exponential convergence to equilibrium: assuming $S$ is finite there exists $\alpha \in [0, 1)$ and $C > 0$ such that

$$ \max_{x \in S} \|P^t(x, \cdot) - \pi\|_{\text{TV}} \le C\alpha^t. $$
<figure><img src="image_6.png" /><figcaption>Figure 1.1: The cutoff phenomenon.</figcaption></figure>

From this equation, it may be tempting to think that convergence is always exponentially fast and the notion of mixing times not so decisive after all. This would be a fatal mistake. While the convergence is indeed exponential asymptotically, it often looks far from being exponential in practice when one restricts to a finite interval of time. In some cases, the distance can even decrease as some kind of a step function, as in Figure 1.1: this is the cutoff phenomenon, discussed later. In most cases of interest, the Markov chain depends on a parameter that measures the size or dimension of the state space. Such Markov chains are for instance the simple random walk on graphs with $n$ vertices, on the $n$-dimensional hypercube, shuffles of a deck of $n$ cards, etc. In that regard, it is crucial to understand how mixing times scale with this parameter $n$. All in all, the theory is thus mainly about obtaining asymptotic developments of the mixing times in the limit $n \to \infty$. We refer to [117] and [136] for references on mixing times of finite Markov chains.

We now move on more closely to the topic of our second work, which is about the acceleration of Markov chains. This subject finds its motivations in very practical matters that are Markov Chain Monte Carlo (MCMC) methods [148, 147]. MCMC methods consist in the design of sampling schemes to sample from specific target distributions. Most often than not, the probability distribution of interest is computationally too complex to be performed directly. This issue arises particularly in the context of simulating probabilistic models in statistical physics [131] or in Bayesian statistics [139]: in these settings states generally consist of high-dimensional configurations modeled with Gibbs distributions: a configuration is in state $\psi$ with probability defined up to a normalizing constant by

$$ \mathbb{P}[\psi] \propto e^{-H(\psi)} $$

where $H(\psi)$ is the energy of the configuration. The probability of a configuration can thus be well estimated up to the normalizing constant, the partition function, which requires an enourmous number of computations, often too large to be realized
numerically. MCMC methods address this difficulty by leveraging the convergence
of Markov chains towards a stationary measure: in order to sample from a target
probability distribution $\pi$, the idea is to sample instead from a Markov chain with $\pi$
as invariant measure and wait for the chain to converge to its equilibrium. In the case
of Gibbs distributions, the local nature of the phenomena generally involved allow to
design chains that bypass the issue of computing the normalizing constant: this is the
Gibbs sampler, also called Glauber dynamics in the case of spin systems. Even in more
general settings finding a Markov chain with prescribed invariant measure is in theory
solved by the Metropolis-Hastings algorithm [134, 86], (see also [55] and [117][Chapter
3]). However the convergence for many cases of interest is often too slow to be used in
practice. One therefore needs to design new chains specifically tailored to the problem
at hand. Another option consists in trying to improve already available dynamics: this
is the acceleration of Markov chains. We refer to the survey [58] by Diaconis for an
introduction to the subject. Numerous works consider speed-ups obtained by giving
some inertia to the chain, which means in practice considering non-reversible chains
on augmented (lifted) state spaces. See [47, 60, 7, 140] and the references therein. We
note that similar acceleration mechanisms have been considered for optimization and
message-passing algorithms [146].

In our work, we focus on a somewhat peculiar acceleration mechanism, that consists
in inserting steps of a deterministic dynamics between those of the Markov chain.
The resulting speed-up is spectacular: for general Markov chains, the mixing time
can be brought down to logarithmic order in the size of the state space by taking
for the deterministic dynamics a bijective map chosen ... at random. This result
is due to Chatterjee and Diaconis [45], however this is not the origin of this story.
The acceleration by a deterministic map was first identified by Chung, Diaconis and
Graham [49] whose motivation was to study the mixing time of a process arising in
the generation of pseudo-random numbers. Their model consists in the Markov chain
$X$ on $Z/nZ$ defined by the recursion: $X_{t+1} = aX_t + B_t$, with ($B_t$) a sequence of iid
increments uniformly distributed on $\{-1, 0, 1\}$. For $a=2$ they proved that after $t =
O(\log n \log \log n)$ steps the distribution of $X_t$ is close to uniform, which already shows
a dramatic speed-up over the simple random walk: the latter is obtained with $a=1$ and
is known to mix in around $n^2$ steps. This is not the promised acceleration to $O(\log n)$
steps, however Chung, Diaconis and Graham also prove that for "most sequences of
$n", the mixing time is in fact really of order $\log n$.

Recently, attention has been brought back to the potential speed-up obtained by
applying deterministic functions to Markov chains. In [45] Chatterjee and Diaconis
consider the following setting: let $P$ be a stochastic matrix on $[n]$ and $S$ the matrix
of a permutation of $n$ elements uniformly distributed on the symmetric group. Under mild assumptions, they prove that the mixing time of the chain with transition matrix $PS$ is $O(\log n)$ with high probability. However they also note that explicit examples are particularly challenging to find. In our research, we study a multi-dimensional analog of the Chung-Diaconis-Graham process: we consider a chain $X$ on $(\mathbb{Z}/n\mathbb{Z})^d, d \ge 1$ defined by the recursion:

$$X_0 := 0 \quad X_t = AX_{t-1} + B_t \mod n \quad \forall t \ge 1$$

Here $A \in \text{GL}_d(\mathbb{Z})$ is an invertible hyperbolic matrix, by which we mean that $A$ is invertible, its inverse has integer entries and $A$ has no eigenvalue of modulus 1, whereas $B_t$ are iid random variables on $\mathbb{Z}^d$ with some distribution $\mu$. Such multi-dimensional cases have been previously studied by Asci [8, 9], Hildebrand [100] and Klyachko [106] who proved acceleration to $O((\log n)^2)$ under mild assumptions on $\mu$. Our contribution is to establish bounds that match the one-dimensional case: we obtain mixing in $O(\log n \log \log n)$ and $O(\log n)$ steps for "most sequences of $n$". Furthermore, we suggest a lead as to how explicit maps causing speed-up may be constructed: our proof is based on the properties of the deterministic dynamical $x \mapsto A^\top x$ on the continuous torus $(\mathbb{R}/\mathbb{Z})^d$, which is known to exhibit chaotic behaviour. We thus suggest that the speed-up is in this case to be explained by the pseudo-random behaviour of the deterministic dynamics, and that other examples may potentially be obtained this way.

## 1.3 Concentration on the symmetric group

One of the fundamental laws of probability, the law of a large numbers, asserts that the empirical mean of a family of iid random variables converges to its expectation. This is an instance of the concentration of measure phenomenon: functions that depend smoothly on a large numbers of independent random variables tend to behave deterministically and concentrate around their mean. Concentration of measure has become a central aspect of modern probability, we refer to the monographs of Ledoux [111] and Boucheron, Lugosi and Massart [34] for an introduction to the subject. Often, concentration of measure refers more closely to the use of concentration inequalities, which quantify how close a given function is with respect to its mean. It also comes with a geometric flavour: in the case of independent random variables, instead of interpreting concentration as the property of many random variables interacting with each other, it can be seen as the property of one measure (the product measure) on a given high-dimensional space (a product space). The concentration of measure thus goes beyond the world of independent random variables. Our work on the cutoff phenomenon,
discussed in the next section, led us to consider such a problem of concentration of measure for the uniform measure on the symmetric group. Concentration phenomena for groups and more generally for weakly dependent random variables were studied by Chatterjee in his PhD. thesis [41, 43, 42], who developed techniques to obtain concentration inequalities based on Stein's method. Among those works, Chatterjee established a Bernstein-like inequality for the uniform measure on the symmetric group that can be stated as follows: let $A \in M_n(\mathbb{R}_+)$, $\sigma \in S_n$ is a uniform permutation and consider the random variable

$$Z = \sum_{i} A_{i\sigma(i)}$$

Then for all $t \ge 0$

$$\mathbb{P}[|Z - \mathbb{E}[Z]| \ge t] \le 2 \exp\left(\frac{-t^2}{2 \|A\| (t + 2\mathbb{E}[X])}\right),$$

where $\|A\| = \max_{i,j \in [n]} A_{i,j}$. The random variable $Z$ can be seen as arising from a linear function on the symmetric group, in the sense that it is a linear combination of indicators $S_{ij} := \mathbb{1}_{\sigma(i)=j}$, which are entries of the permutation matrix $S$. In our work, we propose a higher-order version of this result, that is a concentration inequality for random variables writing as smooth and low-degree polynomials in the entries of $S$. Our starting point was the representation of higher degree polynomials as linear maps on tensor vector spaces (which is another linearization trick) but the final result is not stated in terms of a matrix $A$. Instead we consider directly functions $\phi$ on the space of $n \times n$ real matrices $M_n(\mathbb{R})$. Since functions are to be applied to permutation matrices, some constraints can be imposed, such as the fact that the degree is at most one in each entry. It is crucial however that coefficients are non-negative. For such a polynomial function $\phi$ and $S$ the matrix of a uniform permutation, Theorem 4.1 establishes a concentration inequality that takes the form of a Bernstein inequality similar to the one-dimensional inequality above. The smoothness parameter that plays the role of $\|A\|$ having a more involved expression we will not try to give a more precise statement here. This smoothness parameter involves the degree as well as the $\ell^\infty$ norm of the gradient of $\phi$, but also requires the consideration of auxiliary functions with degrees up to that of $\phi$. This is a consequence of the proof, which is based on an induction on the degree. Following Chatterjee's arguments, the proof consists eventually in proving an upper bound on the moment generating function. Using a linear tensor representation of the polynomial function, Stein's method of exchangeable pairs yields a recursion formula on the moment generating function from which an upper bound is obtained by induction.
## 1.4 The cutoff phenomenon

Discovered by Diaconis, Shahshahani and Aldous [61, 4, 5], the cutoff phenomenon is an intriguing feature observed in a large number of Markov chains, that consists in the abrupt convergence to equilibrium. The formal definition is the following. As usual when considering mixing time of a Markov chain one actually considers a family of Markov chains indexed by an integer $n$. The chain exhibits cutoff if for all $\epsilon \in (0, 1)$, its mixing time satisfies

$$ \frac{t_{\text{mix}}(\epsilon)}{t_{\text{mix}}(1-\epsilon)} \xrightarrow{n \to \infty} 1. $$

The simplest Markov chain to exhibit cutoff is perhaps the simple random walk on the $n$-dimensional hypercube $\{0, 1\}^n$, shown to have cutoff at time $\frac{1}{4}n \log n$ for its continuous version by Aldous. Historical examples include the famous random transposition process proved to exhibit cutoff at time $\frac{1}{2}n \log n$ by Diaconis and Shahshahani [61], and the riffle shuffle, modeled by Gilbert-Shannon and Reeds. Aldous [4] first established the cutoff at time $\frac{3}{2}n \log n$, after which a more thorough analysis was conducted by Bayer and Diaconis [15]. From their work comes the immensely popular statement that to mix a deck of 52 cards, 6 shuffles is not enough but 7 shuffles is more than satisfactory. The cutoff phenomenon is believed to be a very common feature of Markov chains and today numerous examples support this opinion. To name but a few, cutoff has been established for many random walks on finite groups, for which we refer to [57, 150, 48], birth and death chains [63], the Bernoulli-Laplace model [62, 70, 3], Glauber dynamics of spin systems, in particular for the Ising model at high temperature [116, 64, 123, 124], one-dimensional interacting particle systems, for which we refer to the survey of Lacoin [108] and Schmid's PhD dissertation [151].

However not all Markov chains exhibit cutoff: examples are for instance low-dimensional chains such as simple random walks on grids and torii (this can be shown thanks to the product condition given after). Most of the research on the cutoff phenomenon has thus been fueled by the question of determining a simple characterization of cutoff. Ideally, a good characterization should be simple enough to avoid the sharp computation of the mixing time, so the prefactor in the leading term needs not to be known exactly. To this date, no such characterization is known but important progress has been made. A known necessary condition for reversible chains is the product condition. A chain with transition matrix $P$ and invariant measure $\pi$ is reversible if it satisfies the detailed balance equation

$$ \pi(x)P(x, y) = \pi(y)P(y, x) $$

for all states $x, y$. Let $\lambda_*$ be the eigenvalue of $P$ with maximal absolute value but which is distinct from the trivial eigenvalue 1. Define the absolute spectral gap as $\gamma := 1 - \lambda_*$
and the relaxation time $t_{rel} := \gamma^{-1}$. The product condition is the requirement that for all $\varepsilon \in (0, 1)$,

$$ \frac{t_{\text{mix}}(\varepsilon)}{t_{\text{rel}}} \xrightarrow[n \to \infty]{} \infty. $$

The product condition was at first conjectured to be an equivalence, but counter examples exist, e.g. [117][Example 18.7]. Another characterization of cutoff was established by Basu, Hermon and Peres in [14] for reversible chains in terms of hitting time, unfortunately this requires the sharp computation of the mixng time.

The understanding of the phenomenon improved drastically when attention shifted to the case of generic chains. This shift was initiated by the seminal work of Lubetzky and Sly [122] who established cutoff for random walks on random regular graphs. As such chains do not have fixed transition probabilities, the proof strategy cannot rely on an explicit knowledge of the transition matrix, as was the case for the previously cited works. Instead, the result is based on an entropic concentration phenomenon. A heuristic is as follows: ideally the goal is to prove the existence of a constant $h > 0$ such that $-\log P^t(X_0, X_t)$ concentrates around $th$, for all $t$ up to the mixing time. If true, this statement implies that $X_t$ is essentially uniformly distributed on a set of size $e^{th}$. Provided the invariant measure of $X_t$ is sufficiently spread-out on the state space, as is the case for instance for the uniform measure, this immediately implies that $\log n/h$ steps are necessary, but also sufficient for mixing. Since the work of Lubetzky and Sly, a whole series of papers have used the entropic method to prove cutoff for generic chains at entropic time $\log n/h$. From these works, which we review in Chapter 5, a recent breakthrough was made Salez by [149] who gave a sufficient "product-like" condition for cutoff expressed in terms of entropic concentration which in theory can be checked without the sharp knowledge of the mixing time. From this, Salez deduces the cutoff for a large family of chains satisfying a non-negative curvature assumption.

The last of our contributions presented in this thesis is inspired by the paper of Hermon, Sly and Sousi [92] who considered the simple random walk on graphs to which is added a uniform random matching of the vertices. Under mild assumptions on the graph sequence, the simple random walk exhibits cutoff at entropic time. Our work in the area of cutoff is an attempt to generalize this model to more general graphs and in fact more general chains. Starting from two deterministic stochastic matrices $P_1, P_2$ on $[n]$, we investigate the mixing properties of a randomized mixture of $P_1$ and $P_2$: letting $S$ be the matrix of a uniform permutation $\sigma$ and $p \in (0, 1)$, we analyze the mixing of the chain with transition matrix

$$ \mathcal{P} = pP_1 + (1-p)SP_2S^{-1}. $$

In fact, we study a slightly more general model where we allow the probability $p$
to depend on the current state $x$ of the chain and its image $\sigma(x)$. This relaxation is
necessary for the model to include the case of the superposition of graphs. In particular,
taking for $P_1, P_2$ the matrices of the simple random walk on a graph and on a family
of edges respectively, we can recover the model of Hermon, Sly and Sousi. We prove
a cutoff phenomenon at entropic time in the following sense: we establish that in our
model, there exists a measure $\pi$ such that for all $\varepsilon \in (0,1)$, $t = \log n/h + a_n\sqrt{\log n}$,
for any starting point $x \in [n]$, the chain is with high probability at distance at least
$1 - \varepsilon$ in total variation to the measure $\pi$ if $a_n \to -\infty$, and is otherwise $\varepsilon$-close to $\pi$
if $a_n \to +\infty$ and $t = O(\log n)$. We conjecture that the limiting measure $\pi$ is itself
$\varepsilon$-close to a genuine invariant measure, which would allow to deduce proper mixing
time estimates. Unfortunately, at the time this thesis is written, this conjecture is still
being actively pursued. The main issue arises from the fact that the mixing property
holds only for a typical starting point: the initial state of the chain needs to be fixed
before generating the environment or can be chosen uniformly at random, but cannot
be chosen arbitrarily after the environment has been generated.
# Chapter 2

## Linearization of random walks on groups

This chapter is adapted from the paper [30], done jointly with Charles Bordenave.

### 2.1 Introduction

Let $\mathcal{A}$ be a complex unital algebra and consider a non-commutative polynomial $\mathcal{P} = \mathcal{P}(x_1, \dots, x_n)$ in the variables $x_1, \dots, x_n \in \mathcal{A}$. In many cases, a detailed study of the relevant properties of $\mathcal{P}$ is possible only when the degree of $\mathcal{P}$ is small, typically when $\mathcal{P}$ is of degree one, in which case $\mathcal{P}$ is just a linear combination of the $x_i$'s. The linearization trick precisely consists in constructing another polynomial $\tilde{\mathcal{P}}$ of degree one, which can be related to the relevant properties of $\mathcal{P}$. It thus can be used to make computations that were not a priori possible for $\mathcal{P}$. The price to pay is an enlargement of the algebra: writing $\mathcal{P}$ as a finite sum of monomials

$$ \mathcal{P} = \sum_{i_1, \dots, i_k} \alpha_{i_1 \dots i_k} x_{i_1} \cdots x_{i_k}, $$

with $\alpha_{i_1 \dots i_k} \in \mathbb{C}$, $\tilde{\mathcal{P}}$ is generally constructed as

$$ \tilde{\mathcal{P}} = \sum_i \tilde{\alpha}_i \otimes x_i $$

where $\tilde{\alpha}_i \in M_r(\mathbb{C})$ are complex matrices. Therefore $\tilde{\mathcal{P}}$ is no longer in the algebra $\mathcal{A}$ but in the algebra $M_r(\mathbb{C}) \otimes \mathcal{A}$ for some integer $r$ that depends on $\mathcal{P}$ (usually through its degree).

Under various names, the linearization trick has been used in several domains such as electrical engineering, random matrices, operators algebras, automata theory, etc, we refer to the survey [89]. A famous application of the linearization trick in operator
algebra, due to Haagerup and Thorbjornsen [83], is the computation of the spectrum of a non-commutative polynomial. If $a \in \mathcal{A}$, the spectrum of $a$ is defined as $\sigma(a) := \{z \in \mathbb{C}, zI - a$ is not invertible$\}$. Given a non-commutative polynomial $P(x_1, \dots, x_n) \in \mathcal{A}$, it is possible to construct a linear $\tilde{P} \in M_r(\mathbb{C}) \otimes \mathcal{A}$ for some integer $r$, such that the resolvent operator $(zI - P)$ is invertible in $\mathcal{A}$ if and only if $(\Lambda(z) \otimes I_{\mathcal{A}} - \tilde{P})$ is invertible in $M_r(\mathbb{C}) \otimes \mathcal{A}$, where $\Lambda(z)$ is the $r \times r$ matrix with only zero elements except the (1,1) entry which is $z$. Moreover, $(zI - P)^{-1}$ is then precisely the (1,1) entry of $(\Lambda(z) \otimes I_{\mathcal{A}} - \tilde{P})^{-1}$ (seen as a $r \times r$ matrix of elements in $\mathcal{A}$). Such a construction can be found for instance in the monograph [135, Chapter 10].

As illustrated in this last example, we note that the relevant properties of $P$ (here its spectrum and its resolvent) dictates the linearization procedure. In this chapter, we introduce a new linearization of the Markov kernel of a random walk with finite range on a group. This linearization is a new Markov kernel on an enlarged state space and it corresponds to a nearest-neighbour random walk on the group. Many properties of the original random walk can be read on the new random walk. We illustrate our method on free groups and free product of finite groups. Notably, we give a new description of the harmonic measure for finite range random walks on these groups and obtain formulas for the drift and entropy as a byproduct.

### 2.1.1 The linearization trick and coloured random walks on groups

Let $G$ be a finitely generated group with identity element $e$ and we fix a finite set of generators $S$. We assume that $S$ is symmetric, meaning that $g \in S$ implies $g^{-1} \in S$. Let $p = (p_g)_{g \in G}$ be a probability measure on $G$. Consider the Markov chain $(X_n)_{n \ge 0}$ on $G$ with transition probabilities

$$ \mathbb{P}[X_n = h | X_{n-1} = g] = p_{g^{-1}h}, $$

for all $g, h \in G$. Such a Markov chain is called a right convolution random walk on $G$. Left convolution random walk can be considered as well but are essentially the same object, so the choice of right convolution random walks is merely a convention of ours.

The random walk is said to be finitely supported, or to have finite range, if the measure $p$ is finitely supported. It is a nearest-neighbour random walk if $p$ is supported on the set of generators $S$.

As for any Markov chain, the transition kernel of a right convolutional random walk can be seen as an operator acting on square integrable functions: $f = f(x) \mapsto (\mathcal{P}f)(x) = \sum_y P(x, y)f(y)$. In the present case, it can be written in terms of the right multiplication operators $\rho(g)$, $g \in G$, defined as: for all $f \in \ell^2(G)$,

$$ \rho(g) \cdot f : x \mapsto f(xg). $$
Letting $\mathcal{P}(g, h) = p_{g^{-1}h}$ it is then possible to write

$$ \mathcal{P} = \sum_{g \in G} p_g \rho(g). \qquad (2.1) $$

This sum is finite if and only if the random walk is finitely supported. Furthermore, $\rho$ is a group morphism so $\rho(gh) = \rho(g)\rho(h)$ for all $g, h \in G$ ($\rho$ is the right regular representation). Writing each element $g$ in the support of the walk as a product of elements of $S$, it is thus possible to write $\mathcal{P}$ as a non-commutative polynomial in the operators $\rho(g)$, $g \in S$. In other words, $\mathcal{P}$ is an element of the left group algebra which is generated by the $\rho(g)$'s, $g \in G$. The polynomial $\mathcal{P}$ is of degree 1 if and only if the random walk is nearest neighbour. With this point of view, the linearization trick potentially allows to study any finitely supported random walk by considering instead a “nearest-neighbour operator”

$$ \tilde{\mathcal{P}} = \sum_{g \in G} \tilde{p}_g \otimes \rho(g) \qquad (2.2) $$

for some well-chosen matrices $\tilde{p}_g \in M_r(\mathbb{C})$ such that $\sum_g \tilde{p}_g$ is a stochastic matrix, that is, the transition kernel of a Markov chain on $[r]$ where for $n \ge 1$ integer, we set $[n] = \{1, \dots, n\}$.

Then $\tilde{\mathcal{P}}$ is the transition kernel of a Markov chain $(\tilde{X}_n)_n$ on the state space $G \times [r]$, which at each step moves from a pair $(g, u)$ to a pair $(h, v)$ with probability $\tilde{p}_{g^{-1}h}(u, v)$. Equivalently, if one interprets $[r]$ as a set of colours, $\tilde{X}_n$ can at each step be multiplied by $g \in G$ while the colour is updated from $u$ to $v$ with probability $p_g(u, v)$. Such a Markov chain will be called a coloured random walk and can thus be defined similarly to a classical convolution random walk. We note that such random walks already appeared under different names: random walks with internal degrees of freedom [107, 104, 105], covering Markov operators [103], matrix-valued random walks [51]. We note also that a similar idea of using coloured random walks to study finite range random walks on groups has already been considered by Jean Mairesse (personal communication).

**Definition 2.1.** Let $p = (p_g)_{g \in G}$ be a family of matrices with non-negative coefficients of $M_r(\mathbb{R})$ such that

$$ P = \sum_{g \in G} p_g \qquad (2.3) $$

is a stochastic matrix. A coloured random walk is a Markov chain $(Y_n)_n$ on the state space $G \times [r]$, with transition probabilities

$$ \mathbb{P}[Y_n = (h, v) | Y_{n-1} = (g, u)] = p_{g^{-1}h}(u, v). $$

The support of the random walk is the set of elements $g \in G$ such that $p_g \neq 0$. The coloured walk is finitely supported if the support is finite, nearest-neighbour if the support is included in $S$.
By looking only at the colour coordinate, $(Y_n)$ induces a Markov chain on the set of colours $[r]$ whose transition matrix is exactly the matrix $P$ in (2.3).

**Irreducibility assumptions.** For standard convolution random walks, it is generally assumed that the support generates the whole group, which then makes the random walk irreducible. For coloured random walks, we will make the same assumption but suppose as well that the matrix $P$ defines an irreducible Markov chain on the colours. Note this assumption does not necessarily make the coloured walk irreducible, for there may be unreachable pairs $(g, u)$.

**Definition 2.2.** A coloured walk is quasi-irreducible if the marginal of its support on $G$ generates the whole group and the matrix $P$ is irreducible.

**Reversibility.** An important property satisfied by some Markov chains is reversibility. Recall that, if $X$ is a countable set, $\nu$ a measure on $X$ and $Q$ is a Markov chain, then $Q$ is said to be reversible with respect to $\nu$ if for all $x, y \in X$, $\nu(x)Q(x, y) = \nu(y)Q(y, x)$. In other words, $Q$ seen as an operator on $\ell^2(X, \nu)$ is self-adjoint. In our setting, $\mathcal{P}$ defined in (2.1) is said to be reversible if it is reversible for the counting measure on $G$. This is equivalent to the condition: for all $g \in G$, $p_g = p_{g^{-1}}$. Similarly, consider a coloured random walk $\tilde{\mathcal{P}}$ of the form (2.2). Assume that $P$ defined by (2.3) has invariant measure $\pi$ on $[r]$. Then $\tilde{\mathcal{P}}$ is reversible if it is reversible for the product of $\pi$ and the counting measure on $G$. This is equivalent to the condition, for all $g \in G$, $u, v \in [r]$,

$$ \pi(u)p_g(u, v) = \pi(v)p_{g^{-1}}(v, u). $$

## 2.1.2 Main results

**Linearizing random walks.** The first main contribution of our work is to formalize a way to apply the linearization trick to random walks on groups.

**Definition 2.3.** Let $G$ be a group generated by a finite set $S$, with identity element $e$. Let $(X_n)_{n \ge 0}$ be a random walk with kernel $\mathcal{P}$ as in (2.1) and with finite support generating $G$. Let $(Y_n)_{n \ge 0}$ on $G \times [r]$ be a quasi-irreducible, nearest-neighbour coloured random walk with kernel $\tilde{\mathcal{P}}$ as in (2.2). We say that $(Y_n)_{n \ge 0}$ linearizes $(X_n)_{n \ge 0}$ (or $\tilde{\mathcal{P}}$ linearizes $\mathcal{P}$) if the following two property holds: (i) if $Y_0 = (e, 1)$ there exists a sequence of stopping times $(\tau_n)_{n \ge 0}$ with $\tau_0 = 0$ such that $(Y_{\tau_n})_{n \ge 0}$ is a realization of the random walk $(X_n)_{n \ge 0}$ with initial condition $e$, and (ii) these stopping times are a renewal process, that is the variables $\tau_{n+1} - \tau_n$ are iid with finite mean.
To be precise, in the above definition, when saying that $Y_{\tau_n}$ is a convolution random walk, we of course identify $Y_{\tau_n}$ with its $G$ coordinate and forget about the colour, which in this case is constant equal to 1.

We remark also that due to the invariance of transition probabilities by translation by elements of $G$ one can always translate the starting point to $e \in G$, so there is no loss of generality in supposing that the walks are started at $e \in G$.

**Theorem 2.1.** Let $G$ be a group generated by a finite set $S$, with identity element $e$. Consider a random walk with kernel $P$ as in (2.1) with finite support generating $G$. Then there exists $r \ge 1$ and a coloured random walk on $G \times [r]$ with kernel $\tilde{P}$ as in (2.2) which linearizes $P$. Moreover, if $P$ is reversible, then $\tilde{P}$ can be chosen to be also reversible.

Theorem 2.1 has been stated in a non-constructive manner for ease of notation. The proof of Theorem 2.1 in Section 2.2 will exhibit two simple linearization constructions which have a vector $p = (p_g)_{g \in G}$ as input and gives as output the integer $r$ and the family of matrices $(\tilde{p}_g)_{g \in S}$. There is one construction in the general case and one construction which preserves reversibility. We refer to Remark 2.4 for the number of colours $r$ needed in both constructions. We note also that the previous spectral linearization tricks reviewed in [89] did not preserve the Markov property and could not be used to prove Theorem 2.1.

There are possible extensions of the Markovian linearization trick. It is possible with the same proof techniques to linearize a coloured random walk on $G \times [r]$ with finite range and obtain a coloured nearest-neighbour coloured random walk on $G \times [r']$ with $r' \ge r$. In another direction, it is possible to linearize random walks on $G$ which do not have a finite range provided that we allow a countable set of colours, see Remark 2.2 below. Finally, in this work we focus on groups only but our first linearization construction applies to random walks on monoids as well.

**Explicit description of the harmonic measure** The whole point of the linearization trick is that the complexity added by passing to matrices is expected to be much smaller than the benefit of having nearest-neighbour random walks. The second part of this chapter provides such an example where results extend naturally to the matrix setting, thus illustrating the use of the linearization trick. Namely, we extend the explicit description of the harmonic measure for nearest-neighbour convolution walks on groups with an underlying tree structure, such as free groups [102, 114] and free products of finite groups [129, 130, 78, 77]. Following [129], these two cases can be considered at once.
Write $\mathbb{F}_d$ for the free group on $d$ generators $a_1, \dots, a_d$ and let $G_1, \dots, G_m$ be finite groups. Consider the group $G = \mathbb{F}_d * G_1 * \dots * G_m$, with the set of generators

$$ S := \bigcup_{i=1}^{d} \{a_i, a_i^{-1}\} \cup \left( \bigcap_{j=1}^{m} S_j \right). \qquad (2.4) $$

In the above expression, for all $j = 1, \dots, m$, $S_j := G_j \setminus \{e\}$ is the set of elements of $G_j$ distinct from the identity element, and $\cup$ denotes a disjoint union. Such groups were considered in [129, 84] under the name *plain groups*.

Introducing the notation from [129],

$$ \forall g \in S, \quad \text{Next}(g) := \begin{cases} S \setminus \{g^{-1}\} & \text{if } g \in \mathbb{F}_d \\ S \setminus S_i & \text{if } g \in S_i \end{cases}, \qquad (2.5) $$

we see that every element $g \in G$ writes uniquely as a word $g = g_1 \cdots g_n$ with $n = |g|$ and $g_{i+1} \in \text{Next}(g_i)$ for all $i = 1, \dots, n-1$.

Consider an irreducible convolution random walk $(X_n)_{n \ge 0}$ on $G$. If we set aside the trivial cases where $G$ is isomorphic to $\mathbb{Z}$ or $\mathbb{Z}/2\mathbb{Z} * \mathbb{Z}/2\mathbb{Z}$, $G$ is a non-amenable group which implies that $(X_n)_{n \ge 0}$ is transient (see for instance [159, Chapter 1]). More precisely, arguments going back to Furstenberg [76] show that $X_n$ converges a.s. to an infinite word $X_\infty = (\xi_i)_{i \ge 1}$ with the property that for all $i \ge 1$, $\xi_i \in S$ and $\xi_{i+1} \in \text{Next}(\xi_i)$. The law $p^\infty$ of $X_\infty$ is called the harmonic measure and it provides much information on the asymptotic properties of $X_n$.

In the case $(X_n)_{n \ge 0}$ is nearest-neighbour, the harmonic measure can be described very explicitely. In particular it is Markovian: writing $X_\infty^{(k)}$ for the truncature of $X_\infty$ to its $k$ first letters, the sequence $(X_\infty^{(k)})_{k \ge 1}$ is a Markov chain. The transition probabilities are as follows: given $g \in S$, let $\mu_g := p^\infty[\xi_1 = g] = \mathbb{P}[X_\infty^{(1)} = g]$. Then for all $g_1, \dots, g_k \in S$, satisfying $g_{i+1} \in \text{Next}(g_i)$ for all $i$,

$$ p^\infty [(\xi_i)_{i=1}^k = (g_i)_{i=1}^k] = \mathbb{P}[X_\infty^{(k)} = g_1 \cdots g_k] = \mu_{g_1} \frac{\mu_{g_2}}{\sum_{h_2 \in \text{Next}(g_1)} \mu_{h_2}} \cdots \frac{\mu_{g_k}}{\sum_{h_k \in \text{Next}(g_{k-1})} \mu_{h_k}}. \qquad (2.6) $$

This equation determines the harmonic measure on cylinders and thus determines it completely.

On the other hand as soon as one supposes the random walk is only finitely supported, then this description completely falls apart and much less is known about the harmonic measure. A second contribution of our work is to show how these results can actually be extended even for general finitely supported random walks. Extending well-known techniques for nearest-neighbour random walks to the coloured setting, the linearization trick then allows to transfer results back to the case of finitely supported convolution walks.
Extensions of harmonic measures and of more general concepts (namely, the Poisson boundary) to the case of coloured random walks have already been considered in [103]. Here it takes the form of a measure $p_u^\infty$ on infinite words in the group, $u \in [r]$ being the starting colour. Notice that it does not take colours other than through the starting colour. Yet colours need to be incorporated to recover the Markovian decomposition, which is achieved by considering a matrix version of the parameters $\mu_g$, satisfying

$$p_u^\infty(\xi_1 = g) = \sum_{v \in [r]} \mu_g(u, v), \quad \forall u \in [r].$$

Supposing now that $X_n$ is nearest-neighbour, the family of parameters $(\mu_g)_{g \in S}$ is uniquely characterized by a family of matrix relations (2.7), generalizing the so-called traffic equations of Mairesse [129], which arrive as a consequence of stationarity:

$$x_g = p_g \Delta(x)_g + \sum_{\substack{h,h' \in S \\ hh'=g}} p_h x_{h'} + \sum_{h \in \text{Next}(g)} p_{h^{-1}} x_h \Delta(x)_h^{-1} x_g, \quad \forall g \in S, \quad (2.7)$$

where $\Delta(x)_g$ is the diagonal matrix with entries, for $u \in [r]$,

$$\Delta(x)_g(u, u) := \sum_{h \in \text{Next}(g)} \sum_{v \in [r]} x_h(u, v). \quad (2.8)$$

In the sequel, $\Delta(\mu)_g$ will be simply written $\Delta_g$.

These matrices are also used to extend Equation (2.6) to the coloured setting. The global description of the harmonic measure can be summed up in the following theorem. We write $1$ for the vector of $\mathbb{R}^r$ with all coordinates equal to 1 and $1_u$ for the indicator at $u \in [r]$, that is the vector with zero coordinates except the $u$ entry equal to 1.

**Theorem 2.2.** For all starting colour $u \in [r]$ and all cylinder $\xi_1 \cdots \xi_n$,

$$\mathbb{P}_u \left[ X_\infty^{(n)} = \xi_1 \cdots \xi_n, u_n = v \right] = 1_u^\top \mu_{\xi_1} \Delta_{\xi_1}^{-1} \mu_{\xi_2} \cdots \Delta_{\xi_{n-1}}^{-1} \mu_{\xi_n} 1_v, \quad (2.9)$$

and

$$p_u^\infty(\xi_1 \cdots \xi_n) = 1_u^\top \mu_{\xi_1} \Delta_{\xi_1}^{-1} \mu_{\xi_2} \cdots \Delta_{\xi_{n-1}}^{-1} \mu_{\xi_n} 1. \quad (2.10)$$

Moreover, the family $\mu = (\mu_g)_{g \in S}$ is the unique family of matrices with non-negative entries which sum to a stochastic matrix and which are solutions of Equations (2.7).

One motivation for this work was the derivation for finitely supported walks of explicit formulas for various invariant quantities of interest, mainly entropy and drift. By 'explicit', we mean expressing drift and entropy in terms of the unique solutions of some finite dimensional fixed point equations. These can be obtained easily from the harmonic measure.
Suppose $\mathbb{E}[[X_1]] < \infty$, which is in particular true if the walk is finitely supported.
The length with respect to the generating set $S$ of $x = (g, u) \in G \times [r]$ is defined as

$$|x| := |g| = \min\{k, g = a_1 \cdots a_k, a_i \in S\}. \qquad (2.11)$$

On the other hand, recall the definition of the entropy:

$$H(X_n) := - \sum_g \mathbb{P}[X_n = g] \log \mathbb{P}[X_n = g].$$

By sub-additivity arguments, eg. Kingman's theorem, one can prove the existence of
the following limits:

$$\gamma = \lim_{n \to \infty} \frac{|X_n|}{n} \quad \text{a.s. and in } L^1, \qquad (2.12)$$

$$h = \lim_{n \to \infty} - \frac{\log \mathcal{P}^n((e, u), X_n)}{n} \quad \text{a.s. and in } L^1. \qquad (2.13)$$

The quantity $h$, introduced by Avez in [12] and called Avez entropy, or entropy rate, or asymptotic entropy, of the random walk, can in fact be interpreted as the drift for the Green pseudo-metric, see [24]. In this chapter it will often simply be referred to as the entropy of the random walk. We refer the reader to Kaimanovich [102] for a general reference on the topic in the case of convolution random walks, whereas extended notions of entropy and drift to the setting $G \times [r]$ were considered in [104, 105].

In the specific case of a linearizing random walk, the initial random walk can be recovered along a sequence of stopping times. Hence the law of large numbers immediately yields the following Abramov formulas. Such formulas are well known, see [85, 72].

**Corollary 2.1.** Let $(X_n)_{n \ge 0}$ be a finitely supported random walk on $G$ and $(Y_n)_{n \ge 0}$ a coloured random walk that linearizes $(X_n)_{n \ge 0}$ in the sense of Definition 2.3. The drift $\tilde{\gamma}$ and entropy $\tilde{h}$ of $(Y_n)_{n \ge 0}$ can be related to the drift $\gamma$ and entropy $h$ of $(X_n)_{n \ge 0}$ by: $\gamma = \mathbb{E}[\tau_1]\tilde{\gamma}$ and $h = \mathbb{E}[\tau_1]\tilde{h}$.

We notice also that the expected time $\mathbb{E}[\tau_1]$ has a simple expression in the two linearization constructions given in Section 2.2, see Remark 2.1 and Remark 2.3.

On the other hand, the following results provide formulas for the drift and entropy coloured random walks. They are direct extensions of known results in the colourless case (corresponding to $r = 1$) and the proof will be omitted. The usual scalar product is denoted by $\langle, \rangle$.

**Theorem 2.3.** Let $(Y_n)_{n \ge 0}$ be a nearest-neighbour quasi-irreducible coloured random walk on $G \times [r]$ defined by a family of matrices $(p_g)_{g \in S}$. Let $\pi$ be the unique invariant
probability measure of the stochastic matrix $P = \sum_g p_g$. The drift end entropy of $(Y_n)_{n \ge 0}$ are respectively given by

$$ 
\begin{aligned}
\gamma &= \sum_{g \in S} \langle 1, \pi p_g(-\mu_{g^{-1}} + \sum_{h \in \text{Next}(g)} \mu_h) \rangle \\
&= \sum_{g \in S} \sum_{u,v,w \in [r]} \pi(u)p_g(u,v) (-\mu_{g^{-1}}(v,w) + \sum_{h \in \text{Next}(g)} \mu_h(v,w)).
\end{aligned}
$$

and

$$ h = - \sum_{\substack{g \in G \\ u,v \in [r]}} \pi(u)p_g(u,v) \int \log \left( \frac{dg^{-1}p_u^{\infty}}{dp_v^{\infty}} \right) dp_v^{\infty}. \quad (2.14) $$

For nearest-neighbour random walks, the previous integral formula can yield explicit expression for the entropy. However the non-commutativity of $M_r(\mathbb{C})$ creates new difficulties. For coloured random walks, adapting the computation naturally leads to the problem of determining the limit of infinite products of random matrices. This in turn leads to a formula of the entropy in terms of the parameters $(\mu_g)_{g \in S}$ and the law of a family indexed by $[r]$ of random probability measures on $\mathbb{R}^r$ whose law is uniquely characterized by some invariance equation.

To state our result more precisely, we first introduce the hitting probabilities defined as follows. Given $g \in G$, $u \in [r]$, let $\tau_{(g,u)} := \inf\{n : X_n = (g, u)\}$ be the hitting time of a pair $(g, u)$, so that $\tau_g := \min_u \tau_{(g,u)}$ is the hitting time of $g$. For $g \in S$, set

$$ q_g(u, v) := \mathbb{P}[\tau_g < \infty \text{ and } \tau_g = \tau_{(g,v)}]. \quad (2.15) $$

As we will check, the matrices $q_g$ and $\mu_g$ satisfy a simple relation (2.24) and the hitting probabilities $(q_g)_{g \in S}$ are characterized by a quadratic equation (2.28) which can be solved quite explicitly for the free group. In the statement below, $\mathcal{P}^+$ denotes the open simplex of probability measures on $[r]$:

$$ \mathcal{P}^+ := \left\{ x \in \mathbb{R}^r : \sum_{i \in [r]} x_i = 1 \text{ and } x_i > 0, \forall i \in [r] \right\}. \quad (2.16) $$

**Theorem 2.4.** Suppose the matrices $(q_g)_{g \in S}$ satisfy (2.37) defined in Section 2.4. Then the entropy of the coloured random walk is given by

$$ 
\begin{aligned}
h = & - \sum_{g \in S} \sum_{u,v,w \in [r]} \pi(u)p_g(u,v) \left[ \mu_{g^{-1}}(v,w) \int \log \left( \frac{\langle 1_v, z \rangle}{\langle q_{g^{-1}}(u, \cdot), z \rangle} \right) d\nu_w(z) \right. \\
& + \sum_{h \in \text{Next}(g)} \mu_h(v,w) \int \log \left( \frac{\langle q_g(v, \cdot), q_h z \rangle}{\langle 1_u, q_h z \rangle} \right) d\nu_w(z) \quad (2.17) \\
& + \sum_{h \in S: gh \in S} \mu_h(v,w) \int \log \left( \frac{\langle q_{gh}(v, \cdot), z \rangle}{\langle q_h(u, \cdot), z \rangle} \right) d\nu_w(z) \left. \right]
\end{aligned}
$$
where $(\nu_u)_{u \in [r]}$ is the unique family of probability measures on $\mathcal{P}^+$ satisfying

$$ \int f(z) d\nu_u(z) = \sum_{\substack{g \in S \\ v \in [r]}} \int f(q_g z) \mu_g(u, v) d\nu_v(z), \quad \forall u \in [r], $$

for all bounded measurable functions $f$ on $\mathcal{P}^+$.

The technical condition (2.37) is described in Section 2.4. Let us simply note that this condition is automatically satisfied for coloured random walks arising as a linearization of a finite range random walk on $G$ (this is the content of Proposition 2.4 below). Applying Theorem 2.4 to a nearest-neighbour walk for which $r = 1, \pi = 1, \nu = \delta_1$, we get back formula (22) in [129]:

$$ h = - \sum_{g \in S} p_g \left( \mu_{g^{-1}} \log \frac{1}{q_{g^{-1}}} + \sum_{h \in \text{Next}(g)} \mu_h \log q_g + \sum_{h \in S: gh \in S} \mu_h \log \frac{q_{gh}}{q_h} \right). $$

As alluded to above, in Theorem 2.4, the measure $\nu_g$ on $\mathcal{P}_+$ will arise as the convergence in direction toward a random rank one projector of the product of matrices $q_{g_1}q_{g_2}\cdots q_{g_n}$ where $g_1, g_2, \dots$ in $S$ are the successive letters of $X_\infty$ with law $p^\infty$ conditioned to start with $g_1 = g$.

For finite range random walks on free products of groups, fine qualitative results on drift and entropy were already available such as [109, 112] and even on general hyperbolic groups, see [113, 79, 132, 80] and references therein. As pointed in [114, 79], the computations for drift and entropy for nearest-neighbour random walk on the free group have been known for around 50 years but it was however unexpected that these explicit formulas could be extended to finite range random walks. To our knowledge, Theorem 2.3 and Theorem 2.4 provide the first formulas for finite range random walks on free products of group, see 2.1 for an illustration. It would be interesting to try to generalize this kind of formulas in other settings such as amalgamated free products of finite groups or virtually free groups.

In this work, we have chosen to focus through the harmonic measure on the drift and entropy but there are other numerical invariants associated to a random walk such as the spectral radius of $\mathcal{P}$ or the index of exponential decay of the return probability: $\lim_{n \to \infty} \mathcal{P}^{2n}(e, e)^{1/(2n)}$ (they coincide for reversible walks). Our linearization technique could also be used to study these last two quantities but this is less novel since these quantities can be read on the resolvent operator and previous linearization techniques allow to compute resolvent of operators of the form (2.1), see [89] for such linearization and [115, 67] for examples of computation of resolvent operators of the form (2.2).
<figure><img src="image_7.png" /><figcaption>Figure 2.1: Numerical simulation of a finite range random walk $(X_t)_{t \ge 0}$ on $\mathbb{F}_2 = \langle a, b \rangle$ with 12 generators of length 1, 2 and 3, and with random transition probabilities. The linearization procedure gives $r = 16$. On the left, an average of $|X_t|$ over $n = 20000$ trajectories compared to the line $\gamma t$. On the right, an average of $H(X_t)$ over $n$ trajectories compared to the line $ht$. For computational efficiency, the entropy $H(X_t)$ is approximated with the entropy of a random walk on $[n]$ where $\lambda(g), g \in \{a, b\}$, are replaced by an independent uniform permutation matrix of size $n$ (in other words, we consider a random action of $\mathbb{F}_2$ on a set of size $n$). This approximation is valid as long as $ht \le \ln n$, see [31].</figcaption></figure>

### Organization of the chapter

In Section 2.2 we propose a general construction of linearized coloured walks, with some variations, that lead to Theorem 2.1. In Section 2.3 we define the harmonic measure and prove Theorem 2.2. Section 2.4 contains the arguments leading to Theorem 2.4.

## 2.2 A linearization trick: proof of Theorem 2.1

Let $(X_n)_{n \ge 0}$ be a finitely supported random walk on $G$. In this section we construct a nearest-neighbour coloured random walk $(Y_n)_{n \ge 0}$ from which $(X_n)_{n \ge 0}$ can be easily recovered. A natural strategy is to try to split transitions into nearest-neighbour steps, so that when projected on $G$, $Y_n$ becomes a delayed version of $X_n$. The two constructions that follow are simple refinements of this idea. The first one improves on the naive approach in order to reduce the dimension of the matrices, whereas the second approach adapts the idea to preserve reversibility.

From now on, let $a_1, \dots, a_d$ be the elements of the generating set $S$, and $a_0 := e$. Let $K$ denote the support of the probability measure $p$ and $\ell_K$ be the maximal length of an element of $K$. For each $g \in K$ choose arbitrarily a representative $s(g)$, which can always be assumed to be of length $|g|$. We will generally identify $g$ with its representative and
write simply $g = a_{i_1} \cdots a_{i_k}$ to refer to the fact that $s(g) = a_{i_1} \cdots a_{i_k}$, for some $i_1, \dots, i_k \in [d]$. Similarly, set $p_{i_1 \cdots i_k} := p_g$, with in particular $p_0 := p_e$ and $p_i := p_{a_i}$, whether $a_i \in K$ or not. Since we look for a nearest-neighbour coloured random walk, the coloured random walk $(Y_n)_{n \ge 0}$ is defined by the $r \times r$ matrices $\tilde{p}_i$, $i \in [0 : d]$.

**General Idea** Suppose $X_n$ can jump directly from $e$ to the element $g = a_{i_1} \cdots a_{i_k} \in K$. The basic idea consists in splitting this one transition into $k$ successive steps: from $e$ to $a_{i_1}$, then from $a_{i_1}$ to $a_{i_2}$, etc. The question arising next is the following: once the walk is at $a_{i_1}$ how can it tell whether this step was part of the move towards $g$ or the first step of another transition? This problem is addressed by the introduction of colours. With this extra parameter, it becomes possible to distinguish between transitions that use the same elementary steps. A specific colour, written 1, will therefore serve as a reference colour: it is the colour telling the walk that it is not in the middle of transition. By opposition, all other colours are only transitional. In particular, the initial random walk is recovered as the trace of the coloured walk along colour 1.

The previous ideas are common to all the linearization procedures that we propose. The latter differ in the way colours are introduced and by the transition probability one assigns to elementary steps.

### 2.2.1 Linearization in the non-reversible case

The naive strategy sketched at the beginning of this section consists in imposing deterministic steps. Taking again the example of a transition $g = a_{i_1} \cdots a_{i_k} \in K$, we put a probability $p_g$ on the transition from $e$ to $a_{i_1}$ and then probability 1 to all other transitions. This is possible if one allows sufficently many colours, namely $|g| - 1$ colours, exclusive to every generator. Thus the coloured walk $Y_n$ goes from $(e, 1)$ to $(a_{i_1}, 2)$ with probability $p_g$ and then move deterministically from $(a_{i_1}, 2)$ to $(a_{i_2}, 3)$, etc. to eventually arrive at $(g, 1)$. The set of colours $\{2, \dots, |k|\}$ needs to be exclusive to $g$.

It is possible to improve on this idea, noticing that elements of $K$ with common prefixes can share the same colours.

Recall that a representative of minimal length has been fixed for each element of $K$. These representatives are called the representatives of $K$. Given $g, h \in K, g = a_{i_1} \cdots a_{i_k}, h = a_{j_1} \cdots a_{j_k'},$ the prefix of $g$ and $h$ is defined as $g \wedge h = a_{i_1} \cdots a_{i_m}$ where $m := \max\{n \ge 0 : i_1 = j_1, \dots, i_n = j_n\}$. $h$ is a strict prefix of $g$ if $g \wedge h = h$ and $|g| > |h|$. For $k \in [\ell_K]$ and $i_1, \dots, i_k \in [d]$, let

$$[i_1 \cdots i_k] := \{g \in K, g \wedge a_{i_1} \cdots a_{i_k} = a_{i_1} \cdots a_{i_k}, |g| \ge k + 1\}$$
and

$$p_{[i_1 \cdots i_k]} := \sum_{g \in [i_1 \cdots i_k]} p_g$$

be the cumulative mass under $p$ of all words in $K$ for which $a_{i_1} \cdots a_{i_k}$ is a strict prefix. Then for $k \in [\ell_K]$, we set

$$q_{i_1 \cdots i_k} = \frac{p_{[i_1 \cdots i_k]}}{p_{[i_1 \cdots i_{k-1}]}}$$

where the denominator is to be taken as equal to one in the case $k=1$.

The essential idea is the following: we associate a colour $u_{i_1 \cdots i_k}$ to each strict prefix $[i_1 \cdots i_k]$. Suppose now the random walk starts at $(e, 1)$ and goes to $a_{i_1}$. With probability $p_{i_1}$ it stays at colour 1 and with probability $q_{i_1} = p_{[i_1]}$ it takes colours $u_{i_1}$. Suppose this case occurs and the walk continues to $a_{i_1} a_{i_2}$. Then it can come back to colour 1 with probability $p_{i_1 i_2} / p_{[i_1]}$ or continue to colour $u_{i_1 i_2}$ with probability $q_{i_1 i_2}$. With our choice of transition probabilities, the overall probability to have moved from $(e, 1)$ to respectively $(a_{i_1} a_{i_2}, 1)$ and $(a_{i_1} a_{i_2}, u_{i_1 i_2})$ is thus respectively $p_{i_1 i_2}$ and $p_{[i_1 i_2]}$. Iterating this procedure yields the whole generalization, which is formalized in what follows.

Here we will make use of the operator point of view in order to write all the matrices defining $(Y_n)_{n \ge 0}$ at once. As $M_r(\mathbb{C}) \otimes \mathcal{A}$ is isomorphic to $M_r(\mathcal{A})$ for any unital algebra $\mathcal{A}$, the transition kernel $\tilde{P}$ can be written as one matrix whose coefficients are operators on $\ell^2(\mathcal{G})$. In this case, the matrix has coefficients which are linear combinations of the multiplication operators. The matrices $p_i, i \in [0, d]$ can easily be deduced: to obtain $p_i$ it suffices to replace $\rho(a_i)$ by 1 and the $\rho(a_j), j \ne i$ by 0.

For all $k \in [\ell_K]$, let

$$r_k := \mathrm{Card} \left\{ (i_1, \dots, i_k) \in S^k, [i_1 \cdots i_k] \neq \emptyset \right\}$$

be the number of strict prefixes of elements of $K$ that have length $k$. Then, we define the following matrices: $C(k)$ is the $r_{k-1} \times 1$ column matrix

$$C(k) := \left( \sum_{j \in [d]} \frac{p_{i_1 \cdots i_{k-1} j}}{p_{[i_1 \cdots i_{k-1}]}} \rho(a_j) \right)_{i_1 \cdots i_{k-1}},$$

which is indexed by strict prefixes of $K$ of length $k-1$. Given a representative $i_1 \cdots i_{k-1}$, define the row matrix

$$L(i_1, \dots, i_{k-1}) := (q_{i_1 \cdots i_{k-1} j} \rho(a_j))_j$$

indexed by all $j$ such that $i_1 \cdots i_{k-1} j$ is the strict prefix of a representative of $K$. Then use these row matrices to form the $r_{k-1} \times r_k$ diagonal block matrix $D(k)$, whose $i_1 \cdots i_{k-1}$ diagonal entry is $L(i_1, \dots, i_{k-1})$:

$$D(k) = \left( \dots \quad L(i_1, \dots, i_{k-1}) \quad \dots \right).$$
Finally combine all the preceding matrices to construct:

$$
\tilde{\mathcal{P}} := \begin{pmatrix}
\sum_{i \in [0:d]} p_i \rho(a_i) & D(1) & 0 & 0 \\
C(2) & 0 & D(2) & 0 \\
C(3) & 0 & 0 & D(3) \\
\vdots & & \ddots & \vdots \\
C(\ell_K - 1) & 0 & 0 & D(\ell_K - 1) \\
C(\ell_K) & 0 & 0 & 0
\end{pmatrix} \quad (2.18)
$$

**Example 2.1.** The construction will certainly be clearer on a concrete example. Consider a random walk on the group $G$ given by the presentation $\langle a, b | ab = ba \rangle$, which is in fact isomorphic to $\mathbb{Z}^2$. Suppose the random walk has support

$$
K = \{e, a, b, a^2, a^2b\}.
$$

To avoid large matrices, we forget about the inverses $a^{-1}, b^{-1}$ but they should not be discarded in a general case.

Because of the relation $ab = ba$, there can be several ways to write an element of $G$
as words in $a$ and $b$, for instance $a^2b = aba$. Therefore we fix a representative for each
element of the support. In the present case, group elements can be written uniquely as
$a^k b^l$ so it is natural to choice these words as representatives.

Applying the preceding construction, one eventually obtains the following operator
matrix:

$$
\begin{pmatrix}
p_e \rho(e) + p_a \rho(a) + p_b \rho(b) & q_a \rho(a) & 0 \\
\frac{p_a^2}{p[a]} \rho(a) & 0 & q_a^2 \rho(a) \\
\frac{p_a^2 b}{p[a^2]} \rho(b) & 0 & 0
\end{pmatrix}
=
\begin{pmatrix}
p_e \rho(e) + p_a \rho(a) + p_b \rho(b) & (p_a^2 + p_a^2 b) \rho(a) & 0 \\
\frac{p_a^2}{p_a^2 + p_a^2 b} \rho(a) & 0 & \frac{p_a^2 b}{p_a^2 + p_a^2 b} \rho(a) \\
\rho(b) & 0 & 0
\end{pmatrix}.
$$

*Proof of Theorem 2.1 (non-reversible case).* On row $i_1 \cdots i_k$, the sum of entries of the matrix $P = \sum \tilde{p}_i$ is

$$
\sum_{j \in [d]} \frac{p_{i_1 \cdots i_{k-1} j}}{p_{[i_1 \cdots i_{k-1}]}} + \sum_{j \in [d]} q_{i_1 \cdots i_{k-1} j} = \frac{1}{p_{[i_1 \cdots i_{k-1}]}} \sum_{j \in [d]} (p_{i_1 \cdots i_{k-1} j} + p_{[i_1 \cdots i_{k-1} j]}) = 1.
$$

Thus $P$ is stochastic and $\tilde{\mathcal{P}}$ defines indeed a coloured random walk $(Y_n)_{n \ge 0}$.

Suppose now $Y_n = (g_n, u_n)$ is started at colour 1. Then define $(\tau_n)_{n \ge 0}$ as the successive return times at the first colour: $\tau_0 := 0$ and for $n \ge 1$

$$
\tau_n := \inf\{m > \tau_{n-1}, u_m = 1\}
$$

By Markov's property, the random variables $\tau_n - \tau_{n-1}$ are iid with the same law as $\tau_1$.
<figure><img src="image_8.png" /><figcaption>Figure 2.2: The linearizing reversible random walk</figcaption></figure>

For all $g = i_1 \cdots i_k$ in $K$, the probability that $Y_{\tau_1} = g$ is

$$ 
\begin{align*}
\mathbb{P}[Y_{\tau_1} = g] &= q_{i_1} q_{i_1 i_2} \cdots q_{i_1 \cdots i_{k-1}} \frac{p_{i_1 \cdots i_k}}{p_{[i_1 \cdots i_{k-1}]} \\
&= p_{[i_1]} \frac{p_{[i_1 i_2]}}{p_{[i_1]}} \cdots \frac{p_{[i_1 \cdots i_{k-1}]}}{p_{[i_1 \cdots i_{k-2}]} p_{[i_1 \cdots i_{k-1}]} \\
&= p_{i_1 \cdots i_k} = p_g.
\end{align*}
$$

By Markov's property and the fact that the increments are iid one easily deduce that $Y_{\tau_n} \stackrel{(d)}{=} X_n$ for all $n \ge 0$. Finally, the irreducibility of $X_n$ implies the quasi-irreducibility of $Y_n$. $\square$

*Remark 2.1.* The expectation of the hitting time $\tau_1$ is very simple to compute: $Y_1$ can go through each $g \in K$ with probability $p_g$, in which case it needs $|g|$ steps to get back to the colour 1. Hence the expectation of $\tau_1$ is just the average length of elements in $K$:

$$ \mathbb{E}[\tau_1] = p_e + \sum_{g \in K} p_g |g| = p_e + \mathbb{E}[|X_1|]. $$

*Remark 2.2.* If $\mathcal{P}$ is not of finite range, then the construction produces a countable set of colours. The construction could nevertheless be useful if the expected time $\mathbb{E}[\tau_1] = p_e + \mathbb{E}[|X_1|]$ is finite.

### 2.2.2 Linearization in the reversible case

The previous constructions prevent the coloured random walk to be reversible. To correct this, we again assign new colours to every element of $K$ with the following variation. We assume that for all $g \in K$, the representative of $g = a_{i_1} \cdots a_{i_n}$ is chosen such that the representative of $g^{-1}$ is $a_{i_n}^{-1} \cdots a_{i_1}^{-1}$. We start with the neutral colour 1 and, for each pair $(g, g^{-1})$ with $|g| = |g^{-1}| \ge 2$, we add $|g| - 1$ new colours $u_1(g), \dots, u_{|g|-1}(g)$ and we set $u_k(g^{-1}) = u_{|g|-k}(g)$ for all $1 \le k \le |g|-1$. Suppose $g$ is written as $g = a_{i_1} \cdots a_{i_k}$. For all $h \in G$, the transition probability to go from $(h, 1)$ to $(ha_{i_1}, u_1(g))$ is set to some value $\alpha_g$ to be determined, such that $\alpha_g = \alpha_{g^{-1}}$ and $\sum_{g \in S} \alpha_g = 1$. All other transition probabilities on the segment joining $(x, 1)$ to $(xg, 1)$ are set to $1/2$, see Figure 2.2.
Thanks to the constraint $\sum_{g \in G} \alpha_g = 1$, $\tilde{\mathcal{P}}$ is indeed a Markov transition kernel. However, the coloured walk can now make steps that would not have been possible in the naive approach. For instance, it can go from $(e, 1)$ to some $(g, u)$ and then come back to $(e, 1)$, even if $p_e = 0$ for the initial walk. Therefore, the stopping times cannot be taken directly as the return times at colour 1. Instead define, if $Y_n = (g_n, u_n)$ has transition kernel $\tilde{\mathcal{P}}$,

$$ \tau_n := \begin{cases} \inf\{m \ge \tau_{n-1} : u_m = 1, g_m \ne g_{\tau_{n-1}}\} & \text{if } g_{\tau_{n-1}+1} \ne g_{\tau_{n-1}} \\ \tau_{n-1} + 1 & \text{if } g_{\tau_{n-1}+1} = g_{\tau_{n-1}}. \end{cases} $$

Theorem 2.1 in the reversible case is now contained in the following lemma.

**Lemma 2.1.** Suppose $X_n$ is a finitely supported random walk on $G$ defined by a probability vector $p$ and started at $e$. Setting for each $g \in K$

$$ \alpha_g := \begin{cases} \frac{(1-p_e)|g|p_g}{\sum_{h \in K} |h|p_h} & \text{if } g \ne e \\ p_e & \text{if } g = e \end{cases} \qquad (2.19) $$

the preceding construction yields an operator $\tilde{\mathcal{P}}$ which defines a reversible coloured random walk $(Y_n)_{n \ge 0}$ satisfying $Y_{\tau_n} \stackrel{(d)}{=} X_n$ for all $n \ge 0$ if started at $(e, 1)$.

*Proof.* As already pointed, the construction defines a coloured random walk as long as $\sum_{g \in S} \alpha_g = 1$, which is true for $\alpha_g$ defined as in (2.19). Furthermore such a coloured walk is reversible: for all $(g, u) \in G \times [r]$, letting

$$ \mu(g, u) = \begin{cases} 1 & \text{if } u = 1 \\ 2\alpha_h & \text{if } u = u_h(k) \text{ for some } k < |h|. \end{cases} $$

defines a reversible measure for the random walk, as it can be checked directly.

Consider now the coloured walk $(Y_n)_{n \ge 0}$ defined by (2.19), started at $Y_0 = (e, 1)$. Suppose first that $p_e = 0$, so that $\tau_1$ is the hitting time of the set $(K \setminus \{e\}) \times \{1\}$.

At step 1 the coloured walk necessarily enters the segment joining $(e, 1)$ to $(h, 1)$ for some $h \in K$. If the walk escapes this segment at $h$, then $Y_{\tau_1} = h$. Otherwise, it necessarily goes back to the starting state $(e, 1)$. Now on each of these segments, the coloured walk is simply performing a simple random walk so the escape probabilities are given by the standard gambler's ruin problem. Namely the simple random walk on $[0 : n]$ reaches $n$ before it gets to 0 with probability $k/n$ when started at $k \in [0 : n]$. Therefore by Markov's property

$$ \mathbb{P}_{(e,1)}[Y_{\tau_1} = g] = \alpha_g / |g| + \sum_{h \in K} \alpha_h (1 - 1/|h|) \mathbb{P}_{(e,1)}[Y_{\tau_1} = g]. $$

We deduce that

$$ \mathbb{P}_{(e,1)}[Y_{\tau_1} = g] = \frac{\alpha_g / |g|}{\sum_{h \in K} \alpha_h / |h|} = p_g. $$
For the general case $p_e \neq 0$, $Y_{\tau_1} = (e, 1)$ if and only if $Y_1 = (e, 1)$ which occurs with probability $\alpha_e = p_e$. For $g \neq 0$, consider the random walk conditioned to move at every step, written $(Y'_n)_{n \geq 0}$. If $q(x, y)$ is the transition probability for $Y_n$ between two states $x$ and $y$, then the transition probability for $Y'_n$ is 0 if $y = x$ and $q(x, y)/(1 - q(x, x))$ otherwise. The previous argument apply to this walk, so

$$ \mathbb{P}_{(e,1)}[Y'_{\tau_1} = g] = \frac{\alpha_g/((1-p_e)|g|)}{\sum_{h \in K \setminus \{e\}} \alpha_h/((1-p_e)|h|)} = \frac{p_g}{1-p_e}, $$

with $\tau'_1$ is the obvious extension of $\tau_1$ to $Y'_n$. Coming back to $Y_{\tau_1}$: to reach $g \neq e$ it is necessary that $Y_1 \neq e$, which occurs with probability $(1 - p_e)$. Conditional on that event it no longer matters whether the random walk comes back at $e$ and possibly stays there, so one can reason with $Y'_n$ instead. Hence

$$ \mathbb{P}_{(e,1)}[Y_{\tau_1} = g] = (1-p_e)\mathbb{P}_{(e,1)}[Y'_{\tau_1} = g] = p_g. $$

The conclusion follows.

<figure><img src="image_9.png" /></figure>

*Remark 2.3.* The expected time $\mathbb{E}[\tau_1]$, although not as simple as in the non-reversible case, can nonetheless be computed quite easily using for instance the electric network paradigm. Using [128][Prop 2.20], we found in the case $p_e = 0$

$$ \mathbb{E}[\tau_1] = \sum_{g \in K} p_g |g|^2 = \mathbb{E}|X_1|^2. \qquad (2.20) $$

*Remark 2.4.* In the naive approach, we have that the total number of colours is

$$ r = 1 + \sum_{g \in K} (|g| - 1). $$

In the reversible construction, there is a factor 1/2 on front of the sum (because we use the same colours for $g$ and $g^{-1}$). In the improved construction of Subsection 2.2.1, this is an upper bound, the actual value is $r = 1 + \text{Card}(K') - \text{Card}(K)$ where $K'$ is the set of words which are a suffix of some element in $K$ (in the chosen representatives). In a concrete application, it is often possible to design linearization procedures which are more economical in terms of number of colours.

## 2.3 Coloured random walks on free products of groups

In this section we define and study the harmonic measure for coloured random walks on such groups, proving Theorem 2.2. Explicit descriptions of the harmonic measure on free groups were obtained in [102, 54, 114]. Similar approaches can be carried out for free products of finite groups, of monoids, of finite alphabets [78, 77, 130].
The main ingredient in the study of random walks on groups is the invariance by translation of the transition probabilities. This G-invariance of transition probabilities still holds for coloured random walks, allowing many arguments to extend to this setting. Indeed, once a good way of taking colours into account is found, one can essentially replace scalar parameters (such as $p_g, \mu_g$, etc.) by matrices. The argumentation for convolution random walks can then be extended in a straightforward way as long as the computations are consistent with matrix products, which is the case most of the time. For this reason, we will often sketch or omit the proofs when they are too similar to already known arguments.

The case of free groups and free products of finite groups is very similar in nature and they can be handled together as done in [129]. Let $G_1, \dots, G_m$ be finite groups and consider the group $G = \mathbb{F}_d * G_1 * \dots * G_m$, with the set of generators (2.4). Recall the definition of the map Next in (2.5). Every element $g \in G$ writes uniquely as a word $g = g_1 \cdots g_n$ with $n = |g|$ and $g_i \in S, g_{i+1} \in \text{Next}(g_i)$ for all $i$. Such words will be called reduced.

### 2.3.1 The harmonic measure on the boundary

Consider a coloured random walk $(X_n)_{n \ge 0}$ on $G \times [r]$ defined by a family $(p_g)$ of matrices. We assume that the walk is quasi-irreducible and nearest-neighbour. We assume furthermore that $G$ is not isomorphic to $\mathbb{Z}$ or $\mathbb{Z}/2\mathbb{Z} * \mathbb{Z}/2\mathbb{Z}$. This implies the coloured walk is transient, as shown by Proposition 2.1 below.

Define the boundary $\partial G$ as

$$ \partial G := \{ \xi_0 \xi_1 \cdots \xi_n \cdots, \forall i \ge 0, \xi_i \in G, \xi_{i+1} \in \text{Next}(\xi_i) \}. $$

The multiplication action by $G$ on itself can be extended to $\partial G$: given $g \in G$, $\xi = \xi_0 \xi_1 \cdots \in \partial G$, define

$$ g\xi := \begin{cases} g\xi_0\xi_1\cdots & \text{if } \xi_0 \in \text{Next}(g) \\ (g\xi_0)\xi_1\cdots & \text{if } g\xi_0 \in S \\ \xi_1\xi_2\cdots & \text{if } g = \xi_1^{-1}. \end{cases} \quad (2.21) $$

The boundary $\partial G$, which can be seen as a subset of $G^N$, is equipped with the product topology and the corresponding $\sigma$-algebra. Given a measure $\nu$ on $\partial G$, let $g \cdot \nu$ be the image measure of $\nu$ under the multiplication by $g$, that is the measure defined by the fact that

$$ \int f(\xi) d(g \cdot \nu)(\xi) := \int f(g\xi) d\nu(\xi), $$

for all bounded measurable function $f$ on $\partial G$.
**Definition 2.4.** Consider a family $\nu = (\nu_u)_{u \in [r]}$ of probability measures on $\partial G$ indexed by colours. $\nu$ is said to be stationary if for all $u \in [r]$,

$$ \nu_u = \sum_{g \in G, v \in [r]} p_g(u, v) g \cdot \nu_v. \qquad (2.22) $$

From now on, all measures considered on $\partial G$ will be implicitly indexed by colours. The following result extends Theorem 1.12 in [114] to coloured random walks. The proof is exactly the same and will thus be omitted.

**Proposition 2.1.** There exists a random variable $X_\infty \in \partial G$ such that $X_n$ converges a.s. to $X_\infty$. The law of $X_\infty$ is called the harmonic measure and is the unique stationary measure on the boundary $\partial G$. It will be denoted $(p_u^\infty)_{u \in [r]}$ where the index $u$ is to be interpreted as the starting colour of $(X_n)_{n \ge 0}$.

### 2.3.2 Markovian structure of the harmonic measure

A measure on $\partial G$ is uniquely determined by its mass on cylinders. Given a measure $\nu$, we will write $\nu(\xi_1 \cdots \xi_n)$ for the mass of the cylinder containing all infinite words which start with the prefix $\xi_1 \cdots \xi_n$.

In the colourless case, the tree structure of the group $G$ implies the harmonic measure is Markovian. It can be computed entirely from the solutions of a set of equations derived from the stationarity of the harmonic measure with the following interpretation.

For all $k \ge 0$, let $X_\infty^{(k)}$ be the restriction of $X_\infty$ to the first $k$-th letters. Thus for all $k \ge 1$ the mass under the harmonic measure of cylinders of size $k$ is given by the law of $X_\infty^{(k)}$. On the other hand $(X_\infty^{(k)})_{k \ge 1}$ is a non-backtracking walk which one can interpret as the loop-erased random walk formed from $(X_n)_{n \ge 0}$. In the standard colourless setting, the tree structure of the group makes the loop-erased random walk a Markov chain whose transition probabilities can be computed easily.

In the coloured setting, one can expect to have similar properties but the loop-erased random walk of the process is no longer a Markov chain so this is not the right process to consider. Instead let $\tau_g := \inf\{n \ge 0, X_n = (g, \cdot)\}$ be the hitting time of $g$ by the random walk $X_n$ and $u_k$ the colour at time $\tau_{X_\infty^{(k)}}$. Given $g \in S$, set

$$ \mu_g(u, v) := \mathbb{P}_{(e,u)}[X_\infty^{(1)} = g, X_{\tau_g} = (g, v)]. \qquad (2.23) $$

In words, $\mu_g(u, v)$ is the probability that the random walk, starting from $(e, u)$, visits $g$, with colour $v$ for the first time, and later escapes at infinity in direction $g$. The process considered which is the equivalent of the loop erased random walk in the coloured setting is $(X_\infty^{(k)}, u_k)_{k \ge 1}$, which is a coloured Markov chain with increment distribution $\mu$.
*Proof of Theorem 2.2.* Most of the proof is similar to the case of colourless walks, so we will only emphasize what is different. Details can be found in [114, 129, 130].

Recall Definition (2.8) and that $\Delta_g := \Delta(\mu)_g$. Given the definition of the matrices $\mu_g$, Equation (2.9) is an easy consequence of Markov's property and the G-invariance of the transition probabilities of the random walk.

Let us now prove now that the matrices $\mu_g$ are characterized by Equation (2.7). Consider any family $(\nu_g)_{g \in S}$ of non-negative matrices, solutions of (2.7) and such that $\sum_{g \in S} \nu_g$ is a stochastic matrix. Then for all $u \in [r]$ define the measure $\nu_u^\infty$ on $\partial G$ by setting for each cylinder $\xi_1 \cdots \xi_n$,

$$ \nu_u^\infty = \mathbb{1}_u \nu_{\xi_1} \Delta(\nu)_{\xi_1}^{-1} \nu_{\xi_2} \cdots \Delta(\nu)_{\xi_{n-1}}^{-1} \nu_{\xi_n} \mathbb{1} $$

The fact that $\sum_{g \in S} \nu_g$ is a stochastic matrix proves that $\nu_u^\infty$ is indeed a probability measure on $\partial G$.

Mimicking the proof of the case of colourless walks, one can deduce that $\nu^\infty$ is stationary, which by uniqueness of stationary measures yields that $\nu_u^\infty = p_u^\infty$ for all $u \in [r]$.

At this stage we only proved that for all $g \in S$, $u \in [r]$, $p_u^\infty(g) = \sum_{v \in [r]} \mu_g(u, v) = \sum_{v \in [r]} \nu_g(u, v)$. To deduce $\mu_g = \nu_g$, we observe that the previous equality shows $\Delta_g = \Delta(\nu)_g$ for all $g \in S$. Consequently the matrices $\mu_g$ and $\nu_g$ can be seen as the fixed points of a quadratic map $f: M = (M_g)_{g \in S} \mapsto (f(M)_g)_{g \in S}$ from the set of non-negative matrices to itself, where

$$ f(M)_g := A_g + \sum_{\substack{h,h' \in S \\ hh'=g}} p_h M_{h'} + \sum_{h \in \text{Next}(g)} p_{h^{-1}} M_h B_g M_g, $$

for all $g \in S$, and $A_g, B_g$ are non-negative matrices that do not depend on $M$.

By the fact that $f$ is quadratic, one can now use monotonicity arguments as in the proof of [129, Lem. 4.7] to deduce that $\mu_g = \nu_g$. $\square$

**Hitting probabilities.** Let us discuss here another way to compute the harmonic measure through hitting probabilities. It is an easy extension to the coloured case of equations that can be found for classical nearest-neighbour random walks in [114, 129, 130] but here the equations become matrix equations.

Recall Definition (2.15). The motivation for introducing these new matrices is that they can be easily related to the matrices $\mu_g$ by

$$ \mu_g(u, v) = q_g(u, v) \Delta_g(v, v), \quad \forall g \in S. \qquad (2.24) $$
This gives yet another way to write equations (2.9) and (2.10):

$$ \mathbb{P}_u \left[ X_{\infty}^{(k)} = \xi_1 \cdots \xi_k, u_k = v \right] = (q_{\xi_1} \cdots q_{\xi_{k-1}} \mu_{\xi_k}) (u, v), \quad (2.25) $$

$$ p_u^{\infty}(\xi_1 \cdots \xi_k) = \sum_v (q_{\xi_1} \cdots q_{\xi_{k-1}} \mu_{\xi_k}) (u, v). \quad (2.26) $$

Furthermore, using (2.24), the traffic equation (2.23) can be rewritten as

$$ \mu_g = p_g \Delta_g + \sum_{\substack{h,h' \in S \\ hh'=g}} p_h \mu_{h'} + \sum_{h \in \text{Next}(g)} p_{h^{-1}} q_h \mu_g, \quad \forall g \in S. \quad (2.27) $$

Observe that $y_g := \Delta_g 1 = \mu_g 1$ and $y_g \in \mathbb{R}^r$ is equal to the diagonal of the diagonal matrix $\Delta_g$. By construction, we have that $\sum_g y_g = 1$. If we evaluate the matrix equation (2.27) on the vector $1$, we obtain a linear equation for $y = (y_g)_{g \in S}$, seen as a vector with coordinates in $\mathbb{R}^r$, of the form $Ty = 0$ where $T$ is matrix on $S \times S$ with matrix-valued coefficients in $M_r(\mathbb{R})$. Finally, once, $\Delta_g$ is known, Equation (2.27) becomes linear in $\mu$ seen as a vector of matrices. Therefore the matrices $\mu_g$ can be completely recovered from the $q_g$.

On the other hand, the latter satisfies a simpler quadratic equation: conditioning on $X_1$ and applying Markov property, one obtains

$$ x_g = p_g + \sum_{\substack{h,h' \in S \\ hh'=g}} p_h x_{h'} + \sum_{h \in \text{Next}(g)} p_{h^{-1}} x_h x_g. \quad (2.28) $$

Arguing as in the proof of Theorem 2.2, one can prove this equation characterizes the $q_g$ as follows:

**Lemma 2.2.** The family $q = (q_g)_{g \in S}$ is the unique solution to Equation (2.28) among family of matrices $(m_g)_{g \in S}$ such that $\mu_g(u, v) \le m_g(u, v) \le 1$ for all $u, v \in [r]$.

### 2.3.3 Solving the traffic equations

We now propose methods to solve the equations of the previous sections. For a general free product of groups, we show how solutions can be computed numerically. When $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$, these equations can be solved explicitly in the case of classical nearest-neighbour random walks. For coloured random walks, complications arise due to matrix equations, so we can give explicit solutions up to the issue of determining a matrix square root. Thanks to the linearization trick, this problem is thus the only remaining obstacle preventing from obtaining an explicit description for finite range random walks.
**General case.** We have seen in the previous section that the harmonic measure is fully described by the family of matrices $\mu = (\mu_g)_{g \in S}$ on $[r]$ defined by (2.23). By Theorem 2.2, these matrices are uniquely characterized by the traffic equation (2.7) so it is possible to evaluate numerically $\mu$ by iterating the map defining the traffic equations.

The hitting probabilities $q = (q_g)_{g \in S}$ satisfy a simpler quadratic equation (2.28) than the traffic equation of $\mu$. As explained in the proof of Lemma 2.2, it is possible to evaluate numerically from above and from below $q$ by iterating the map $f$ defined in (2.28) such that $q = f(q)$.

**Case of $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$**. In some special cases, one can find additional relations allowing to write the matrix $\mu_g$ as an explicit function of the matrices $q_g$. This case occurs for instance when $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$. Given $g \in S$, let $d_g$ be the diagonal matrix with diagonal entries

$$d_g(u, u) := \sum_w q_g(u, w).$$

In words, $d_g(u, u)$ is the probability to ever reach $g$, starting from the pair $(e, u)$.

**Proposition 2.2.** When $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$, for all $g \in S$ the matrix $(I - q_{g^{-1}}q_g)$ is invertible and

$$\mu_g(u, v) = q_g(u, v) \sum_{w \in [r]} (I - q_{g^{-1}}q_g)^{-1} (I - d_{g^{-1}})(v, w) \quad \forall g \in S, u, v \in [r]. \quad (2.29)$$

*Proof.* Suppose $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$. Then for all $g \in S, u \in [r]$,

$$\mu_g(u, v) = q_g(u, v) \left( 1 - \sum_{w \in [r]} q_{g^{-1}}(v, w) + \sum_{w, z \in [r]} q_{g^{-1}}(v, w) \mu_g(w, z) \right).$$

In particular $q_g(u, v) = 0$ implies $\mu_g(u, v) = 0$. Otherwise, rewrites this equation as

$$\frac{\mu_g(u, v)}{q_g(u, v)} = 1 - d_{g^{-1}}(v, v) + \sum_{w, z \in [r]} q_{g^{-1}}(v, w)q_g(w, z) \frac{\mu_g(w, z)}{q_g(w, z)}.$$

The right-hand being independent of $u$, so is the left-hand side. Consequently let $x_v := \mu_g(u, v)/q_g(u, v)$. Then one can again rewrite the above equation as the matrix linear equation

$$x = (I - d_{g^{-1}})1 + q_{g^{-1}}q_g x.$$

Provided $I - q_{g^{-1}}q_g$ is invertible, solving this equation yields the desired expression for $\mu_g(u, v)$.

Therefore we are left to prove that $I - q_{g^{-1}}q_g$ is invertible. This can be justified by the fact that $\sum_{v \in [r]} \sum_{n \ge 0} (q_{g^{-1}}q_g)^n(u, v)$ is the average number of times the walk goes
to $g^{-1}$ and comes back to $e$ when starting at colour $u$. By transience of the walk, this number must be finite. Hence the sum $\sum_{n \ge 0} (q_{g^{-1}} q_g)^n$ is convergent and the inverse of this matrix is precisely $I - q_{g^{-1}} q_g$. $\square$

We now further study the matrix equation (2.15) satisfied by the hitting probabilities $(q_g)_{g \in S}$. Supposing $G = \mathbb{F}_d * \mathbb{Z}/2\mathbb{Z} * \cdots * \mathbb{Z}/2\mathbb{Z}$, for all $g \in S$, Equation (2.28) becomes:

$$q_g = p_g + \sum_{h \neq g^{-1}} p_{h^{-1}} q_h q_g. \qquad (2.30)$$

In the colourless case, it is possible to reduce Equation (2.30) to a scalar equation, see for example [114]. We extend this computation to the coloured case. We define the matrix in $M_r(\mathbb{R})$,

$$z = I - \sum_{g \in S} p_{g^{-1}} q_g. \qquad (2.31)$$

We now express $q_g$ as a function of $(z, p_g, p_{g^{-1}})$ and find a closed equation satisfied by $z$. For simplicity, we assume that for all $g \in G$, the matrix $p_g$ is invertible. If this is not the case, a similar argument holds but one should be careful with pseudo-inverses.

We define the matrices in $M_{2r}(\mathbb{R})$:

$$P_g = \begin{pmatrix} 0 & p_g \\ p_{g^{-1}} & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} z & 0 \\ 0 & z \end{pmatrix} \quad \text{and} \quad Q_g = \begin{pmatrix} 0 & q_g \\ q_{g^{-1}} & 0 \end{pmatrix}.$$

From our assumption, $P_g$ is invertible and

$$P_g^{-1} = \begin{pmatrix} 0 & (p_{g^{-1}})^{-1} \\ p_{g^{-1}} & 0 \end{pmatrix}.$$

Applying (2.30) to $g$ and $g^{-1}$, we find that, for all $g \in S$, $zq_g = p_g - p_g q_{g^{-1}} q_g$ and thus

$$ZQ_g = P_g - P_g Q_g^2.$$

We set $Z_g = P_g^{-1}Z$. The above equation rewrites

$$(Z_g + Q_g)Q_g = I. \qquad (2.32)$$

In particular $Z_g = Q_g^{-1} - Q_g$ so $Z_g$ and $Q_g$ commute. We may thus solve the quadratic equation $Q_g^2 + Z_g Q_g - I = 0$ with $Q_g$ as unknown as in the scalar case. Completing the square yields

$$(Q_g + Z_g/2)^2 = I + Z_g^2/4.$$

Therefore, for some proper choice of the matrix square root function, we get

$$Q_g = \frac{1}{2} \left( \sqrt[4]{4I + (P_g^{-1}Z)^2} - P_g^{-1}Z \right), \qquad (2.33)$$
where $\sqrt{\cdot}$ is a notation to stress that the choice of the square root is unknown. First, as $Z_g$ and $Q_g$ commute, the eigenvalues completely determine the square root. Also, since $Q_g$ is a block antidiagonal matrix, for every of its eigenvalue $\lambda, -\lambda$ must also be an eigenvalue with the same multiplicity (algebraic and geometric). In particular, we are left with at most $2^r$ choices for the square root to pick in (2.33) (a choice of sign for each eigenvalue pair $(\lambda, -\lambda)$).

There is one useful property to further determine the square root. Consider

$$R_g = Q_g P_g^{-1} = \begin{pmatrix} q_g p_g^{-1} & 0 \\ 0 & q_{g^{-1}} p_{g^{-1}}^{-1} \end{pmatrix}.$$

We observe from (2.30) that $q_g p_g^{-1} = (I - \sum_{h \neq g^{-1}} p_{h^{-1}} q_h)^{-1}$. The matrix $\sum_{h \neq g^{-1}} p_{h^{-1}} q_h$ is sub-stochastic: it has non-negative entries and the sum over each row is less or equal than one (from a starting colour, it corresponds to the probability that the coloured walk killed when visiting $g$ comes back to $e$ after some time). In particular, the matrix $\sum_{h \neq g^{-1}} p_{h^{-1}} q_h$ has spectral radius less than one. Thus all eigenvalues of $q_g p_g^{-1}$ and $R_g$ have positive real part. Using (2.31), the same argument shows that $z$ and $Z$ have all their eigenvalues with positive real parts.

Finally, from Equation (2.31), we have $Z = I - \sum_g P_g Q_g = I - \sum_g P_g R_g P_g$. We deduce that

$$Z = I - \frac{1}{2} \sum_{g \in S} \left( P_g \sqrt{4I + (P_g^{-1}Z)^2} - Z \right). \qquad (2.34)$$

Up to this issue of square root, we thus have found a fixed point equation satisfied by $z$ (in Equation (2.34)) and expressed $q_g$ as a function of $(z, p_g, p_{g^{-1}})$ (in Equation (2.33)). If $r = 1$, we can retrieve a known formula for colourless random walks. We note that Equation (2.34) should be compared to Proposition 3.1 in Lehner [115] where a related formula is derived in a self-adjoint case (it can be checked that $2z$ is the inverse of the diagonal term of the Green function $(I - \tilde{P})^{-1}(e, e)$ where $(I - \tilde{P})^{-1}$ is seen as an infinite matrix indexed by $G \times G$ with coefficients in $M_r(\mathbb{C})$).

## 2.4 Computing drift and entropy

For classical convolution random walks, the general formulas for the rate of escape and entropy given in Theorem 2.3 go back to the work of Furstenberg [76] and are well known. The proofs extend easily to coloured random walks, so we will not give further details. We refer to Ledrappier [114] and the influential paper by Kaimanovich and Vershik [102] for the case of free groups; to the works of Mairesse [129], Mairesse and Matheus [130], Gilch [78, 77] for more general free products. See also the paper of Nagnibeda and Woess [138].
We now turn to the derivation of (2.4) from the integral formula (2.14). The latter shows that the computation of the entropy ultimately comes down to the computation of some Radon-Nikodym derivatives. In the colourless case, this computation goes basically as follows. Consider a cylinder $\xi_1 \cdots \xi_n$. Compute $g \cdot p^\infty(\xi_1 \cdots \xi_n)$ distinguishing the different cases occurring:

* if $g = \xi_1$ then $g \cdot p^\infty(\xi_1 \cdots \xi_n) = p^\infty(\xi_2 \cdots \xi_n)$

* if $\xi_1 \in G_i, g \neq \xi_1$ and there exists $h \in G_i$ such that $gh = \xi_1$, then $g \cdot p^\infty(\xi_1 \cdots \xi_n) = p^\infty(h\xi_2 \cdots \xi_n)$

* otherwise, $g \cdot p^\infty(\xi_1 \cdots \xi_n) = p^\infty(g^{-1}\xi_1 \cdots \xi_n)$.

As one can check, the last case occurs if and only if $\xi_1 \in \text{Next}(g^{-1})$. Expand now the expressions above into products using from (2.26) that $p^\infty(\xi_1 \cdots \xi_n) = q_{\xi_1} \cdots q_{\xi_{n-1}} \mu_{\xi_n}$ to get

$$ \frac{g \cdot p^{\infty}(\xi_1 \cdots \xi_n)}{p^{\infty}(\xi_1 \cdots \xi_n)} = \begin{cases} 1/q_g & \text{if } \xi_1 = g, \\ q_{g^{-1}} & \text{if } \xi_1 \in \text{Next}(g^{-1}), \\ q_h/q_{\xi_1} = q_{g^{-1}\xi_1}/q_{\xi_1} & \text{if } h \in S \text{ and } gh = \xi_1. \end{cases} $$

One can then easily express the integral (2.14) in terms of the scalars $p_g, q_g$ and $\mu_g$ and obtain the formulas given in [114, 130].

For coloured random walks, the same computations can be made with matrices except that the cancellation between products no longer takes place. Instead, one has to deal with an infinite product of random matrices. For example, as one might guess from (2.21)-(2.26), it is true that

$$ \frac{dg p_v^\infty(\xi)}{dp_u^\infty(\xi)} = \lim_{n \to \infty} \frac{\mathbb{1}_v^\top q_{g^{-1}} q_{\xi_1} \cdots q_{\xi_{n-1}} \mu_{\xi_n} \mathbb{1}}{\mathbb{1}_u^\top q_{\xi_1} \cdots q_{\xi_{n-1}} \mu_{\xi_n} \mathbb{1}} \quad \text{a.s.,} \quad (2.35) $$

if $\xi_1 \in \text{Next}(g^{-1})$. Convergence as above is the object of the next subsection.

### 2.4.1 Convergence in direction for inhomogeneous products of matrices

In this final subsection, we prove Theorem 2.4. The computation of the Radon-Nikodym derivatives in the integral formula of the entropy requires to investigate infinite products of random, non-negative matrices (that is, with non-negative entries). We use first use results for non-negative, deterministic matrices [152] to justify limits of infinite matrix products. This yields formulas like (2.35) and a first expression for the entropy (2.39). Then we use results for products of random matrices [35, 40] to describe the law of the limits obtained, which yields eventually Theorem 2.4.
**Convergence of the Radon-Nikodym derivatives.** Instead of the general results in [152], it turns out that we can directly use results from [53, 109] which already involved matrix products to study finite range random walks. It does not seem however that the methods used in these references can be interpreted as an application of the linearization trick.

Let $X$ be a finite set and $Y$ a subset of $X \times X$ such that for all $x \in X$, the set $\{y \in X, (x, y) \in Y\}$ is non empty. Let $\Sigma := X^{\mathbb{Z}}$ be the space of doubly infinite sequences $(\xi_n)_{n \in \mathbb{Z}}$ with values in $X$, such that $(\xi_n, \xi_{n+1}) \in Y$ for all $n \in \mathbb{Z}$. Let $\sigma : (\xi_n)_{n \in \mathbb{Z}} \mapsto (\xi_{n+1})_{n \in \mathbb{Z}}$ denote the standard shift on $\Sigma$ and given a function $f : \Sigma \to \mathbb{C}$ and $n \in \mathbb{N}$, write

$$S_n f := f + f \circ \sigma + \dots f \circ \sigma^{n-1}.$$

Recall the definition of $\mathcal{P}^+$ in (2.16). We will use the following formulation of a result of [109] on convergence of matrix products, but note that a similar result was already used in the earlier reference [53].

**Proposition 2.3 ([109, Prop 5.2]).** Let $(M_x)_{x \in X}$ be a family of $r \times r$ matrices with non-negative entries. Assume there exists integers $m \ge 0, k \ge 1$ and a function $B : X^k \to 2^{[r]} \setminus \emptyset$ (the set of non-empty subsets of $[r]$), such that for every $n \ge m$ and every family $x_1, \dots, x_{n+k} \in X$ with $(x_i, x_{i+1}) \in Y$ for all $i$,

$$(M_{x_1} M_{x_2} \cdots M_{x_{n+k}})_{u,v} > 0 \Leftrightarrow v \in B(x_{n+1}, \dots, x_{n+k}) \quad \forall u, v \in [r] \quad (2.36)$$

Then there exist constants $C > 0$ and $0 < \alpha < 1$, maps $\varphi, \gamma : \Sigma \to \mathbb{R}$ and $V, W : \Sigma \to \mathcal{P}^+$ such that for all $\xi \in \Sigma$,

$$\| e^{-S_n \varphi(\xi)} M_{\xi_1} M_{\xi_2} \cdots M_{\xi_n} - \gamma(\sigma_n \xi) V(\xi) W(\sigma^n \xi)^T \| \le C \alpha^n, \quad (2.37)$$

where $V = V(\xi_1, \xi_2, \dots)$ depends only on the "forward coordinates", while on the other hand $W = W(\xi_0, \xi_{-1}, \dots)$ depends only on the "backward coordinates". Furthermore,

$$M_{\xi_1} V(\sigma \xi) = e^{\varphi(\xi)} V(\xi). \quad (2.38)$$

Proposition 2.3 states shows under condition (2.36), the product $M_{\xi_1} M_{\xi_2} \cdots M_{\xi_n}$ tends up to renormalization factor to a rank one matrix whose range is spanned by the vector $V(\xi)$. This result is well known for powers of a matrix with positive entries, in which case the vector $V$ is nothing but the Perron-Frobenius eigenvector. Proposition 2.3 is thus a generalization of the Perron Frobenius theory to inhomogeneous products of non-negative matrices with possibly zero columns (condition (2.36)). We refer to [109] for additional properties of the functions $\varphi, \gamma$ with the vectors $V, W$ which will not be needed here.
*Proof.* Extend the definition (2.15) of matrices $q_g$ to the whole group and notice that if $g \in G$ writes as a reduced word $g = g_1 \cdots g_n$, then $q_g = q_{g_1} \cdots q_{g_n}$. We recall that given the set of generators considered (2.4) representatives are uniquely defined. Thus proving (2.36) comes down to prove that for $|g|$ large enough, $q_g(u, v) > 0$ if and only if $v$ is in some subset of $[r]$ that depends only on the last letters of $g$. This statement regarding the coloured random walk can be transferred to a statement about the initial walk as follows.

Consider the constructions of the linearized random walks in Section 2.2: both are made so that if $X_0 = e$ and $Y_0 = (e, 1)$, one can couple $(Y_n)_{n \ge 0}$ and $(X_n)_{n \ge 0}$ to have $X_n = Y_{\tau_n}$ where $\tau_n$ is the $n$-th return time at colour 1. Furthermore, for all colour $v \in [r]$, there exists (at least one) $h \in K$ with representative $h = h_1 \cdots h_k h_{k+1} \cdots h_l$ such that $\mathbb{P}_{(e,1)}[Y_k = (h_1 \cdots h_k, v)] > 0$. The main difference between the proposed linearization procedures is the number of such $h$ that one can associate to the colour $v$, but this has no consequence for what follows.

Let $K(v)$ be the set of such elements $h$. For each $h = h_1 \cdots h_k h_{k+1} \cdots h_l \in K(v)$, set $p(h) := h_1 \cdots h_k$ and $s(h) := h_{k+1} \cdots h_l$. Then consider the following events: given $a, g \in G$, $h = h_1 \cdots h_l \in K$, if there exists $k \le l$ such that $ah_1 \cdots h_k = g$, let

$$A_{a,h}(g) := \{ \exists n \ge 0 \mid X_n = a, X_{n+1} = ah \}$$

and $A_{a,h}(g) = \emptyset$ otherwise, and let $B_{a,h}(g)$ the event that $A_{a,h}(g)$ occurs before all other events $A_{b,h'}(g)$, $(b, h') \ne (a, h)$.

Suppose now $Y_0$ starts with colour $u$. By $G$-invariance of transition probabilities we can suppose that it is at $(e, u)$. Then the starting colour imposes the walk to transition towards $(s(h), 1)$ for some $h \in K(u)$. Once at state $(s(h), 1)$, $Y_n$ will visit $g$ if and only $X_n$, started at $s(h)$, makes a transition that goes through $g$, ie if and only if the event $A_{a,h'}(g)$ occurs for some $a \in G$, $h' \in K$. Thanks to the irreducibility of $X_n$ it is clear that such transitions occur, but the difficulty is to make sure that $Y_n$ can arrive for the first time at $g$ with the prescribed color $v$. This will occur with the events $B_{a,h'}(g)$ for $h' \in K(v)$ and $a = gp(h')^{-1}$. Given $x \in G$, $h \in K$, let $m_g(x, h) := \mathbb{P}_x[B_{gp(h')^{-1},h}(g)]$. What precedes thus sums up in the lower bound

$$q_g(u, v) \ge \mathbb{P}_{(e,u)}[\tau_{(s(h),1)} < \infty] m_g(s(h), h') \quad \forall h \in K(u), h' \in K(v)$$

where $\mathbb{P}_{(e,u)}[\tau_{(s(h),1)} < \infty] > 0$ is the probability that $Y_n$ visits $(s(h), 1)$. In particular, it now suffices to prove that for all $x, g \in G$, $h \in K$, the positivity of $m_g(x, h)$ depends only on $h$ and the last letters of $g$, provided $|g|$ is large enough. This can be shown in the same way as Lemma 5.3 in [109] where a similar result is proved.

Let $L$ be the largest length of elements in the support of $X_n$. By $G$-invariance of transition probabilities $m_g(x, h) = m_{x^{-1}g}(e, h)$ so one can in particular suppose $x = e$.
From the irreducibility of $X_n$, every element of the generating set $S$ can be reached by the random walk in a bounded number of steps $l$, because $S$ is finite. Therefore for $|g| > 2L+l$, any path of positive probability that goes from $e$ to $gp(h)^{-1}$ without passing through $g$ and then moves from $gp(h)^{-1}$ to $gp(h)^{-1}h = gs(h)$ can be extended with an initial loop between $e$ and any $s \in S$. From this we deduce that $m_g(e, h) > 0$ if and only if $m_g(s, h) = m_{s^{-1}g}(e, h) > 0$. Choosing $s$ as the first letter of $g$, we deduce that the positivity of $m_g(a, b)$ does not depend on it. Iterating this argument we obtain that it only depends on $h$ and the $2L+l$ last letters of $g$. □

**Law of Radon-Nikodym derivatives.** The previous result is purely deterministic and does not take into account that the process $(X_{\infty}^{(n)}, u_n)_{n \ge 0}$ is a Markov chain. Our goal in this paragraph is to determine the law of the probability vector $V$ appearing in Corollary 2.2. The monograph [35] (see also [40]) state results for products of iid random matrices which, as we shall see, apply to Markovian products as well.

Remploying the general framework of Proposition 2.3, consider a Markov chain $(Z_n)_{n \ge 0}$ on the finite state space $X$ with transition matrix $Q$ and $Y := \{(x, y) \in X \times X, Q(x, y) > 0\}$. Let $(M_x)_{x \in X}$ be a family of $r \times r$ non-negative matrices, such that condition (2.36) holds.

Consider the sequence defined by $Y_n := M_{Z_n}, n \ge 1$. By Proposition 2.3, a.s. the product $Y_1 \cdots Y_n$ is non-zero and converges in direction to a rank one matrix spanned by a random vector $V \in \mathcal{P}^+$. If one multiplies the product on the left by another matrix $M_x$, one still has a products of matrices $M_x$, so one can expect the law of $V$ to satisfy some invariance property.

For all non-negative matrix $A \in M_r(\mathbb{R})$ and all $z \in \mathcal{P}^+$, we define $Az$ to be the normalized image of $z$ (identified with a vector in $\mathbb{R}^r$) that makes it a probability vector, provided $Az \ne 0$. The latter case will not be an issue: condition (2.36) implies in particular that matrices $M_x$ have no zero row, and vectors of $\mathcal{P}^+$ have no zero coordinate so $M_x z$ is well defined for all $x \in X, z \in \mathcal{P}^+$.

Since $Z_n$ is a Markov chain, the law of $V$ may depend on the starting state of $Z_n$. Hence it is natural to think of it as a coloured measure (colours being here the states $x \in X$).

**Definition 2.5.** A family $\nu = (\nu_x)_{x \in X}$ of probability measure on $\mathcal{P}^+$ is called a coloured measure. Let $Q * \nu$ denote the coloured measure defined by

$$ \int f(z) d(Q * \nu)_x(z) = \sum_y \int f(M_y z) Q(x, y) d\nu_y(z) $$

for all bounded measurable function $f$ on $\mathcal{P}^+$ and $x \in X$. The coloured measure $\nu$ is said to be invariant if $Q * \nu = \nu$.
**Lemma 2.3.** Let $\nu_x$ be the law of $V$ when $Z_n$ is started at $x$, the coloured measure $(\nu_x)_{x \in X}$ is the unique coloured measure which is invariant with respect to $Q$.

*Proof.* We use Markov property together with (2.38) to obtain the invariance of the law of $V$.

The proof of uniqueness is similar to the proof for the harmonic measure in Proposition 2.1. Consider another invariant coloured measure $(\rho_x)_{x \in X}$. By invariance, for all bounded measurable function $f$ on $\mathcal{P}^+$ the sequence

$$M_n := \int f(Y_1 \cdots Y_n w) d\rho_{Z_n}(w), \quad n \ge 0$$

is a bounded martingale with respect to the filtration $\mathcal{F}_n := \sigma(Z_0, Z_1, \dots, Z_n)$, so $M_n$ converges a.s. and in $L^1$. This being true for all bounded measurable function, this implies the measures $Y_1 \cdots Y_n * \rho_{Z_n}$ converges weakly to a measure. Now, because the product $Y_1 \cdots Y_n$ converges in direction to $V$, the limit is necessarily the Dirac mass at $V$.

On the other hand, the martingale property with the $L^1$ convergence gives that for all bounded measurable functions $f$ on $\mathcal{P}^+$, for all $x \in X$,

$$\mathbb{E}_x[f(V)] = \mathbb{E}_x\left[\int f \delta_V\right] = \int f d\rho_x.$$

Therefore $\rho_x$ must be the law of $V$ when $Z_0 = x$, that is $\rho_x = \nu_x$, and is consequently unique. $\square$

We are finally ready to prove Theorem 2.4.

*Proof of Theorem 2.4.* We apply Lemma 2.3 in the context of coloured random walks, with $X = S \times [r]$ and $Q((g, u)(h, v)) = \mu_h(u, v)$. Due to the form of the transition probabilities the law of $V$ is only indexed by colours. It remains to use Corollary 2.2 in conjunction with the integral formula of the entropy given by Theorem 2.3. $\square$
# Chapter 3

## Accelerating abelian random walks with hyperbolic dynamics

This chapter is adapted from the paper [65], done jointly with Laurent Massoulié.

### 3.1 Introduction

In [49], Chung Diaconis and Graham investigated the behaviour of a Markov chain on $Z/nZ$ defined by $X_{t+1} = aX_t + B_t$, with $(B_t)$ a sequence of iid increments distributed on $\{-1, 0, 1\}$. They proved for $a = 2$ that after $t = O(\log n \log \log n)$ steps the distribution of $X_t$ is close to uniform, thus showing a dramatic speed-up over the simple random walk, which needs $\Omega(n^2)$ steps. Recently, attention has been brought back to the potential speed-up obtained by applying deterministic functions to Markov chains [45, 87, 88, 18]. In this work, we study an analog of the Chung-Diaconis-Graham process in the multi-dimensional case. This case has been previously studied [8, 100, 9, 106] however the bounds proved in these papers did not match those of dimension one, or only in specific cases. This work improves these results and aims to provide a new look on the speed-up caused by the doubling map.

#### 3.1.1 Main results

Let $d \ge 2$ be an integer, $\mu$ a finitely supported probability measure on $Z^d$. We write $\text{GL}_d(Z)$ for the set of invertible matrices with integer entries and integer-valued inverse. A matrix is hyperbolic if it has no eigenvalue of modulus 1. Given $n \ge 1$ and $A \in \text{GL}_d(Z)$ an invertible hyperbolic matrix, consider the discrete-time random walk $(X_t)_{t \ge 0}$ on $(Z/nZ)^d$ defined by

$$X_0 := 0 \qquad X_t = AX_{t-1} + B_t \quad \text{mod } n \quad \forall t \ge 1 \qquad (3.1)$$
where $B_t$ are iid random variables on $\mathbb{Z}^d$ with distribution $\mu$. Such random walks have been first considered by Chung, Diaconis and Graham in [49] in the case $d = 1, A = 2$.

A induces a bijection on the finite set $(\mathbb{Z}/n\mathbb{Z})^d$. It is easy to see from this that the uniform measure $U$ on $(\mathbb{Z}/n\mathbb{Z})^d$ is invariant for $X_t$, so $X_t$ will converge in law to $U$ provided it is irreducible and aperiodic. Convergence to stationarity of finite Markov chains is classically measured by total variation distance: for any pair of measures $p, q$ on a finite set $X$, one sets

$$ \|p - q\|_{\text{TV}} := \max_{A \subseteq X} |p(A) - q(A)| = \frac{1}{2} \sum_{x \in X} |p(x) - q(x)|. $$

The mixing time is then defined as the time needed for a Markov chain to get at distance at most $\epsilon$ to its stationary distribution, for a fixed parameter $\epsilon$.

Let $\text{supp } \mu$ denote the support of $\mu$ and consider $H$ the smallest $A$-invariant subgroup of $\mathbb{Z}^d$ that contains $\text{supp } \mu - \text{supp } \mu := \{x - y : x, y \in \text{supp } \mu\}$.

As a subgroup of $\mathbb{Z}^d$, $H$ is itself isomorphic to $\mathbb{Z}^k$ for some integer $k \le d$; see for instance [110, Thm 7.8]. More precisely, there exists a basis of $\mathbb{Z}^d$, that is a family $(u_i)_{i=1}^d$ that generates $\mathbb{Z}^d$ as a group, and positive integers $(a_i)_{i=1}^k$, such that $H$ is the subgroup generated by $(a_i u_i)_{i=1}^k$. The integer remark $H := k$ is called the rank of $H$ and is equal to the dimension of the $Q$-subvector space of $Q^d$ spanned by $H$. Our first result gives an upper bound on the mixing time of the same order as the one given by Chung, Diaconis and Graham in [49]. It applies to any dimension $d \ge 2$ and improve the results of [9, 100].

**Theorem 3.1.** Let $d \ge 2$ be an integer, $\mu$ a probability measure on $\mathbb{Z}^d$ and $A \in \text{GL}_d(\mathbb{Z})$. Let $(B_t)_{t \ge 1}$ be iid random variables with law $\mu$ and consider the random walk $(X_t)_{t \ge 0}$ on $(\mathbb{Z}/n\mathbb{Z})^d$ defined by (3.1).

Let $P^t(0, \cdot)$ denote the distribution of $X_t$ and $U$ the uniform measure on $(\mathbb{Z}/n\mathbb{Z})^d$. Let $H$ be the smallest $A$-invariant subgroup of $\mathbb{Z}^d$ that contains $\text{supp } \mu - \text{supp } \mu$. Suppose $H$ is of rank $d$, generated by $(a_i u_i)_{i=1}^d$ for some basis $(u_i)_{i=1}^d$ of $\mathbb{Z}^d$ and positive integers $(a_i)_{i=1}^d$. If $A$ is hyperbolic, there exists a constant $C > 0$ such that, for all $n$ coprime with all the $a_i$, if $t > C \log n \log \log n$ then $\|P^t(0, \cdot) - U\|_{\text{TV}} \to 0$ as $n \to \infty$.

**Remark 3.1.** The hyperbolicity assumption on $A$ is essential. Theorem 3.11 of [9] shows that if $A$ has an eigenvalue which is a root of unity, $\Omega(n^2)$ steps are necessary. The proof of Theorem 3.1 will use extensively the properties of the deterministic dynamical system $x \mapsto A^\top x$ on the continuous torus $\mathbb{R}^d/\mathbb{Z}^d$. Such dynamical systems are commonly refered to as hyperbolic toral automorphisms and are typical examples of dynamical systems exhibiting chaotic properties. Thus Theorem 3.1 and its proof suggest that the speed-up observed is the consequence of specific features of hyperbolic dynamical systems.
Remark 3.2. On the other hand, the invertibility assumption on A seems superfluous. We conjecture it suffices to have det A ≠ 0 and restrict to n coprime with det A, as it is already the case for dimension 1 [49, 94, 95]. To prove Theorem 3.1 we make use of Markov partitions, which apply essentially to invertible maps. Many arguments in this work, even those about Markov partitions, only use "forward trajectories" and could thus be extended to the non-invertible case. The main issue is thus to show existence of Markov partitions for non invertible maps.

Remark 3.3. As one can guess, the condition given on H and n is necessary to have irreducibility and aperiodicity of the random walk. This will be proved subsequently in Proposition 3.6. Thus Theorem 3.1 shows that for all n, O(log n log log n) steps are sufficient to reach stationarity as long as convergence holds.

Remark 3.4. Let us remark also that there is no loss of generality in supposing the walk is started at 0. Indeed, should the random walk start at x ∈ (Z/nZ)d, we can always write X_t = A^t x + X̃_t with X̃_t a random walk started at 0. Since A^t x is deterministic, it does not affect total variation distance.

Our second result establishes a lower bound on the mixing time, under a condition of finite entropy. Given any measure p on a discrete set X, we recall the entropy of p is defined as

$$
H(p) := - \sum_{x \in X} p_x \log p_x.
$$

**Theorem 3.2.** Let $\mu$ be a measure on $\mathbb{Z}^d$ with finite entropy. Let $(X_t)_{t \ge 0}$ be as in (3.1). Then

$$
\| P^t(0, \cdot) - U \|_{\text{TV}} \ge 1 - \frac{tH(\mu) + \log 2}{\log n}. \quad (3.2)
$$

The upper bound of Theorem 3.1 is valid for all $n$, as long as convergence to uniformity holds. As it was already the case for the Chung-Diaconis-Graham process in dimension one, it turns out that for almost all $n$ tending to infinity only $O(\log n)$ steps suffice to reach stationarity. A property $\mathcal{P}$ is satisfied by almost all integer if the proportion of integers smaller than $n$ that satisfy $\mathcal{P}$ tends to 1 as $n \to \infty$.

**Theorem 3.3.** Consider the setting of Theorem 3.1. There exist a constant $C$ such that for almost all $n$, if $t > C \log n$ then $\|P^t(0, \cdot) - U\|_{\text{TV}} \to 0$ as $n \to \infty$.

Affine random walks defined by (3.1) allow in particular to study random walks defined by recursions of higher order. For instance the so-called Fibonacci random walk on $\mathbb{Z}/n\mathbb{Z}$, $X_{t+1} = X_t + X_{t-1} + B_{t+1}$, studied in [45], can naturally be written as an affine random walk, using the matrix $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, which is hyperbolic. Theorems 3.1 and 3.3 thus imply that when convergence holds, $O(\log n \log \log n)$ or $O(\log n)$ steps
are sufficient to reach stationarity. This applies in particular to the case where $B_t$ is uniform in $\{-1, 0, 1\}$ and improves the result of [45].

*Remark 3.5.* From Theorem 3.3, one may inquire if the upper bound of $O(\log n)$ is valid for all $n$. We conjecture it is not. In dimension $d=1$, $A=2$ and $B_t$ uniform in $\{0, \pm 1\}$, [49] gives specific values of $n_k$, including $n_k = 2^k - 1$, for which $O(\log n_k \log \log n_k)$ is in fact the right order of magnitude. This phenomenon occurs because for such $n_k$, the map induced by $x \mapsto 2x$ on $\mathbb{Z}/n\mathbb{Z}$ has order $O(\log n_k)$. Thus we expect that for certain distributions of $B_t$, $O(\log n \log \log n)$ is indeed the right mixing time whenever the permutation induced by the matrix $A$ has order $O(\log n)$. This could be an interesting question for future research.

### 3.1.2 Related works

On the Chung-Diaconis-Graham process, ie the case $d=1$, great effort has been made to improve the bounds on the mixing rates, see [95, 96, 97, 98, 141]. The latest paper is [68], where Eberhard and Varjú eventually established the cutoff phenomenon at entropic time $\log n/h$ for almost all $n$ and some entropic constant $h$.

There has also been interest for generalizations of this process: Hildebrand considered the case $X_t = a_t X_{t-1} + B_t$ where a new random multiplier $a_t$ is applied at each step [94, 99], while Asci [8, 9] and Hildebrand, McCollum [100] considered $d$-dimensional generalizations, obtaining upper bounds of order $O((\log n)^2)$. Asci [9] and recently Klyachko [106] managed to prove order $O(\log n \log \log n)$ for specific cases in dimension 2. Our results improve on these works, giving a $O(\log n \log \log n)$ upper bound for any hyperbolic matrix $A \in \text{GL}_d(\mathbb{Z})$. One crucial argument in the one-dimensional case was the use of the binary decomposition in order to identify the dynamical system $x \mapsto 2x$ on $\mathbb{R}/\mathbb{Z}$ with a shift, which a priori had no direct extension to the multi-dimensional case, thus accounting for the difference in the order of magnitude. Klyachko [106] uses a similar technique, $\beta$-ary expansions, to get the $\log n \log \log n$ bound. This work uses the theory of Markov partitions which provides a general framework where dynamical system can be identified to shifts. Both kind of expansions are related. Another related result is [59], where Diaconis and Graham investigated the case of an affine random walk on the hypercube. With our notations this would amount to taking $n=2$ and $d \to \infty$, which is not a case covered here.

On the other hand, the effect of applying deterministic bijections on the mixing times of Markov chains has been recently reconsidered from a general point of view. In [32], Bordenave, Qiu and Zhang prove an upper bound on the second eigenvalue of the product of a bistochastic matrix with a uniform permutation. In [45] Diaconis and Chatterjee consider a generic Markov chain on $n$ states, and give a geometric
condition on deterministic bijections which yields a mixing time of order $O(\log n)$. This condition is made to increase the expansion of the Markov chain to $\Omega(1)$, a property known to imply mixing in $O(\log n)$. Moreover, it holds with large probability when the bijection is chosen uniformly at random, so almost every bijection actually yields fast mixing. Those results were subsequently improved by Ben Hamou and Peres in [18], who established the cutoff phenomenon at entropic time in the case the bijection is picked uniformly at random.

Although speed-up occurs with almost every bijection, it was noticed however in [45] that the doubling map $x \mapsto 2x$ does not fall in that category, so expansion is not the reason accounting for the acceleration. Thus a second goal of our work is to suggest an alternative explanation as to why the doubling map improves the mixing rate. As explained in Remark 3.1, at the heart of our proof is the behaviour of the hyperbolic dynamical system $x \mapsto A^\top x$. Hence the speed-up established here may be specific to such maps and of a different nature than the acceleration proved for almost all bijection.

Finally, let us mention two other examples of explicit deterministic bijections implying speed-ups that have been studied. On the cycle $Z/pZ$ with $p$ prime, He [87] proves an almost linear mixing time in $p$ when the bijection considered is a rational function. This bound has been improved in [88] in the specific case of the inverse function $f: x \mapsto 1/x$ if $x \neq 0$, $f(0) := 0$, where He, Pham and Xu shows that $O(\log p)$ steps suffice to reach stationarity.

### 3.1.3 Discussion

In the two following paragraphs we discuss motivations and related models.

**Random matrices:** One can inquire about applying random matrices instead of deterministic ones, ie consider random walks of the form $X_t = A_t X_{t-1} + B_t$, with for instance $(A_t)_{t \ge 1}$ iid random matrices. For $d=1$, such cases were considered in [94, 99].

The simplest randomness we can add is by taking $A_t = A^{\epsilon_t}$ where $\epsilon_t$ are iid Bernoulli random variables of parameter $1/2$. This may slow down the convergence to stationarity, for instance with $B_t$ corresponding to increments of the simple random walk. With constant $A$, acceleration comes from applying successive powers $A^t$ to the random increments $B_k$. Now with $A_t = A^{\epsilon_t}$ the exponent of $A$ is to be replaced with the $t$-th step a random walk on $\mathbb{Z}$. Because of the diffusive behaviour of the random walk on $\mathbb{Z}$, it is of order at most $O(\sqrt{t})$. As a consequence, the mixing time becomes $O((\log n)^2)$. This can be proven with the same argumentation as in [99], which treats the case $d=1$.

Another case which can be considered is when $A_t$ are iid with distribution $\nu$, such that the subgroup generated by $\text{supp} \nu$ is $\text{SL}_d(\mathbb{Z})$. In this case, it is possible to prove
acceleration to ($O(\log n)$), without restriction on $n$, while removing the constraint that the matrices have no eigenvalues of modulus 1. The idea is to consider the evolution of the pair $(X_t, S_t)$ with $S_t := A_1 \cdots A_t$. Since the $A_t$ are iid, the process $(X_t, S_t)$ is a convolution random walk, ie a product of iid increments, on the semi-direct product $(\mathbb{Z}/n\mathbb{Z})^d \times \text{SL}_d(\mathbb{Z}/n\mathbb{Z})$, whose group operation is defined by $(x, A)(y, B) = (x+Ay, AB)$. This random walk can then be obtained as the reduction modulo $n$ of a convolution random walk on the infinite group $\mathbb{Z}^d \times \text{SL}_d(\mathbb{Z})$. Such groups have been extensively studied for their expansion properties, as they give rise to deterministic constructions of families of expander graphs, including quotients $\text{SL}_d(\mathbb{Z}/n\mathbb{Z})$. We refer to the monography of Tao [157] for an introduction to this topic.

Since expansion is related to the fast-mixing of simple random walks, the same tools can be used to prove fast mixing of affine random walks. Incidentally, such results have already been used in [88] to prove speed-up for the inverse mapping on $\mathbb{Z}/p\mathbb{Z}$. Let us give a few examples.

Let $S$ be a finite symmetric set of generators of $\mathbb{Z}^d \times \text{SL}_d(\mathbb{Z})$ and consider the Cayley graph $G_n = (V_n, E_n)$ where $V_n = (\mathbb{Z}/n\mathbb{Z})^2$ and $(x, y) \in E_n$ is an edge if and only if there exists $s = (z, A) \in S$ such that $y = sx := Ax + z$. Consider the simple random walk, which at each step is multiplied by a uniform element of $S$. To ensure aperiodicity we can always impose laziness, ie allow the walk to stay put with positive probability. Theorem 2.4.1 in [157] proves that the graphs $G_n$ are expanders, which implies that the (lazy) simple random walk mixes in $O(\log n)$ steps. In particular this applies to the random walk on $(\mathbb{Z}/n\mathbb{Z})^2$ which has holding probability $1/2$ and otherwise moves from $(x, y)$ to $(x \pm 1, y)$, $(x, y \pm 1)$, $(x \pm y, y)$ or $(x, y \pm x)$ with probability $1/16$.

Let us finally mention the result of [118], which shows that the expansion of a simple random walk on a semi-direct product $(\mathbb{Z}/p\mathbb{Z})^d \times \text{SL}_d(\mathbb{Z}/p\mathbb{Z})$, $p$ prime, and that of the projection to $\text{SL}_d(\mathbb{Z}/p\mathbb{Z})$, are of the same order. Hence in this case the mixing properties of an affine random walk are essentially determined by the product of random matrices.

**Interacting random walks:** There has been another motivation to generalizing the result of [49] to the high-dimensional case. Suppose one has two Markov chains $(X_t)$, $(Y_t)$ on the same finite state space. Would it be possible to make them "interact" in such a way as to accelerate the convergence to stationarity? A natural example of interaction is group multiplication. Thus one could investigate Markov chains $Z_t = (X_t, Y_t)$ on $G \times G$, with $G$ a finite group, defined for instance such that, with some probability we add to $Z_t$ a random increment, and with remaining probability we make its two coordinates interact, in the sense that either $X_{t+1} := Y_t X_t$ or $Y_{t+1} := Y_t X_t$ with some
probability. Such models were proposed in [45]: given a finite set $S$, $P$ a transition
matrix on $S$ and $f: S^d \to S$ a function such that $f(\cdot, x_2, \dots, x_d)$ is a bijection for all
$x_2, \dots, x_d$, the authors inquire about the random walk that moves deterministically
from a state $(X_1, \dots, X_d)$ to the state $(X_2, \dots, X_{d-1}, f(X_1, \dots, X_d))$ and then takes a
step of $P$ in the last coordinate. The latter model allows in particular to study Markov
chains defined by recursion of higher order, like $X_{t+1} = X_t X_{t-1} B_{t+1}$ with $(B_t)$ a sequence
of i.i.d. random variables on the group. However at this stage there is no general result
on the mixing rates of such Markov chains.

A case at hand is that of Abelian groups. When the group is Abelian, bijections
such as $(x, y) \mapsto (y, x + y)$ are group homomorphisms. Moreover every finite Abelian
group $G$ is isomorphic to a product of cyclic groups $G \simeq \prod_i \mathbb{Z}/k_i\mathbb{Z}$, and one can ensure
uniqueness of the $k_i$ by imposing that $k_i$ divides $k_{i+1}$ for all $i$; see [110, Thm 7.7]. Then
$G^d \simeq \prod_i (\mathbb{Z}/k_i\mathbb{Z})^d$ and the previous homomorphisms are those obtained by taking a
matrix $A \in GL_d(\mathbb{Z})$ and applying $A$ to each $i$-th coordinate. Thus the projection on an
affine random walk on the $i$-th coordinate yields an affine random walk on the torus
$(\mathbb{Z}/k_i\mathbb{Z})^d$, to which we can apply Theorem 3.1.

What about non-linear interactions? The proof technique initiated in [49] which has
been central to all works on affine random walks of $(\mathbb{Z}/n\mathbb{Z})^d$ relies heavily on linearity.
The question therefore remains open. Let us remark though that when the bijection
takes the form of random multiplications between coordinates in $G^d$, the model looks
very similar to the so-called product replacement algorithm. The latter is designed to
construct uniform sets of generators of a finite group. Given a $k$-uplet of generators of
a group $G$, the algorithm consists at each step, to select two generators at random and
multiply one by the other. Bounds of order $\log|G|$ on the mixing time are available
when $G$ is Abelian. In the general case this is conjectured to be the correct order, as
it would be the consequence of Kazhdan's (T) property for the automorphism groups
of free groups; see [125, 144]. As far as we know this is still an open question.

**Organization of the chapter**

We start by proving the lower bound in Section 3.2. Section 3.3, which forms the
crux of the chapter, contains the essential arguments used in the proof of Theorem
3.1, including results from hyperbolic dynamics. It is followed by Section 3.4, where we
establish that the necessity of conditions in 3.1 for irreducibility and aperiodicity. Then
in Section 3.5 we prove Theorem 3.3. Finally, Section 3.6 provides the definitions and
proofs of the results about hyperbolic dynamics that are needed in the other sections.
## 3.2 A lower bound for all $n$: proof of Theorem 3.2

Entropic arguments to get lower bounds on mixing times have become standard. The following inequality, due to Fannes and Audenaert [10], was already used in [88]. An entropic argument was also used in [68] to lower bound the mixing time and prove the cutoff phenomenon.

**Proposition 3.1** (Fannes and Audenaert [10]). Let $\mu, \nu$ be two probability measures defined on a finite set of size $N \ge 1$. Let $\epsilon := \|\mu - \nu\|_{\text{TV}}$ denote their total variation distance. Then

$$|H(\mu) - H(\nu)| \le \epsilon \log(N - 1) + H(\epsilon) \quad (3.3)$$

where $H(\epsilon) = -\epsilon \log \epsilon - (1 - \epsilon) \log(1 - \epsilon)$ is the entropy of a Bernoulli random variable of parameter $\epsilon$.

*Proof of Theorem 3.2.* We can bound the entropy of a Bernoulli random variable by $\log 2$, hence Proposition 3.1 shows

$$\|P^t(0, \cdot) - U\|_{\text{TV}} \ge 1 - \frac{H(X_t) + \log 2}{\log n}.$$

On the other hand the entropy of $X_t$ grows at most linearly as $tH(\mu)$. Indeed we can construct $X_t$ as $X_t = Y_t \mod n$, where $Y_t$ is an affine random walk on $\mathbb{Z}^d$ defined by $Y_0 := 0, Y_t := AY_{t-1} + B_t$ for all $t \ge 1$. Using the well known fact that entropy is non-increasing under deterministic transforms yields $H(X_t) \le H(Y_t)$. Using conditional entropies, we can then notice $(H(Y_t))_{t \ge 0}$ forms a subadditive sequence, as

$$\begin{aligned} H(Y_{t+s}) &\le H(Y_{t+s}, Y_t) = H(Y_t) + H(Y_{t+s}|Y_t) \\ &= H(Y_t) + H(Y_s) \end{aligned}$$

To get the second line, notice that one can write $Y_{t+s} = A^s Y_t + Z_s$ with $Z_s$ a random variable independent from $Y_t$ and distributed like $Y_s$, so that $H(Y_{t+s} | Y_t) = H(Y_s)$. As a consequence of subadditivity, $H(Y_t) \le tH(Y_1) = tH(\mu)$, which proves the result. $\square$

## 3.3 An upper bound for all $n$: proof of Theorem 3.1

**Main idea of the proof.** The basic idea is to use Fourier analysis: by the classical upper bound lemma of Diaconis and Shahshahani (see (3.4) below), the $\ell^2$-distance between the law $P^t := P^t(0, \cdot)$ of the random walk and the uniform measure can be expressed in terms of $\widehat{P^t}$, the discrete Fourier transform of the law. However, by the linearity of the dynamics, the process $X_t$ is a sum of independent random variables, so its Fourier transform factorizes. The factors of $\widehat{P^t}$ are the Fourier transform $\hat{\mu}$ of
$\mu$ composed with successive powers of $A^\top$, the transpose of the matrix $A$. The goal will thus be to get the best upper bound on $|\hat{\mu}((A^\top)^s \rho)|$ for all $\rho \in (\mathbb{Z}/n\mathbb{Z})^d$, $\rho \neq 0$. Considering a function $f$, independent of $n$, defined on the continuous torus $\mathbb{R}^d/\mathbb{Z}^d$ such that $f(\rho/n) = |\hat{\mu}(\rho)|$ for all $\rho \in \mathbb{T}_n$, we will then identify a compact subset $W^c$ of $\mathbb{R}^d/\mathbb{Z}^d$ on which $f$ is bounded by a constant $\gamma < 1$. Thus we can bound $\hat{P}^t(\rho)$ by $\gamma^l$, where $l$ is the number of steps $s \le t$ for which $(A^\top)^s \rho \in W^c$. For that matter, we will use the theory of hyperbolic toral automorphisms to code such orbits by bi-infinite sequences. By doing so, the map $x \mapsto A^\top x$ gets identified with a shift, which allows to bound the number of times the orbits cross $W^c$.

### 3.3.1 Fourier analysis on the torus

Let $n \ge 1$ be an integer. From now on we write $\mathbb{T}_n := (\mathbb{Z}/n\mathbb{Z})^d$. Let $(X_t)_{t \ge 0}$ be defined as in (3.1), and for all $t \ge 0$ write $P^t$ for the law of $X_t$.

Let $\langle \cdot, \cdot \rangle$ be the usual inner product on $\mathbb{R}^d$. Given $\rho \in \mathbb{T}_n$ and a function $f$ on $G$, the Fourier transform of $f$ at $\rho$ is

$$ \hat{f}(\rho) := \sum_{x \in \mathbb{T}_n} f(x) e^{2i\pi \langle x, \rho \rangle / n}. $$

In this expression $x, \rho$ are implicitly identified with their representative in $[0, n-1]^d$. Due to the $2\pi$-periodicity of the complex exponential, the result is independent of the choice of representatives. Such identifications will be done frequently in the sequel without further explicit mention.

Bounds on mixing times can be obtained through Fourier transforms thanks to the upper bound lemma of Diaconis and Shahshahani [56]. Recall $U$ denotes the uniform measure on $\mathbb{T}_n$. In the present setup it yields that for any measure $\nu$ on $\mathbb{T}_n$:

$$ 4 \|\nu - U\|_{\text{TV}} \le \sum_{g \ne 0} |\hat{\nu}(g)|^2. \qquad (3.4) $$

This bound will be applied to $P^t$. The linearity of the problem yields a nice factorization of the Fourier transform, as shown by the following lemma, initially due to Asci [8]:

**Lemma 3.1.** For all $t \ge 1$, for all $\rho \in \mathbb{T}_n$,

$$ \widehat{P}^t(\rho) = \prod_{j=0}^{t-1} \hat{\mu}((A^\top)^j \rho). \qquad (3.5) $$
*Proof.* Applying the definition of the Fourier transform, for all $t \ge 1$,

$$ 
\begin{aligned}
\widehat{P^t}(\rho) &= \sum_{\substack{x \in \mathbb{T}_n \\ y \in \text{supp } \mu}} P^{t-1}(x)\mu(y)e^{2i\pi\langle Ax+y, \rho \rangle/n} \\
&= \sum_{x \in \mathbb{T}_n} P^{t-1}(x)e^{2i\pi\langle x, A^\top \rho \rangle/n} \sum_{y \in \text{supp } \mu} \mu(y)e^{2i\pi\langle y, \rho \rangle/n} \\
&= \widehat{P^{t-1}}(A^\top \rho)\hat{\mu}(\rho)
\end{aligned}
$$

which gives the result by induction, since $\widehat{P^0} = 1$. $\square$

### 3.3.2 Expansiveness

Let $\mathbb{T}^d := \mathbb{R}^d/\mathbb{Z}^d$. A induces a bijective map on $\mathbb{T}^d$, which is identified with $A$.

The factorization of the Fourier transform provided by Lemma 3.1 motivates the study of the deterministic dynamical system $x \mapsto A^\top x$ on $\mathbb{T}^d$. In the next section, we will see that by partitioning $\mathbb{T}^d$ into a finite number of "rectangles", we can represent any point by the sequence of rectangles its trajectory passes through. A key ingredient to make this representation work is the expansiveness property: the orbits of two distinct points must separate from each other at exponential rate. This in turn will ensure that provided rectangles of the partition are small enough, two distinct points cannot have their trajectories going through the exact same set of rectangles, hence representations are well-defined. Note that from Lemma 3.1 the results of the two next sections will be applied later on with $A^\top$.

Let us introduce the quotient metric on $\mathbb{T}^d$. Let $p$ be the natural projection of $\mathbb{R}^d$ onto $\mathbb{T}^d$. Given a norm $\|\cdot\|$ on $\mathbb{R}^d$, the quotient metric $d$, defined as

$$ d(x, y) = \inf \{ \|\hat{x} - \hat{y}\|, \hat{x} \in p^{-1}(x), \hat{y} \in p^{-1}(y) \} $$

makes $\mathbb{T}^d$ a compact metric space.

Since $A$ has no eigenvalue of modulus one, by factorizing the characteristic polynomial of $A$ into a product of irreducible factors and regrouping them, one can write it as the product of two real polynomials $P_u, P_s$, the eigenvalues of which all have modulus strictly above or below 1 respectively. Then $P_u, P_s$ being coprime, it is a standard result in linear algebra that $\ker P_u P_s(A)$ is the direct sum of $\ker P_u(A)$ and $\ker P_s(A)$. However by Cayley Hamilton theorem $\ker P_u P_s(A) = \mathbb{R}^d$. Thus we obtain the following decomposition which is the very heart of hyperbolic dynamics.

**Definition 3.1.** $\mathbb{R}^d$ can be decomposed as the direct sum of two subspaces $E_s$ and $E_u$, invariant by $A$ such that the restriction of $A$ to each of these subspaces has eigenvalues of modulus $|\lambda| < 1$ and $|\lambda| > 1$ respectively. $E_s$, resp. $E_u$ is called the stable subspace, resp. unstable subspace.
**Lemma 3.2.** There exists a norm $\|\cdot\|$ on $\mathbb{R}^d$ such that for all $x \in \mathbb{R}^d$ decomposing as $x = x_s + x_u$ with $x_s \in E_s$ and $x_u \in E_u$, $\|x\| = \max(\|x_s\|, \|x_u\|)$ and $\|A|_{E_s}\| < 1$, $\|A^{-1}|_{E_u}\| < 1$, where the norms considered are the operator norms induced by $\|\cdot\|$.

*Proof.* Start from any norm $\|\cdot\|$ on $\mathbb{R}^d$. Since all the eigenvalues of $A|_{E_s}$ have modulus strictly smaller than 1, there exists an integer $l \ge 1$ such that $\|A|_{E_s}^l\| < 1$. This can be proved with the Jordan's normal form of the matrix. Similarly there exits $l' \ge 1$ such that $\|A|_{E_u}^{-l'}\| < 1$. Taking the maximum of $l, l'$ we can suppose $l = l'$. Setting

$$ \|x\|' := \max \left\{ \sum_{k=0}^{l-1} \|A|_{E_s}^k x_s\|, \sum_{k=0}^{l-1} \|A|_{E_u}^{-k} x_u\| \right\} $$

for all $x = x_s + x_u$ yields an adapted norm $\|\cdot\|$'.

<figure><img src="image_10.png" /></figure>

A norm satisfying the properties of the lemma will be called adapted to $A$. From now on, we consider such an adapted norm $\|\cdot\|$ and the associated quotient metric $d$.

Finally let

$$ \lambda := \max(\|A|_{E_s}\|, \|A^{-1}|_{E_u}\|) < 1 \quad (3.6) $$

**Proposition 3.2.** Let $\epsilon > 0$ small enough so that $p$ is injective on $B(0, \epsilon \|A\|)$. Consider $x, y \in \mathbb{T}^d$ and define

$$ K_+ := \sup\{k \ge 0 \mid \forall l \le k, d(A^l x, A^l y) < \epsilon\}. $$

where by convention the supremum is taken as $-\infty$ if the corresponding set is empty, that is if $d(x, y) \ge \epsilon$. Otherwise let $v$ be the unique representative of $x - y$ in $B(0, \epsilon)$ and decompose it as $v = v_s + v_u$ with $v_s \in E_s$ and $v_u \in E_u$. Then

$$ \|v_u\| < \lambda^{K_+} \epsilon \quad (3.7) $$

In particular if $d(A^k x, A^k y) < \epsilon$ for all $k \ge 0$, then $y \in W_\epsilon^s(x)$.

The previous proposition is only concerned with future trajectories. Applying with $A^{-1}$ in place of $A$, it yields a dual statement on the past trajectories. Taken simultaneously with the forward statement, this yields a "two-sided" result for toral automorphisms. The last statement is what is traditionally refered to as the expansiveness property of toral automorphisms.

**Corollary 3.1.** Let $\epsilon > 0$ so that $p$ is injective on $B(0, \epsilon \max(\|A\|, \|A^{-1}\|))$. Consider

$$ K := \sup\{k \ge 0 \mid \forall l \in [-k, k] d(A^l x, A^l y) < \epsilon\}. $$

Then

$$ d(x, y) < \epsilon \lambda^K. \quad (3.8) $$

In particular if $d(A^k x, A^k y) < \epsilon$ for all $k \in \mathbb{Z}$ then $x = y$.
The smallest parameter $\epsilon$ satisfying Equation (3.8) is called the expansiveness constant of $A$ and will be denoted $\epsilon_c$.

*Proof of Proposition 3.2.* Assume without loss of generality that $d(x, y) < \epsilon$ to have $K_+ \ge 0$. Then for $k = 1$, $\|A^kv\| < \epsilon'$ so $A^kv$ is the unique representative in $B(0, \epsilon')$ of $A^k(x - y) \in \mathbb{T}^d$. Thus if $d(A^kx, A^ky) < \epsilon$ we deduce that $A^kv \in B(0, \epsilon)$. Iterating this argument, we get by induction that $A^kv \in B(0, \epsilon)$ for all $0 \le k \le K_+$.

Now since the norm is adapted to $A$, $\|v\| = \max(\|v_s\|, \|v_u\|)$ and thus $A^{K_+}v_u$ belongs to $B(0, \epsilon)$. Then

$$ \|v_u\| = \|A^{-K_+}A^{K_+}v_u\| < \|A^{-K_+}|_{E_u}\| \epsilon = \lambda^{K_+}\epsilon. $$

□

### 3.3.3 Symbolic Representations

The main ingredient in [49] that allows to get a mixing time of $O(\log n \log \log n)$ is the use of the binary decomposition to study the orbits of elements of the form $\rho/n$ under the doubling map $x \mapsto 2x$. The theory of symbolic representations and Markov partitions provides a generalization of the binary decomposition to the multidimensional setting and beyond. By making the dynamical system $x \mapsto Ax$ essentially conjugate to a shift, this will permit the same kind of analysis as for the doubling map.

The basic idea is as follows: given a finite partition $\mathcal{P} = \{P_1, \dots, P_m\}$ of $\mathbb{T}^d$, one may try to code an element $x \in \mathbb{T}^d$ by the subsets of $\mathcal{P}$ containing the orbit of $x$. For instance if for all $k \in \mathbb{Z}$, $A^kx \in P_{x_k}$, then one may try to identify $x$ with the sequence $(x_k)_{k \in \mathbb{Z}}$.

There is a main obstacle to this: without restriction on $\mathcal{P}$, two distinct elements may be coded by the same sequence. In the case of invertible hyperbolic automorphisms on the torus, it is possible to design well-suited families, called Markov partitions, to avoid this issue.

A Markov partition is not properly a partition: its sets, called rectangles, are closed sets with disjoint interiors but may have intersecting boundaries. Rectangles have additional properties but those are not necessary for the proofs of Theorems 3.1 and 3.3, so the definition is postponed to Section 3.6. The diameter of a Markov partition is the maximal diameter of its rectangles.

Given a Markov partition $\mathcal{R} = \{R_1, \dots, R_m\}$, define the adjacency matrix $\mathcal{A} = \mathcal{A}(\mathcal{R})$ as the $m \times m$ matrix with entries

$$ \mathcal{A}_{ij} = \begin{cases} 1 & \text{if } \mathrm{int}(R_i) \cap A^{-1}(\mathrm{int}(R_j)) \neq \emptyset \\ 0 & \text{otherwise.} \end{cases} \qquad (3.9) $$
Given an $m \times m$ adjacency matrix $\mathcal{A}$, define

$$ \Omega_A := \{ \omega \in [m]^Z : \forall k \in \mathbb{Z}, \mathcal{A}_{\omega_k, \omega_{k+1}} = 1 \}. \quad (3.10) $$

Let $\theta : (\omega_k)_{k \in \mathbb{Z}} \mapsto (\omega_{k+1})_{k \in \mathbb{Z}}$ be the shift operator on $\Omega_A$. $[m]$ denotes the set of integers from 1 to $m$ and $\Omega_A$ is given the product topology.

The following results are [37][Thm. 3.18, Thm. 3.12] applied to toral automorphisms, and will be proved in Section 3.6.

**Proposition 3.3.** For any hyperbolic matrix $A \in \text{GL}_d(\mathbb{Z})$, there exist Markov partitions of arbitrarily small diameter.

**Proposition 3.4.** Let $\mathcal{R}$ be a Markov partition and $\mathcal{A} = \mathcal{A}(\mathcal{R})$ be the associated adjacency matrix. Provided the diameter of $\mathcal{R}$ is small enough, for all $\omega \in \Omega_A$, the intersection $\cap_{k \in \mathbb{Z}} A^{-k}(R_{\omega_k})$ is reduced to a single point, denoted $\pi(\omega)$. The map $\pi : \Omega_A \to \mathbb{T}^d$ is continuous, finite-to-one, surjective and satisfies $\pi \circ \theta = A \circ \pi$.

*Remark 3.6.* In addition to being finite-to-one, the set of points which admit several coding sequences is actually negligible, in the sense that for all ergodic $\theta$-invariant measure with support $\Omega_A$, the set of points which have two images or more under $\pi$ has null measure; see [21][Thm 12.4].

A pair $(\Omega_A, \pi)$, as given in Proposition 3.4, or simply the map $\pi$, will be called a symbolic representation of the dynamical system $x \mapsto Ax$. Similarly for $\xi \in \mathbb{T}^d$, a sequence $\omega \in \pi^{-1}(\xi)$ will be called a symbolic representation of $\xi$. $\pi^{-1}(\xi)$ denotes here the inverse image of the singleton $\{\xi\}$. We omit braces when considering inverse image of singletons.

We will finally need the two following results about Markov partitions which form Lemma 1 and Corollary 11 of [36]. They are proved in Section 3.6.

**Proposition 3.5.** (i) If $x$ belongs to a rectangle $R \in \mathcal{R}$, then there exists $\omega \in \Omega$ such that $x = \pi(\omega)$ and $\omega_0 = R$.

(ii) If $\pi(\omega)$ is a periodic point, then $\omega$ is periodic.

### 3.3.4 Proof of Theorem 3.1

Let $\rho \in \mathbb{T}_n$ and $t \ge 1$. From the formula of the Fourier transform, multiply Equation (3.5) by its conjugate to obtain

$$ |\hat{P}^t(\rho)|^2 = \prod_{j=0}^{t-1} |\hat{\mu}((A^\top)^j \rho)|^2 \quad (3.11) $$

$$ = \prod_{j=0}^{t-1} \left( \sum_{x,y \in \text{supp } \mu} \mu(x)\mu(y) e^{2i\pi(A^j(x-y), \rho)/n} \right). \quad (3.12) $$
For $k \ge 0$ and $\xi \in \mathbb{T}^d$, define

$$f_k(\xi) := \sum_{x,y \in \text{supp } \mu} \mu(x)\mu(y) e^{2i\pi \langle A^k(x-y), \xi \rangle}$$

so that $|\widehat{P^t}(\rho)|^2 = \prod_{k=0}^{t-1} f_k(\rho/n)$. For all $k, l \ge 0$, $0 \le f_l \le 1$ and $f_k \circ (A^\top)^l = f_{k+l}$ hence for $k \in [0, d] = \{0, 1, \dots, d\}$,

$$\begin{aligned} |\widehat{P^{t+d}}(\rho)|^2 &= \prod_{l=0}^{k-1} f_l(\rho/n) \prod_{j=k}^{t+d-1} f_j(\rho/n) \\ &\le \prod_{j=0}^{t+d-k-1} f_{j+k}(\rho/n) \\ &\le \prod_{j=0}^{t+d-k-1} f_k((A^\top)^j \rho/n) \\ &\le \prod_{j=0}^{t-1} f_k((A^\top)^j \rho/n). \end{aligned}$$

In particular, if we set

$$f := \min_{k \in [d]} f_k \qquad (3.13)$$

then we have for all $t \ge 0$,

$$|\widehat{P^{t+d}}(\rho)|^2 \le \prod_{j=0}^{t-1} f((A^\top)^j \rho/n). \qquad (3.14)$$

Furthermore, the $f_k$ are continuous and thus so is $f$.

Consider now

$$H := \langle \bigcup_{k \ge 0} A^k (\text{supp } \mu - \text{supp } \mu) \rangle \qquad (3.15)$$

the smallest subgroup of $\mathbb{Z}^d$ that contains $\text{supp } \mu - \text{supp } \mu$ and is invariant by $A$. By Cayley-Hamilton's theorem, we can in fact restrict the powers of $A$ to have exponent less than $d$.

Let $u_1, \dots, u_d$ be generators of $H$, although at this stage one does not require $H$ to have rank $d$. They can be chosen of the form $u_i = A^{k_i}(x_i - y_i)$ with $k_i \le d$ and $x_i, y_i \in \text{supp } \mu$. Then let

$$\alpha := \min \bigcup_i \{\mu(x_i), \mu(y_i)\} > 0$$

and

$$W = \{\xi \in \mathbb{T}^d : \forall h \in H, \langle h, \xi \rangle \in \mathbb{Z}\}.$$

$W$ is a closed set of $\mathbb{T}^d$ and is invariant by $A^\top$ since $H$ is invariant by $A$. If $\xi \notin W$, then one can find $h \in H$ such that $\langle h, \xi \rangle \notin \mathbb{Z}$. However $h$ being a linear combination
with integer coefficients of the $A^{k_i}(x_i - y_i)$, we can directly assume that $h = A^{k_i}(x_i - y_i)$. Then we deduce that

$$ 
\begin{aligned}
f(\xi) &\le 1 - 2\mu(x_i)\mu(y_i) + 2\mu(x_i)\mu(y_i) \cos 2\pi \langle A^{k_i}(x_i - y_i), \xi \rangle \\
&\le 1 - 2\alpha^2 |1 - \cos 2\pi \langle A^{k_i}(x_i - y_i), \xi \rangle| \\
&< 1.
\end{aligned} 
\quad (3.16) $$

By continuity of $f$ we get for all $\eta > 0$

$$ \sup_{\xi: d(\xi, W) \ge \eta} f(\xi) \le \gamma \quad (3.17) $$

for some $\gamma = \gamma(\eta) < 1$. Thus our goal is now to prove that the points on the orbit of $\rho/n$ spend a considerable amount of time away from the “bad set” $W$.

For this, we will use the symbolic representation of the orbits with an explicit description of the set $W$. So far Fourier transforms were expressed in the canonical basis but this choice is not well-suited for expressing the elements of $H$. On the other hand by considering a basis adapted to $H$, $H$ becomes generated by multiple of the basis vectors the set $W$ takes a very simple form. We use the following well known result (see [110, Chap. III Thm. 7.8]) which can be deduced from the Smith normal form of a matrix. We recall a basis of a subgroup $H \subseteq \mathbb{Z}^d$ is a minimal generating family of $H$. The terminology comes from the fact that subgroups of $\mathbb{Z}^d$ are free modules over the ring $\mathbb{Z}$.

**Lemma 3.3.** Let $H$ be a subgroup of $\mathbb{Z}^d$. Then there exists a basis $(u_i)_{i \in [d]}$ of $\mathbb{Z}^d$ and positive integers $a_1, \dots, a_k$, such that $a_i$ divides $a_{i+1}$ for all $i = 1, \dots, k-1$ and $a_1 u_1, \dots, a_k u_k$, forms a basis of $H$. The family $(a_i)_{i=1}^k$ is uniquely determined by the previous conditions.

**Change of basis** By the previous lemma, there exists a basis $(u_i)_{i \in [d]}$ of $\mathbb{Z}^d$ and a family of positive integers $(a_i)_{i \in [d]}$ such that the subgroup $H$ has basis $(a_i u_i)_{i=1}^d$. Let $Q$ be the matrix formed from the vectors $u_i$, expressed in the canonical basis, so that $Qe_i = u_i$ for all $i \in [d]$.

We can now express everything in the basis $(u_i)_{i \in [d]}$: this comes down to replace the map $A$ by $Q^{-1}AQ$ which has the same desired properties as $A$: it is in $GL_d(\mathbb{Z})$ and hyperbolic, while representation $\rho$ has to be pulled-back by $Q$, ie it has to be replaced by $\rho \circ Q$. Notice now that the upper bound lemma (3.4) involves summing over all non-trivial representations, which form a set left invariant by the pull-back operation, so we can simply forget about this pull-back.