Journées ALÉA 2012

Parmi toutes les urnes de Polya équilibrées, on cherche à démasquer celles qui ont une série génératrice algébrique. Pour cette investigation, les méthodes automatiques de Guess'n'Prove ont mis en lumière de nombreux exemples témoins. On peut a posteriori les classifier grâce à des conditions arithmétiques sur les coefficients des règles de l'urne. Cela conduit à des preuves élémentaires d'algébricité et à une description précise des polynômes annulateurs. Il s'agit d'un travail en cours avec A. Bostan, F. Chyzak et Ph. Dumas.

Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.

Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.

Une partie fondamentale en théorie de la concurrence repose sur l'opérateur d'entrelacement de processus. Le principe de base est tel que deux processus s'exécutant en parallèle, noté P ||| Q, peut être obtenu en mélangeant leurs exécutions. L'opérateur d'entrelacement satisfait a.P' ||| b.Q' = a.(P' ||| b.Q') + b.(a.P' ||| Q') où l'opérateur + est un opérateur de branchement. Le but de notre étude est l'obtention de l'arbre résultant de l'entrelacement de grands processus typiques. L'explosion combinatoire entre la taille des processus et son arbre d'entrelacement est connue, mais à travers cet exposé nous allons présenter de manière bien plus fine les mesures et formes moyennes de l'arbre typique d'entrelacements de grands processus. Cette étude nous permettra d'ailleurs de quantifier le taux de partage des branches de cet arbre moyen. Nous terminerons la présentation avec la présentation de deux algorithmes efficaces permettant pour l'un de compter le nombre d'exécutions différentes induites par l'entrelacement des processus et pour l'autre d'en tirer une uniformément au hasard.

Une expression logique représentant une fonction booléenne peut être représentée par un arbre dont les n{\oe}uds internes sont étiquetés par un connecteur et les feuilles par un littéral. En choisissant la manière d'étiqueter (i.e. le système logique), la structure d'arbres (planaire ou non, binaire ou d'arité quelconque, équilibré ou non) ainsi que sa distribution (uniforme suivant la taille, processus de Galton-Watson), on induit une distribution différente sur les fonctions booléennes. Dans cet exposé, je présenterai les résultats principaux, ainsi que les idées clé sous-jacentes, de travaux réalisés en collaboration avec A. Genitrini, B. Gittenberger et V. Kraus. Ces travaux se concentrent sur des distributions uniformes selon la taille, mais explorent différentes structures d'arbres (non-planaires et/ou non-binaires), ainsi que deux systèmes logiques distincts (et/ou et implication). Enfin, je soulèverai des interrogations sur les différentes notions de taille d'un arbre (notamment dans le cas d'arbres non-binaires) et donc sur les différentes notions de complexité d'une fonction booléenne. J'introduirai un nouveau modèle, à l'étude actuellement, fondamentalement différent des autres et dont les premiers résultats laissent envisager un comportement distinct de la distribution induite sur les fonctions booléennes.

Un automate cellulaire (AC) est un réseau régulier de cellules, chacune contenant un état (simplement 0 ou 1 en général). Les contenus de toutes les cellules évoluent de manière synchrone, en fonction des états d'un nombre fini de leurs voisines. Le problème de "classification de la densité" consiste à chercher un AC capable de déterminer si une configuration initiale définie sur un anneau contient une majorité de 0 ou de 1. Nous nous intéressons ici à l'extension de ce problème à un réseau infini. Chaque cellule est initialisée indépendamment à l'état 1 avec probabilité p ou à l'état 0 avec probabilité 1-p, et la question est alors de construire un AC qui converge vers la configuration "tout 0" lorsque p< 1/2, et vers la configuration "tout 1" quand p> 1/2 (synchronisation de toutes les cellules sur l'état majoritaire). On dira qu'un tel AC classifie la densité. Nous montrons que sur la grille Z2, l'AC de Toom (règle majorité sur le voisinage nord-est-centre) classifie la densité. Sur les arbres homogènes de degré supérieur ou égal à 3, nous savons aussi exhiber des AC qui classifient la densité. Sur Z, il existe des AC et des ACP (automates cellulaires probabilistes) candidats, mais la question reste ouverte. Travail en collaboration avec Ana Busic, Nazim Fatès et Jean Mairesse.

Pour m>26, l'asymptotique du vecteur composition d'un arbre m-aire de recherche fait apparaî tre au second ordre une variable aléatoire à valeurs complexes W^DT. Lorsqu'on plonge en temps continu, le processus de branchement multitype obtenu a également un second terme asymptotique en W^CT, une (autre) variable aléatoire à valeurs complexes. Chacune de ces variables aléatoires est solution d'une équation de point fixe en distribution. Dans cet exposé, on rappellera les résultats obtenus par la méthode de contraction puis on se concentrera sur l'existence d'une densité pour W^DT et W^CT et sur leur support, qui s'avère être tout le plan complexe. En outre ces variables admettent des moments exponentiels. Les méthodes utilisées sont de l'analyse fine des transformées de Fourier et la mise en évidence de martingales ``cascades'' de Mandelbrot.

Ce travail en cours étudie une marche particulière en milieu aléatoire. Le milieu est un arbre déterministe constituant un réseau électrique dont les résistances sont aléatoires et suivent des lois gaussiennes inverses pour les sommets internes et des lois gaussiennes inverses réciproques pour les sommets externes. Les paramètres sont choisis de sorte que la résistance équivalente du réseau (au sens des lois d'Ohm-Kirchoff) suive une loi gaussienne inverse réciproque. La marche aléatoire considérée ici est celle que l'on peut naturellement définir sur tout réseau électrique selon le livre de Doyle et Snell Random walks and Electrical networks. Nous nous intéressons notamment à la probabilité qu'une particule, partant de la racine de l'arbre, atteigne une feuille avant de revenir à la racine.

On considère un automate cellulaire simple représentant deux particules de vitesses différentes qui s'annihilent quand elles se rencontrent. En traçant un parallèle entre le comportement de cet automate sur une configuration initiale aléatoire et celui d'une certaine marche aléatoire, l'approximation par un mouvement brownien permet d'obtenir des informations sur son comportement asymptotique. En utilisant cette approche, nous pouvons calculer des temps d'entrée asymptotiques, généralisant un résultat de Kurka et al., et une approximation plus fine permet de donner des bornes polynomiales sur la densité de particules et la vitesse de convergence vers la mesure limite.

Il y a près de 30 ans, Philippe Flajolet, dans un de ses papiers les plus cités, a montré que l'on pouvait concevoir des algorithmes pour estimer extrêmement précisément le nombre d'éléments différents dans un multi-ensemble, en utilisant peu de mémoire auxiliaire, en un seul passage sur les données et avec une simplicité et une élégance extraordinaires. C'est un cas particulier, mais assez important, de ce que l'on appelle "streaming analysis". Mais pour que les algorithmes d'estimation fonctionnent, on a besoin d'une analyse très précise de ses propriétés probabilistes : il faut trouver des paramètres qui sont au coeur de ce type d'algorithmes, et c'est l'analyse qui les fournit. À la suite de ce travail, beaucoup de chercheurs, Philippe lui-même avec autres coauteurs, ont proposé de nouveaux algorithmes et ont étudié leurs performances. Les outils mathématiques (combinatoire, proba, ...) qu'il faut mettre en jeu sont très intéressants et nous trouvons dans ce domaine des défis mathématiques et informatiques très attrayants. Sans doute, le domaine des algorithmes de streaming est l'un des meilleurs exemples d'interaction parfaite entre mathématiques et informatique.

Nous considérons deux processus stochastiques classiques : les urnes d'Ehrenfest, introduites en 1907 pour la théorie cinétique des gaz pour décrire les échanges de chaleur entre deux corps et le modèle d'Engset introduit en 1918 et qui est, avec le modèle d'Erlang, un des tous premiers modèles stochastiques de réseaux de communication. Nous proposons d'étudier le comportement asymptotique de la distribution des temps d'atteinte de ces deux processus lorsque le nombre de particules ou d'utilisateurs croît vers l'infini. En particulier, nous obtenons des résultats sur les temps d'atteinte de frontière. Cette étude repose sur des techniques de martingales et notamment sur une famille de martingales positives qui est l'équivalent pour le processus d'Ehrenfest des martingales exponentielles utilisées pour l'étude des marches aléatoires et du mouvement brownien.

Dans de nombreux contextes, les objets étudiés peuvent être modélisés par des graphes, appelés graphes de terrain : topologie de l'internet, graphes du web, réseaux sociaux, réseaux biologiques, ... La plupart de ces graphes sont dynamiques, c'est-à-dire qu'ils évoluent au fil du temps par l'apparition et la disparition de nœuds et de liens. L'étude de cette dynamique soulève de nombreuses questions importantes. Je m'intéresserai dans cet exposé à un cas particulier : la topologie de l'internet (constituée de routeurs et de liens de communication au niveau IP). On peut capturer une partie de sa dynamique en s'intéressant à ce qu'une machine donnée peut voir de cette topologie, qu'on appelle vue ego-centrée, et en répétant périodiquement la mesure de ces vues ego-centrées. Je présenterai une analyse de la dynamique observée sur de telles mesures. On verra en particulier que ces vues ego-centrées évoluent à un rythme beaucoup plus élevé que ce à quoi on aurait pu s'attendre. On verra également que deux phénomènes jouent un rôle clé dans la dynamique observée : le load-balancing ou équilibrage de charge, et l'évolution du routage. Enfin, je présenterai des pistes pour la modélisation de la topologie de l'internet et sa dynamique. On verra que des approches basées sur des graphes aléatoires permettent de reproduire fidèlement les observations. Ces approches ont le double avantage de permettre d'expliquer les comportements observés, et de permettre, par une étude détaillée de l'impact des différents paramètres, d'espérer quantifier de manière rigoureuse la dynamique réelle de la topologie.

L'objectif de cet exposé est de présenter une nouvelle méthode pour déterminer des lois limites dans des permutations aléatoires (uniformes). La méthode fonctionne pour de nombreuses statisques renormalisées: nombre d'excédences, d'adjacences, de motifs généralisés. Elle se base sur la méthode des moments et formalise l'intuition que les images de deux entiers différents sont "quasi-indépendantes".

L'exposé de Conrado Martínez présente un panorama de la richesse de l'algorithmique probabiliste développée pour le traitement quantitatif de grandes masses de données. Cette algorithmique repose essentiellement sur des observations probabilistes et pour les évolutions les plus récentes, d'algèbre et d'algèbre linéaire. Nous considérons un point de vue différent. Il s'avère que les flux de données peuvent être considérés comme des permutations aléatoires : ainsi, on peut concevoir et analyser ces algorithmes de manière complètement combinatoire, et notamment se baser sur des statistiques bien connues sur les permutations pour en déduire des estimateurs. C'est ce que nous illustrerons principalement au travers de RECORDINALITÉ, un estimateur du nombre d'éléments distincts qui se base sur le nombre de records observés dans une permutation, dont tout bon combinatoricien sait qu'il est de l'ordre de ln(n), où n est le nombre d'éléments de la permutation. Avec cette approche originale, nous espérons intéresser les nombreux combinatoriciens d'exception qui fréquentent les journées Aléa !

Dans un travail récent, Olivier Bernardi et Mireille Bousquet-Mélou ont prouvé que la série génératrice des cartes planaires pondérées par leur polynôme de Tutte (un polynôme bivarié qui généralise le polynôme chromatique) satisfait une équation différentielle algébrique (énorme).
Ce résultat repose sur une approche récursive, et la preuve est extrêmement lourde et technique. Il semble robuste, puisqu'il subsiste lorsqu'on remplace les cartes planaires générales par les triangulations.
On se concentre ici sur une spécialisation à une variable du polynôme de Tutte, qui compte les forêts couvrantes selon le nombre de composantes connexes.
Partant d'une construction de Bouttier, Di Francesco et Guitter (2007), nous établissons, de manière combinatoire, des équations fonctionnelles pour la série étudiée, dont découlent ensuite les équations différentielles cherchées. Cette approche s'applique à des familles variées de cartes..
Les équations fonctionnelles permettent de mener à bien l'étude asymptotique des séries obtenues, et d'analyser la nature des transitions de phase.

Motivés par une modélisation de réseau de distribution de contenus et par un problème d'orientation d'hypergraphes aléatoires, on s'intéresse au calcul de la taille maximale d'un b-matching dans une suite de graphes aléatoires qui convergent localement faiblement vers un arbre de Galton-Watson. On utilise un algorithme de message passing appelé Belief Propagation (BP) à température positive pour approximer la distribution marginale de cette quantité à chaque sommet du graphe. On établit d'une part des propriétés de convergence de l'algorithme utilisé et d'autre part on vérifie que le calcul effectué est asymptotiquement correct. Comme le graphe limite que l'on considère est un arbre de Galton-Watson, on obtient des équations récursives en distribution sur les messages de BP, ce qui conduit à une formule analytique pour la quantité recherchée.

Le modèle fluide stochastique est souvent utilisé dans les réseaux de communication à haut débit.
En réalité, l'information qui circule dans un réseau est toujours discrète, on parle de nombre de tâches à exécuter et non de quantité.
À l'échelle d'une rafale, l'information est supposée arriver selon un flux liquide avec des débits aléatoires.
Plus précisément, le débit d'entrée fluide est supposé être régi par un processus de Markov à espace d'états fini. Lorsque ce liquide dépasse la capacité du serveur, traitant cette information, il est stocké dans un buffer afin d'être servi ultérieurement..
On s'intéresse alors à la distribution de probabilité de la quantité du liquide dans le buffer en régime asymptotique. Les deux cas d'un buffer à capacité infinie et l'autre à capacité finie sont traités et analysés. Les deux méthodes proposées sont à la fois précises et numériquement stables. Un exemple de trafic vidéo MPEG sera modélisé et étudié.

Le fait que le problème de décider si un graphe possède un noyau est NP-complet ne garantit pas qu'il est facile d'obtenir des distributions naturelles produisant des instances difficiles (les algorithmes connus sont de complexité exponentielle). Nous montrerons qu'il existe une connexion entre la complexité de trouver un noyau et les tailles possibles des noyaux. Cependant, la taille des noyaux d'un graphe de G(n,p) varie fortement selon la valeur de p. Nous verrons pourquoi le cas p = c/n fournit les instances les plus difficiles.

Les probabilités libres permettent de modéliser le comportement des matrices aléatoires de grandes tailles, en particulier leurs propriétés spectrales. J'expliquerai les bases de la théorie et de ses applications aux matrices aléatoires, ainsi que les outils combinatoires qui ont été développés à cet effet.

Les constellations sont des cartes planaires dont les faces sont coloriées en noir ou blanc, de telle sorte que : - deux faces adjacentes sont de couleurs opposées - toute face noire a degré p - toute face blanche a un degré multiple de p (p étant un entier fixé ≥ 2). On s'intéresse ici à la « fonction à deux points » : série génératrice des constellations avec deux sommets marqués à distance fixée. Nous montrerons comment la fonction à deux points des constellations est naturellement encodée par une fraction multicontinue et comment on peut utiliser cette correspondance pour obtenir la fonction à deux points grâce à une généralisation des déterminants de Hankel. Travail en commun avec Jérémie Bouttier.

RESUME

La percolation de paramètre p, c'est ce qui reste dans Z² quand on efface chaque arête indépendamment avec probabilité 1-p.
Quand p est proche de un, il y a une composante connexe infinie. Le TASEP, ce sont des voitures qui avancent de façon aléatoire sur une seule voie, sans se doubler et sans se rentrer dedans.
A priori, ça n'a rien à voir.
Le but de cet exposé est de montrer que des estimées sur le TASEP permettent d'obtenir des estimées sur certaines distances dans la composante infinie de percolation, quand p est très proche de un. (Travail avec A.-L. Basdevant et N. Enriquez).

On y mange et on y boit

On y mange et on y boit

On y mange et on y boit

On y mange et on y boit

On y mange et on y boit