Mixing times of Markov chains: acceleration and cutoff in random environment
Temps de mélange de chaînes de Markov : accélération et cutoff en environnement aléatoire
Résumé
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.
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é 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.
Origine : Fichiers produits par l'(les) auteur(s)
