Journées ALÉA 2011

Soit S un sous-ensemble fini de Z^2. On s'intéresse au comptage des chemins du plan à pas dans S, issus de l'origine et confinés au premier quadrant. En particulier, on voudrait connaître la nature de la série génératrice associée : est-elle rationnelle, algébrique, différentiellement finie ? On présentera deux types d'approche pour résoudre ce problème, l'une basée sur la manipulation de séries formelles (mbm), l'autre utilisant des méthodes plus analytiques (K. Raschel).

Dans cet exposé, nous aborderons des problèmes d'analyses d'algorithmes manipulant des langages réguliers en utilisant deux types de représentation par automates. Dans un premier temps, nous parlerons de la représentation de ces langages par des automates déterministes et accessibles. Nous présenterons un algorithme de génération aléatoire de ces automates, l'analyse en moyenne de l'algorithme de minimisation dû à Moore et des résultats sur la compléxité des opérations rationnelles dans le cas de langages finis. Dans un second temps, nous discuterons la complexité de la construction d'automates non-déterministes particuliers, les automates de Glushkov, Ces automates sont en correspondance naturelle avec les expressions rationnelles qui permettent de représenter les langages réguliers.

Nous utilisons et étendons des idées qui proviennent de la théorie des espèces de structures. Nous en tirons d'une part des algorithmes de complexité quasi-optimale pour calculer des suites d'énumération (ce qui donne un prétraitement quasi-optimal à la génération aléatoire par la méthode récursive), d'autre part des oracles numériques pour les générateurs aléatoires dans le modèle de Boltzmann. Il s'agit d'un travail en commun avec Carine Pivoteau et Michèle Soria.

On se donne S, un ensemble fini de points inclus dans un certain domaine du plan D. Ces points sont vus comme un ensemble d'étapes possibles pour un voyageur. Le voyageur partant d'un point s et allant à un point t, doit s'arrêter "au premier point" de l'ensemble t union S, situé "dans la direction de t". Nous examinons alors la distance parcourue par le voyageur, et la comparons à la distance Euclidienne entre s et t, lorsque l'ensemble S est tiré aléatoirement (et à une taille tendant vers l'infini), et pour diverses notions de "premiers points" et de "dans la direction de t".

Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multi-objective optimization or data processing, and the k-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the number of k-dominant skylines is asymptotically zero for large samples when 0 < k < d under two reasonable (continuous) probability assumptions of the input points, d being the (finite) dimensionality. This suggests that practical use of such skylines under similar data conditions has to be more cautious. On the other hand, a sharp threshold phenomenon is established for the (d-1)-dominant skylines when the dimensionality is allowed to grow with n. We also derive an asymptotic linearity property for the k-dominant skylines under a categorical model. These explain to some extent the difference between theoretical and empirical estimates. (Joint work with W.-M. Chen and T.-H. Tsai)

Les permutations alternantes sont celles où les descentes sont exactement les entiers impairs. En fait, si on définit une "classe de descente" comme étant les permutations avec un ensemble de descente donnée, les permutations alternantes forme la plus grosse classe de descente. En se basant sur cette idée, les permutations alternantes ont été généralisées dans d'autres groupes, notamment les groupes de permutations signées. Les objets qui apparaissent ont été appelés serpents par Vladimir Arnol'd. Le but de ce travail est de donner une définition combinatoire explicite des serpents dans les groupe de Coxeter (qui généralisent les permutations signées).

Le modèle de Boltzmann est une technique séduisante pour la génération aléatoires d'objets combinatoires, mais il a potentiellement le défaut de reposer sur un "oracle" chargé d'évaluer diverses séries génératrices en un même point. Une question naturelle est celle de l'influence, sur la qualité du résultat, de la précision numérique de l'oracle. On apportera à cette question des réponses plus ou moins satisfaisantes et intriguantes.

Nous montrerons que certaines questions de combinatoire énumérative peuvent être traitées de façon systématique en utilisant une approche de type " mathématiques expérimentales " guidée par des algorithmes modernes du calcul formel. Nous décrirons la découverte et la preuve assistées par ordinateur de l'algébricité de la série génératrice des chemins confinés au quart de plan et utilisant des pas de longueur un vers l’est, l'ouest, le sud-ouest, ou le nord-est.

Je montrerai qu'il existe un lien surprenant entre les deux problèmes combinatoires suivants: (1) compter des cartes planaires avec un bord de longueur fixée et (2) compter des cartes planaires avec deux points marqués à distance prescrite. La solution à ces deux problèmes est codée dans le développement d'une même quantité de deux manières: en série pour (1) et en fractions continues pour (2). Je montrerai alors comment utiliser une solution connue de (1) pour résoudre (2) et dériver ainsi certaines formules exactes pour la fonction à deux points des cartes planaires.

On dispose d'une machine comportant m composantes, initialement toutes neuves. A chaque unité de temps, l'une des m composantes, choisie au hasard, est rem- placée par une composantes neuve avec probabilité p. Au bout de n unités de temps, quel est le comportement de L_n l'âge de la plus vieille composante ? Quelle aura été la durée, H_n, de vie maximale d'une composante ? Ce problème est lié au problème de Pat Moran en biologie des populations. Dans ce travail on s'intéresse au cas où m=1 et p\in]0,1[. Grace à des outils d'analyse complexe (études des singularites de la série génératrice associée à H_n) on obtient des expressions explicites de l'espérance et de la variance de H_n. Ensuite on obtient la loi limite de H_n: on montre l'existence d'une suite déterministe explicite beta_n d'ordre \ln(n)/-\ln(1-p) telle que le processus H_n-beta_n converge en loi vers une loi double exponentielle.

Hwang a montré un théorème central limite pour les Λ-partitions où Λ est une suite croissante tendant vers l'infini qui satisfait certaines conditions. Une de ces conditions est que la série de Dirichlet associée possède un unique pôle d'ordre 1 à l'abscisse de convergence. Dans cet exposé nous montrons que cette condition peut être relâchée et donnons des exemples provenant de l'analyse des entiers ayant des chiffres manquants dans leur représentation en base b.

At the last ANALCO 2011, a talk was presented by C. Martinez (in collaboration with G. Louchard and H. Prodinger) about the mean analysis of the Swedish leader election protocol. The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one player remaining, the protocol stops and the player is declared the leader. Otherwise, all remaining players flip a biased coin, with probability q the player survives to the next round, with probability p = 1-q the player loses (is killed) and plays no further.. unless all players lose in a given round (null round) , so all them play again. In the classical leader election protocol, any number of null rounds may take place, and with probability 1 some player will ultimately be elected. In the Swedish leader election protocol there is a maximum number of consecutive null rounds, and if the threshold is attained the protocol fails without declaring a leader. The analysis was based on an analytic treatment of some recurrences. In the present talk, we present a more probabilistic analysis, based on an urn model. We obtain asymptotic distributions and the first two moments.

Nous nous intéressons à l'énumération asymptotique de lambda-termes de taille donnée, lorsque la hauteur unaire (nombre d'abstractions imbriquées) est bornée. Notre approche relève de la combinatoire analytique; la fonction génératrice s'exprime en termes de racines carrées imbriquées, et la singularité dominante se révèle avoir un comportement surprenant. L'analyse asymptotique du nombre de tels lambda-termes met en évidence le rôle de la borne sur la hauteur unaire. Nous nous intéressons également à la génération aléatoire de lambda-termes, et mettons en évidence les difficultés rencontrées par la génération de Boltzmann sur ces structures.

Les chaînes de Markov à mémoire de longueur variable (en anglais VLMC) constituent une classe de sources probabilistes. Elles fournissent notamment des exemples "concrets" de sources intermittentes. Il sera question des propriétés de mélange, de l'analyse du trie et de celle du trie des suffixes dans un cas stationnaire simple où l'arbre des contextes est un peigne infini.

Je considère une classe d'urnes de Polya à 2 couleurs, équilibrées et additives dont la fonction génératrice est algébrique. Par des méthodes de combinatoire analytique, et notamment une méthode de col faisant intervenir des cols "coalescents", on obtient des résultats sur la distribution asymptotique de l'urne, avec loi normale ainsi que loi locale limite, et grandes déviations, propriétés jusqu'alors inaccessibles par les méthodes classiques probabilistes. Ce travail poursuit l'étude des urnes de Polya du point de vue de la combinatoire analytique, travail amorcé par Flajolet-Dumas-Puyhaubert en 2006.

Les fonctions génératrices des probabilités stationnaires pour les files d'attente multiserveur avec ressaies sont holonomiques. Pour un ou deux serveurs, il s'agit des fonctions hypergéométriques bien connues, mais pour plusieurs serveurs elles appartiennent a une classe encore peu étudiée des fonctions hypergéométriques de type Okubo, ayant une singularité irrégulière en 0. Pour plusieurs serveurs, l' identification de l'unique fonction analytique autour de cette singularité semble être un problème ouvert.

La distribution du degré de la topologie d'internet est considérée comme une de ses principales propriétés. Néanmoins, on ne la connaît qu'à travers une procédure de mesure qui donne une estimation biaisée. En première approximation, cette mesure peut être modélisée par un arbre de parcours en largeur (ou BFS, pour Breadth First Search). On explore notre capacité à déduire le type de la distribution du degré (Poisson ou power-law) à partir de connaissances limitées. On construit des procédures qui estiment la distribution du degré d'un graphe à partir de son BFS et on montre expérimentalement (sur des modèles et des données réelles) que cette approche réussit à distinguer le type de distribution entre Poisson et power-law.

0n peut se demander quelles mesures peuvent être obtenues comme valeurs d'adhérence de la suite des itérés d'une mesure par un automate cellulaire. Un résultat surprenant est que pour chaque mesures calculables, et seulement celles-ci, il existe un automate cellulaire tel que la suite des itérés par une mesure de Bernoulli, et plus généralement une mesure ergodique de support total, converge vers la mesure initialement choisi. On peut même construire un automate cellulaire "universel" dans le sens que suivant la mesure initiale choisie, les valeurs d'adhérences de la suite des itérés par l'automate de la mesure initiale pourra être n'importe quel ensemble de mesures atteignable par un automate cellulaire.

Dans cet exposé, on établie une inégalité de concentration qui permet de majorer P(g(X₁,...,X_n)-Eg(X₁,...,X_n)), où X₁,...,X_n est une famille des variables aléatoires négativement associées. On applique enfin, le résultat à un processus d'exclusion symétrique possédant une distribution initiale 'Strong Rayleigh'.