Soutenance de thèse de MOUMENI Nordine
Titre de thèse
Marches aléatoires sur des suites de graphes monotones
Random walks on monotonous graph sequences
Résumé de la thèse
Dans cette thèse, nous étudions la fusion d'une chaîne de Markov inhomogène en temps sur un espace discret et en temps discret. La fusion désigne la capacité de la chaîne à oublier sa loi initiale. Après un chapitre introductif où nous présentons les bases et le vocabulaire nécessaires pour comprendre nos résultats sur la fusion, nous consacrons un second chapitre à une condition suffisante pour établir cette fusion. Nous faisons l'hypothèse de conditions assurant l'irréductibilité et l'apériodicité de la chaîne inhomogène en temps. Nous supposons également l'existence d'une probabilité initiale propre, donnant une suite de lois tendue. Nous prouvons alors la fusion de la chaîne. Énonçons notre résultat : considérons ((K_t)_{t geq 1}), une suite d'opérateurs de transition de Markov sur un même ensemble discret (V). Nous notons (mu_t^x) la loi au temps (t), en partant de (x) et induite par la suite ((K_t)_{t geq 1}). Nous utilisons (d_{TV}) pour désigner la distance en variation totale. Soit (rho) une mesure de probabilité propre sur (V). Écrivons ((rho_t)_{t geq 0}) la suite des lois induites par la suite ((K_t)_{t geq 1}) de loi initiale (rho). Si la suite ((rho_t)_{t geq 0}) est tendue, alors :
[
forall (x,y)in V, quad lim_{t to +infty} d_{TV}(mu_t^x, mu_t^y) = 0,.
]
Ce résultat est obtenu par l'intermédiaire d'un outil original : les ensembles accompagnants. Cet objet aléatoire est dérivé des *evolving sets* de B. Morris et Y. Peres. Il nous permet également de fournir un résultat qui s'inscrit dans le cadre des *ratio theorems*, non plus sous l'hypothèse de tension, mais sous l'hypothèse de l'existence de (A), un sous-ensemble fini de (V) tel que la limite inférieure de la suite ((rho_t(A))_{t geq 0}) soit strictement positive. En parallèle, dans ce même chapitre, nous nous intéressons à la convergence des lois lorsque les opérateurs ou les mesures invariantes convergent en tout point de (V). ~
Dans un second chapitre, nous fournissons des estimations quantitatives sur la fusion de chaînes de Markov inhomogènes en temps, sous réserve que les mesures invariantes puissent être ordonnées de manière croissante. Les chaînes de Markov issues des réseaux électriques nous donnent une classe d'exemples où les mesures invariantes sont explicites. Notre approche consiste à adapter les inégalités fonctionnelles classiques : Poincaré, Nash et hypercontractivité. Dans les bornes obtenues, nous trouvons un terme additionnel en plus des termes classiques. Celui-ci prend la forme d'une fonction des masses totales. Donnons le premier résultat : il provient de l'utilisation du trou spectral et de l'inégalité de Poincaré. Fixons ((K_t)_{t geq 1}), une suite d'opérateurs de transition Markoviens sur un même ensemble discret (V). Notons ((pi_t)_{t geq 1}) une suite de leurs mesures invariantes, supposées finies et croissantes en tout point de (V). La mesure (pi_t), étant finie, est proportionnelle à une mesure de probabilité, que nous noterons (Tilde{pi}_t). Pour chaque (t geq 1), notons (gamma_t) la constante de Poincaré de l'opérateur (K_t^*K_t), où (K_t^*) est l'adjoint de (K_t) dans l'espace de Hilbert (ell^2(pi_t)).
Nous avons établi :
[
forall (x,y)in V,,quad d_{TV}(mu_t^x, mu_t^y) le frac{1}{2} sqrt{frac{pi_t(V)}{pi_1(V)}} left(frac{1}{sqrt{Tilde{pi}_1(x)}} + frac{1}{sqrt{Tilde{pi}_1(y)}}right) prod_{s=1}^t sqrt{1 - gamma_s}.
]
Thesis resume
In this thesis, we study the merging property of a discrete-time Markov chain on a countable space. Merging refers to the chain's ability to forget its initial distribution. After an introductory chapter where we present the basic concepts and necessary vocabulary to understand our results on merging, we dedicate the second chapter to a sufficient condition for establishing this merging. We assume conditions ensuring irreducibly, aperiodicity, and the tightness of a sequence of laws with a proper initial probability measure. We then prove that the chain merges. Let ((K_t)_{t geq 1}) be a sequence of Markov transition operators on the same discrete set (V). Let (mu_t^x) denote the law at time (t) starting from (x), driven by the sequence ((K_t)_{t geq 1}), and let (d_{TV}) be the classical total variation distance. Let (rho) be a proper probability measure on (V). Denote by ((rho_t)_{t geq 0}) the sequence of laws driven by the sequence ((K_t)_{t geq 1}) with the initial law (rho). If the sequence ((rho_t)_{t geq 0}) is tight, then:
[
forall (x,y) in V, quad lim_{t to +infty} d_{TV}(mu_t^x, mu_t^y) = 0,.
]
This result is proved using an original tool: the accompanying sets process. This random object is derived from the evolving sets introduced by B. Morris and Y. Peres. It also allows us to provide a result within the framework of ratio theorems, but under the hypothesis that there exists a finite subset (A) of (V) such that the limit inferior of the sequence ((rho_t(A))_{t geq 0}) is strictly positive, instead of the usual tightness assumption. Additionally, in this same chapter, we study the convergence of the laws when the operators or invariant measures converge pointwise. ~
In the second chapter, we provide quantitative estimates on the merging of time-inhomogeneous Markov chains, assuming that the invariant measures can be ordered in an increasing manner. Markov chains arising from electrical networks provide a class of examples where the invariant measures are explicit. Our approach involves adapting classical functional inequalities: Poincaré, Nash, and hypercontractivity. In the proven bounds, alongside the classical terms, we find an additional term that takes the form of a function of the total masses. Let us illustrate our bounds using the spectral gap and the Poincaré inequality. Let ((K_t)_{t geq 1}) be a sequence of Markov transition operators on the same discrete set (V). Let ((pi_t)_{t geq 1}) be the sequence of their invariant measures, assumed to be finite. We denote by (Tilde{pi}_t) the probability measure derived from the finite measure (pi_t). We assume that for all (x in V), the sequence ((pi_t(x))_{t geq 1}) is non-decreasing. For each (t geq 1), let (gamma_t) be the Poincaré constant of the operator (K_t^*K_t), where (K_t^*) is the adjoint of (K_t) in the Hilbert space (ell^2(pi_t)). Then, we obtain:
[
forall (x,y) in V, quad d_{TV}(mu_t^x, mu_t^y) le frac{1}{2} sqrt{frac{pi_t(V)}{pi_1(V)}} left(frac{1}{sqrt{Tilde{pi}_1(x)}} + frac{1}{sqrt{Tilde{pi}_1(y)}}right) prod_{s=1}^t sqrt{1 - gamma_s}.
]