Valérie Berthé
Densité de langages rationnels et équidistribution
Nous considérons dans cet exposé la densité de langages rationnels par rapport à des mesures de probabilité invariantes sur des ensembles de mots infinis, ce qui généralise la notion classique de densité étudiée dans le cadre des langages formels et la théorie des automates. La densité d'un langage est définie comme la limite en moyenne (si elle existe) de la probabilité qu'un mot d'une longueur donnée appartienne au langage. La densité d'un langage rationnel peut ainsi être considérée comme la fréquence d'un certain motif (par exemple les mots ayant un nombre pair d'une lettre donnée). Nous établissons l'existence de densités pour tous les langages rationnels et pour toutes les mesures invariantes. Notre approche combine la théorie des semigroupes avec les propriétés ergodiques de produits croisés. Nous en déduisons en particulier des résultats d'équidistribution par rapport à des groupes finis.
Il s'agit d'un travail commun avec H. Goulet-Ouellet, C.-F. Nyberg-Brodda, D. Perrin et K. Petersen.
***
Alice Contat
Universalité des équations catalytiques en combinatoire analytique.
Depuis les travaux pionniers de Tutte sur l’énumération des cartes planaires, l’idée d’introduire une variable dite catalytique pour résoudre des équations impliquant des fonctions génératrices s’est révélée très fructueuse. Nous montrerons que les équations catalytiques positives et non linéaires ont un exposant polynomial universel 5/2 autour de leur singularité.
Basé sur un travail en commun avec Nicolas Curien.
***
Lucas Gerin
Marches aléatoires entropiques : une approche combinatoire
La marche aléatoire (maximale) entropique sur un graphe fini est une chaîne de Markov naturelle introduite par Burda et al. (2009). La construction de ce processus est explicite en fonction du vecteur propre de Perron-Frobenius de la matrice d'adjacence du graphe.
Le but de cet exposé est de proposer une construction analogue sur le graphe infini formé de Z perturbé par des boucles (sans boucle la marche entropique coïncide avec la marche standard). Grâce à une représentation combinatoire explicite des vecteurs propres de Perron-Frobenius on peut décrire assez précisément le comportement des marches.
***
Hélène Guérin
Distribution asymptotique de la marche aléatoire de l’éléphant en régime superdiffusif
Introduite par des physiciens au début des années 2000, la marche aléatoire de l'éléphant évolue sur un réseau et elle a besoin de se remémorer de tous les pas de son passé pour avancer. Son comportement dépend ainsi d'un paramètre de mémoire. Trois régimes de comportement asymptotique ont été identifiés : diffusif, critique et superdiffusif.
Plusieurs variantes de cette marche ont été étudiées, mais dans cet exposé, nous nous concentrerons sur la marche classique de l'éléphant. En utilisant une connexion avec les urnes de Polya, une équation de point fixe pour la loi asymptotique dans le régime superdiffusif est mise en évidence. Nous en déduirons des informations sur cette loi, comme l'existence d'une densité. Nous nous concentrerons ensuite sur les propriétés de cette fonction de densité pour estimer les queues de la distribution limite.
Cet exposé est basé sur des travaux récents menés conjointement avec Lucile Laulin (Université de Paris Nanterre), Kilian Raschel (CNRS, Université d'Angers), et Thomas Simon (Université de Lille).
***
Benjamin Hellouin
Phénomène de randomisation dans des pavages algébriques
On s'intéresse aux colorations d'une grille régulière par un ensemble fini de nombres qui satisfont des contraintes locales prenant la forme d'une équation linéaire sur Z/nZ. L'exemple connu est celui du pavage de Ledrappier.
On tire une ligne de ce pavage au hasard de manière i.i.d non uniforme, et on remplit le demi-plan supérieur de la seule manière possible (c'est un automate cellulaire linéaire). On observe en s'éloignant de la ligne initiale une convergence vers la mesure uniforme dans un sens plus ou moins fort en fonction de la direction choisie pour la ligne initiale.
Je montrerai des exemples expérimentaux de ce comportement et quelques résultats formels, qui reposent tous sur la forte structure autosimilaire du système qui vient de ses propriétés algébriques. Je parlerai aussi de questions laissées en suspens sur l'existence de tels comportements dans des systèmes moins algébriques, et du lien avec d'autres questions ouvertes sur les automates cellulaires surjectifs.
C'est un exposé issu de travaux avec Ville Salo et Guillaume Theyssier.
***
Lucile Laulin
La limite diffusive des marches aléatoires renforcées amnésiques
Une marche aléatoire renforcée par ses pas est une marche aléatoire qui, à chaque instant, répète un de ses pas passés choisis uniformément ou fait un nouveau pas.
Dans cet exposé, on présentera le modèle uniforme puis une version modifiée où la mémoire dépend du passé de façon « amnésique ». On montre que dans un certain régime et sous des hypothèses raisonnables de mémoire, on trouve toujours un résultat de type principe de Donsker où la limite est la somme de deux processus gaussiens dépendants et explicites.
(Travail en collaboration avec Marco Bertenghi)
***
Sébastien Martineau
Domination stochastique de relèvements et applications en percolation
Pensez à un tableau, formé de cases arrangées en colonnes. Pour chaque colonne indépendamment, avec probabilité p, on pose une pierre sous cette colonne. C'est alors à Alice de jouer : en pleine connaissance de la configuration des pierres et peut-être en utilisant de l'aléa supplémentaire, elle dispose chaque pierre dans une case de son choix de la colonne attitrée. C'est ensuite à Bob de jouer. Il n'a pas le droit d'enlever ni de déplacer les pierres d'Alice. Sa seule capacité est d'ajouter des pierres, possiblement en utilisant de l'aléa supplémentaire. Est-il toujours possible pour Bob de jouer de telle sorte que, dans le tableau final, les cases soient remplies indépendamment les unes des autres et chacune avec probabilité p ?
On verra qu'étudier cette question, qui admet diverses variantes intéressantes, permet de revisiter le résultat suivant de théorie de la percolation : si un graphe est obtenu comme quotient d'un autre graphe (par exemple Z²×Z/nZ par rapport à Z^3), alors le point critique du graphe quotient est supérieur ou égal à celui du graphe de départ.
Il s'agit d'un travail en collaboration avec Rémy Poudevigne--Auboiron et Paul Rax.
***
Samuel Petite
Sous-shifts au langage stable
Les sous-shifts au langage stable forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d’entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité linéaire. Ils sont génériques parmi la famille des sous-shifts. Nous présentons dans cet exposé quelques unes de leurs propriétés, notamment celles concernant les automates cellulaires les préservant et leurs mesures invariantes.
***
Juliette Schabanel
3-permutations et triangle solitaire
L’énumération des permutations de dimension 3 évitant certain motifs par Nicolas Bonichon et Pierre-Jean Morel a donné lieu à de nombreuses conjecture bijectives. Dans cet exposé, on construit une bijection explicite pour l’une de ses classes, la reliant aux bases du triangles, des ensembles de points entiers particuliers issus de la théorie des pavages. Cette bijection permet ensuite de transférer certains outils d’un objet à l’autre et notamment de tirer un système dynamique, le solitaire, des bases aux permutations.
***
Paul Thévenin
Limites d'arbres à descentes
Les arbres à descentes sont une interpolation, dépendant d'un paramètre, entre deux célèbres modèles d'arbres aléatoires : les arbres uniformes aléatoires uniformes, et les arbres aléatoires récursifs, utilisés en biologie et en informatique. Notre but est d'étudier la limite d'arbres à descentes de grande taille, d'un point de vue local (à quoi ressemble un voisinage de la racine ?) et global. En particulier, dans un certain régime, la limite de ces arbres est un dendron aléatoire, structure introduite récemment par Elek et Tardos. Nos méthodes sont un mélange de considérations probabilistes, d'étude de permutations aléatoires et de combinatoire anaytique.
Il s'agit d'un travail en commun avec Victor Dubach (IECL, Nancy) et Stephan Wagner (TU Graz).
***
Brigitte Vallée
Poids de Shannon pour les sources dynamiques
Une source (probabiliste) est définie comme l'ensemble des mots infinis (sur un alphabet dénombrable) muni d'une probabilité mu. Nous étudions ses poids de Shannon: alors que l'entropie classique de Shannon est la quantité d'information moyenne apportée par un préfixe du mot émis, la suite des poids de Shannon décrit la quantité moyenne d'information apportée par le préfixe émis de longueur n. Une source d'entropie de Shannon nulle possède donc des poids de Shannon en o(n).
Nous considérons le modèle des sources dynamiques, où le mot émis est produit par la trajectoire d'un système dynamique de l'intervalle unité, muni d'une probabilité mu. De telles sources à entropie nulle conduisent à des systèmes dynamiques qui possèdent des points fixes indifférents, et nous construisons explicitement des sources binaires (sur l'alphabet {0,1}) qui ont un poids de Shannon avec un comportement prescrit.
Nos méthodes sont fondées sur la combinatoire analytique et les séries génératrices, et utilisent des outils issus des systèmes dynamiques, comme les opérateurs de transfert.
C'est un travail commun avec Ali Akhavi (LIPN, Paris-Nord), Eda Cesaratto (Buenos-Aires), Frédéric Paccaut (LAMFA, Amiens), Pablo Rotondo (IGM, Paris-Est).
