Journées ALÉA 2010
Pensez à vérifier la page d'accueil pour les dernières nouvelles, la photo de groupe et télécharger l'archive de toute la semaine.
Planning
Les Journées ALÉA 2010 se dérouleront du lundi 22 mars au vendredi 26 mars 2010. Une version PDF du planning est disponible.
Les résumés sont disponibles ici.
| Lundi | Mardi | Mercredi | Jeudi | Vendredi | ||
|---|---|---|---|---|---|---|
09:00 | Philippe Flajolet | Kirone Mallick [transparents] [résumé] Solutions exactes pour le processus d'exclusion asymétrique Le processus d'exclusion asymétrique (ASEP) est un modèle de particules en interaction de coeur dur qui évoluent selon une dynamique stochastique sur un réseau unidimensionnel. Ce système, considéré comme un paradigme de physique statistique hors d'équilibre, représente, de manière minimale, les phénomènes de transport de particules, d'énergie ou de charges dans un conducteur en contact avec deux réservoirs placés à des potentiels différents. Ce modèle est résoluble exactement à l'aide de techniques variées dont quelques unes seront décrites dans ce cours. Nous expliquerons comment la mesure stationnaire du modèle peut-être codée à l'aide d'algèbres quadratiques, ce qui permet de calculer les propriétés aux grandes échelles du système. Nous montrerons aussi comment analyser selon les mêmes techniques des généralisations naturelles de ce processus. Enfin, nous verrons que les propriétés spectrales d'ASEP sont accessibles par l'Ansatz de Bethe, méthode fondamentale en théorie des systèmes intégrables, dont nous ferons une présentation élémentaire. | Kirone Mallick [transparents] [résumé] Solutions exactes pour le processus d'exclusion asymétrique Le processus d'exclusion asymétrique (ASEP) est un modèle de particules en interaction de coeur dur qui évoluent selon une dynamique stochastique sur un réseau unidimensionnel. Ce système, considéré comme un paradigme de physique statistique hors d'équilibre, représente, de manière minimale, les phénomènes de transport de particules, d'énergie ou de charges dans un conducteur en contact avec deux réservoirs placés à des potentiels différents. Ce modèle est résoluble exactement à l'aide de techniques variées dont quelques unes seront décrites dans ce cours. Nous expliquerons comment la mesure stationnaire du modèle peut-être codée à l'aide d'algèbres quadratiques, ce qui permet de calculer les propriétés aux grandes échelles du système. Nous montrerons aussi comment analyser selon les mêmes techniques des généralisations naturelles de ce processus. Enfin, nous verrons que les propriétés spectrales d'ASEP sont accessibles par l'Ansatz de Bethe, méthode fondamentale en théorie des systèmes intégrables, dont nous ferons une présentation élémentaire. | Brigitte Vallée [transparents] [résumé] Théorie de l'information : modèles, algorithmes, analyse Tout étudiant d'un cours d'algorithmique de base apprend que la complexité moyenne de l'algorithme QuickSort est en O(n logn), celle de QuickSelect est en O(n) et celle de RadixSort est en O(n logn). De tels énoncés ont le mérite d'être simples, mais leur simplicité est trompeuse, car ils sont fondés sur des hypothèses spécifiques à chaque algorithme: pour les deux premiers algorithmes, le coût unitaire est la comparaison entre clés, tandis que, pour le troisième, le coût unitaire est la comparaison entre symboles. Ces études souffrent donc de deux inconvénients majeurs: il n'est pas possible de comparer réellement ces algorithmes entre eux, car les mesures de coût sont différentes. Ensuite, la mesure de coût adoptée pour analyser QuickSort ou QuickSelect est peu réaliste, dès que les clés ont une structure complexe, ce qui est le cas dans le contexte des bases de données ou de la langue naturelle, par exemple. Pour effectuer une analyse réaliste, il faut donc d'abord travailler en théorie de l'information pour définir un cadre adapté. En théorie de l'information, une source est un mécanisme aléatoire qui produit des symboles d'un alphabet donné. On construit ici un modèle de source très général, qui prenne en compte la possibilité de corrélations importantes entre symboles émis. Les clés considérées par l'algorithme sont alors des mots produits (indépendamment) par la même source. Il faut ensuite considérer un coût unitaire qui soit le même pour tous les algorithmes: c'est la comparaison entre symboles, et le coût de l'algorithme est donc le nombre total de comparaisons effectuées entre symboles. Nous revisitons ainsi, dans un tel modèle, à la fois unifié et réaliste, l'analyse probabiliste de trois principaux algorithmes: QuickSort, QuickSelect, et les algorithmes de dictionnaire fondés sur la structure de trie. Ce mini-cours est fondé sur des travaux communs avec Julien Clément, James Fill, et Philippe Flajolet. | 09:00 | |
09:15 | Marc Noy [transparents] [résumé] Lois limites pour les cartes planaires Nous proposons de discuter de différents paramètres des cartes planaire aléatoires. Certains conduisent à des lois limites gaussiennes, comme par exemple le nombre de sommets, le nombre de blocs ou le nombre de boucles. Nous présentons aussi quelques paramètres extrémaux, comme la taille du plus grand bloc ou le degré maximum. Nous nous concentrons ensuite sur la distribution du degré du sommet (de la face) racine, et étudions la distribution limite discrète. Nous analysons les queues de ces distributions et tentons d'expliquer certains phénomènes d'universalité. Eventuellement, nous discuterons brièvement des cartes et de graphes sur les surfaces, en mettant en évidence les différences et les similarités avec les cartes planaires. | Philippe Flajolet [transparents] [résumé] Machines et Nombres de Buffon Une expérience bien connue due à Buffon produit un procédé probabiliste continu, une sorte de "calculateur analogique", dont la probabilité de succès met en jeu le fameux nombre Pi. Est-il possible de composer des procédés probabilistes simples et discrets, fondés uniquement sur des tirages à pile ou face, pour atteindre le même résultat? Une des motivations est la réalisation de simulateurs de Boltzmann pour de grands modèles combinatoires discrets. Nous examinerons des constructions qui permettent d’atteindre des constantes telles que π, e−1, log2, √3, cos(1/4), ζ(5) et réaliser une grande variété de fonctions (exponentielles, trigonométriques, algébriques, logarithmiques, hypergéométriques, etc). On en déduira notamment des générateurs purement discrets de la loi de Poisson et de la loi logarithmique. L’un des générateurs associés au nombre Pi nécessite moins de sept tirages de pièces en moyenne et l’expérience peut être facilement réalisée par un humain. (Ce travail est joint avec Maryse Pelletier et Michèle Soria, LIP6, Paris). | 09:15 | |||
09:30 | 09:30 | |||||
09:45 | 09:45 | |||||
10:00 | 10:00 | |||||
10:15 | 10:15 | |||||
10:30 | 10:30 | |||||
10:45 | Florent Le Gac [transparents] [résumé] Sur les matrices à signe alternant Les matrices à signe alternant (ASMs) sont des objets largement étudiés en physique statistique. Ils se trouvent en bijection avec les configurations de boucles compactes, sur lesquelles porte la conjecture de Razumov-Stroganov. Nous présentons une formule de comptage des ASMs en fonction de leur taille et de leur nombre d’entrées négatives. Cette formulation nous permet de trouver l’asymptotique pour les ASMs ayant un nombre fixé d’entrées négatives ainsi que des formules exactes lorsque le nombre d’entrées négatives reste petit. | Lucas Mercier [transparents] [résumé] Graphes inhomogènes : comportement au seuil critique Dans le modèle classique de graphe aléatoire d’Erdös-Rényi a lieu une transition de phase au voisinage de 1/n. Söderberg a montré qu’un phénomène similaire avait lieu dans un modèle de graphe inhomogène, généralisation du modèle d’Erdös-Rényi. Dans le modèle classique, Aldous a montré que l’on pouvait relier la taille des plus grandes composantes connexes à la longueur des excursions browniennes. Le but de cet exposé est de généraliser ces résultats au voisinage du seuil critique dans le cas des graphes inhomogènes. | Conrado Martinez [transparents] [résumé] Rank Selection on Multidimensional Data Structures Suppose we have a set of K-dimensional records stored in a general purpose spatial index like a K-d tree. The index efficiently supports insertions, ordinary exact searches, orthogonal range searches, nearest neighbor searches, etc. Here we consider whether we can also efficiently support search by rank, that is, to locate the i-th smallest element along the j-th coordinate. We answer this question in the affirmative by developing a simple algorithm with expected cost O(nα(1/K) logn), where n is the size of the K-d tree and α(1/K)<1 for any K≥ 2. The only requirement to support the search by rank is that each node in the K-d tree stores the size of the subtree rooted at that node (or some equivalent information). This is not too space demanding. Furthermore, it can be used to randomize the update algorithms to provide guarantees on the expected performance of the various operations on K-d trees. Although selection in multidimensional data can be solved more efficiently than with our algorithm, those solutions will rely on ad-hoc data structures or superlinear space. Our solution adds to an existing data structure (K-d trees) the capability of search by rank with very little overhead. The simplicity of the algorithm makes it easy to implement, practical and very flexible; however, its correctness and efficiency are far from self-evident. Furthermore, it can be easily adapted to other spatial indexes as well.(Joint work with A. Duch and R. M. Jimenez.) | Axel Bacher [transparents] [résumé] Une famille de chemins auto-évitants faisant intervenir le produit de Hadamard
des séries Un chemin fini sur le réseau carré est auto-évitant si il ne passe pas deux fois par le même sommet. Je définis une famille de chemins auto-évitants, une extension naturelle de la famille des chemins dits " faiblement dirigés ", la plus nombreuse que l’on sache énumérer jusqu’à présent. La série énumérant ces chemins est caractérisée par une équation faisant intervenir le produit de Hadamard. | 10:45 | |
11:00 | Yann Ponty [transparents] [résumé] Combinatoire et repliement algorithmique des ARN
| 11:00 | ||||
11:15 | Émilie Coupechoux [transparents] [résumé] Apparition de la composante géante pour un hypergraphe aléatoire Dans les graphes d’Erdös-Renyi dilués, la taille de la plus grande composante subit une transition de phase lorsque le degré moyen dépasse strictement 1. Nous généralisons ce résultat au cas d’hypergraphes aléatoires, c’est-à-dire de graphes pour lesquels les (hyper)arêtes peuvent contenir plus de deux sommets : le poids d’une arête est alors le nombre de sommets qu’elle contient. Par des méthodes d’approximation de chaînes de Markov, nous déterminons, en fonction de la distribution des degrés des sommets et des poids des arêtes, si la plus grande composante contient une fraction des sommets et dans ce cas calculons sa taille. | Cédric Saule [transparents] [résumé] Enumération de structures ARN avec pseudonœuds En 2004, Anne Condon et ses co-auteurs dressèrent une classification des algorithmes exactes de prédiction de structures ARN ab initio avec pseudonœuds basée sur le degré de généralité des structures qu’ils peuvent prédire. Ils montrèrent que ces classes sont en relation d’inclusion. Nous proposons d’évaluer le compromis entre complexité en temps et le nombre de structures prédictibles par chaqu’un de ces algorithmes. En particulier nous montrerons qu’il existe une bijection entre les structures de la classe de Lyngso et Pedersen à n arcs et les cartes planaires enracinées sans isthmes à un ou deux sommets et n arêtes. Nous montrerons aussi que ces structures peuvent être codées par des langages algébriques non ambigüs. Nous en déduisons la série génératrice et le comportement asymptotique du nombre de structures. Nous ajouterons également deux classes de structures à cette classification. | Mathieu Roux [transparents] [résumé] Comportement moyen d’un trie construit sur une source sans mémoire Une source sur un alphabet Σ est déterminée par la famille (pw) des probabilités fondamentales, où pw est la probabilité qu’un mot commence par le préfixe w. La série de Dirichlet de la source, Λ(s)=∑w∈Σ⋆ pws, joue, via la transformée de Mellin, un rôle fondamental dans l’analyse probabiliste des structures de données construites sur les mots de la source. C’est en particulier le cas pour beaucoup de paramètres des tries (nombre de nœuds internes, longueur de cheminement, notamment). Le comportement de la série Λ(s) est souvent d’étude délicate, même dans le cas de sources simples –sources sans mémoire ou chaines de Markov–. Dans ce cas, la série Λ(s) converge pour ℜ s>1 et a un pôle simple en s = 1, mais l’analyse en moyenne des structures de données est fondée sur la géométrie fine des pôles de Λ dans le demi-plan gauche ℜ s ≤ 1. Dans le cas d’une source sans mémoire, d’alphabet fini Σ = [1..r], associée à la famille de probabilités (pi), cette géométrie est étroitement reliée aux propriétés arithmétiques de la famille αk,ℓ=logpℓ/logpk. Il y a deux cas principaux selon que la matrice α := (αk, ℓ) est rationnelle ou non. Dans le cas rationnel, la série Λ(s) a une infinité de pôles régulièrement espacés sur la droite ℜ(s) = 1, tandis que, dans l’autre cas, il existe à gauche de ℜ(s) = 1 une région sans pôles. Je décrirai précisément cette région sans pôles, et montrerai comment sa forme dépend des propriétes d’approximation de la famille α. J’expliquerai aussi comment ces résultats précis permettent d’obtenir une asymptotique fine pour le comportement moyen des tries construits sur ces sources. (Travail commun avec Philippe Flajolet et Brigitte Vallée) | Alice Jacquot [transparents] [résumé] Une bijection inattendue Nous considérons les λ-termes sans variable libre où chaque λ lie exactement une variable. Cet ensemble de λ-termes correspond aux formules de logique dites "BCI" par la bijection de Curry-Howard. Nous présentons une bijection entre ces λ-termes et les cartes triangulées pointées, basée sur la présentation en arbre enrichis d’arcs retour des λ-termes. Cette bijection nous donne une vision alternative à l’énumeration par équation aux dérivées partielles des λ-termes et permet d’en déduire l’asymptotique et d’engendrer des BCI aléatoirement. | 11:15 | |
11:30 | Lucas Gerin [transparents] [résumé] Génération aléatoire de chemins par contraction Les méthodes de génération aléatoire par chaînes de Markov permettent de générer quantité d’objets, elles sont souvent faciles à implémenter et rapides en pratique. L’inconvénient est qu’il est en général difficile d’estimer le temps de convergence de ces algorithmes. Je vais présenter une telle méthode pour générer certains chemins unidimensionnels, et surtout expliquer comment une approche géométrique des chaînes de Markov permet dans ce cas d’obtenir des bornes intéressantes. | 11:30 | ||||
11:45 | Mireille Régnier [transparents] [résumé] Grandes déviations sur des ensembles de mots La motivation de ce travail est l’évaluation précise de la probabilité d’apparition de mots (ou ensembles de mots) exceptionnels. On ordonne alors les mots. À partir de la série génératrice de probabilité d’ensembles de mots, on calcule une formule de grandes déviations, en utilisant la méthode du col. En s’appuyant sur une simulation de Monte-Carlo, on étudiera l’écart à l’(incorrecte) approximation normale. On discutera le lien avec les chevauchements de mots, ou clumps. | Frédéric Paccaut [transparents] [résumé] Arbre de contextes, chaines de Markov d’ordre variable, systemes dynamiques Nous décrivons une méthode pour associer à toute VOMC (ou tout arbre des contextes) un système dynamique de l’intervalle. Nous donnerons plusieurs exemples, avec contexte infini, et décrirons plus précisement la mesure stationnaire associée. | Matthieu Josuat-Vergès [transparents] [résumé] Nombres de Genocchi et tableaux alternatifs Dumont et Foata ont découvert en 1976 des polynômes symétriques en trois variables qui raffinent les nombres de Genocchi. Un problème toujours ouvert est de donner une interprétation combinatoire où la symétrie est apparente. Nous ne répondons pas à cette question, mais nous donnons une nouvelle interprétation de ces polynômes grâce aux tableaux alternatifs, objets apparus dans d’autres contextes (processus d’exclusion asymétrique...) | Éric Rémila [transparents] [résumé] Average Long-Lived Memoryless Consensus:
The Three-Value Case We study strategies that minimize the instability of a fault-tolerant consensus system. More precisely, we find the strategy than minimizes the number of output changes over a random walk sequence of input vectors (where each component of the vector corresponds to a particular sensor reading). We analyze the case where each sensor can read three possible inputs. The proof of this result appears to be much more complex than the proof of the binary case (previous work). In the binary case the problem can be reduced to a minimal cut in a graph. We succeed in three dimensions by using the fact that an auxiliary graph (projected graph) is planar. For four and higher dimensions this auxiliary graph is not planar anymore and the problem remains open (joint work with Ivan Rapaport, (DIM-CMM (umi 2807 CNRS), Universidad de Chile). | 11:45 | |
12:00 | Thomas Fernique [transparents] [résumé] Stochastic Flips on Dimer Tilings We introduce a Markov process inspired by the problem of quasicrystal growth. It acts over dimer tilings of the triangular grid by randomly performing local transformations, called flips, which do not increase the number of identical adjacent tiles (this number can be thought as the tiling energy). Fixed-points of such a process play the role of quasicrystals. We are here interested in the worst-case expected number of flips to converge towards a fixed-point. Numerical experiments suggest a O(n2) bound, where n is the number of tiles of the tiling. We prove a O(n2.5) upper bound and discuss the gap between this bound and the previous one. We also briefly discuss the average-case. | 12:00 | ||||
12:15 | 12:15 | |||||
12:30 | 12:30 | |||||
12:45 | 12:45 | |||||
13:00 | 13:00 | |||||
13:15 | 13:15 | |||||
13:30 | Hubert Larchevêque [transparents] [résumé] Sur la longueur des chemins de recherche dans les skip graphs Dans ce travail nous étudions une structure de données probabiliste nommée skip graph, inspirée des skip lists et mieux adaptée que celles ci au travail dans un environnement distribuée. Nous étudions la hauteur, correspondant au chemin de recherche de longueur maximale, de cette structure probabiliste en nous inspirant des travaux de Devroye sur les skip lists. En particulier nous prouvons que, comme son analogue dans les skip lists, cette hauteur est d’ordre logn. | 13:30 | ||||
13:45 | 13:45 | |||||
14:00 | Philippe Nadeau [transparents] [résumé] Enumeration de configurations de boucles compactes dans un triangle Motivated by the Razumov Stroganov conjecture, we are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with cœfficients computed from TFPL configurations. We then give constraints and enumeration results for certain classes of TFPL configurations. For special boundary conditions, we show that TFPLs are counted by the famous Littlewood Richardson cœfficients. | 14:00 | ||||
14:15 | 14:15 | |||||
14:30 | Cyril Banderier [transparents] [résumé] Allons compter les résidus Je considère les résidus d’ordre m dans ℤ/nℤ (c’est-à-dire le nombre de puissances m-ièmes), pour lesquels je donne quelques formules et les asymptotiques correspondantes, ainsi que quelques séries de Laurent ou de Dirichlet explicites. J’aborde aussi d’autres questions d’une nature similaire qui ont des applications en tomographie quantique. | 14:30 | ||||
14:45 | 14:45 | |||||
15:00 | Éric Fusy [transparents] [résumé]
Distances dans les arbres plans et cartes planaires Nous proposons un survol des techniques permettant d'obtenir les facteurs d'échelle et distributions limites pour les paramètres de distance (distances typiques ou distances extremales) sur les arbres plans et cartes planaires (quadrangulations) aléatoires à n sommets. Pour les arbres plans on montre par décomposition et séries génératrices que le facteur d'échelle est n1/2. Pour les quadrangulations, on s'appuie sur une bijection due à Gilles Schaeffer et sur les séries génératrices pour montrer que le facteur d'échelle est n1/4. Si le temps le permet nous montrerons que l'on peut aussi prouver des propriétés de type "large déviation" sur les distances, pour les arbres plans, cartes planaires, et meme graphes planaires (non plongés) aléatoires. | Brigitte Vallée [transparents] [résumé] Théorie de l'information : modèles, algorithmes, analyse Tout étudiant d'un cours d'algorithmique de base apprend que la complexité moyenne de l'algorithme QuickSort est en O(n logn), celle de QuickSelect est en O(n) et celle de RadixSort est en O(n logn). De tels énoncés ont le mérite d'être simples, mais leur simplicité est trompeuse, car ils sont fondés sur des hypothèses spécifiques à chaque algorithme: pour les deux premiers algorithmes, le coût unitaire est la comparaison entre clés, tandis que, pour le troisième, le coût unitaire est la comparaison entre symboles. Ces études souffrent donc de deux inconvénients majeurs: il n'est pas possible de comparer réellement ces algorithmes entre eux, car les mesures de coût sont différentes. Ensuite, la mesure de coût adoptée pour analyser QuickSort ou QuickSelect est peu réaliste, dès que les clés ont une structure complexe, ce qui est le cas dans le contexte des bases de données ou de la langue naturelle, par exemple. Pour effectuer une analyse réaliste, il faut donc d'abord travailler en théorie de l'information pour définir un cadre adapté. En théorie de l'information, une source est un mécanisme aléatoire qui produit des symboles d'un alphabet donné. On construit ici un modèle de source très général, qui prenne en compte la possibilité de corrélations importantes entre symboles émis. Les clés considérées par l'algorithme sont alors des mots produits (indépendamment) par la même source. Il faut ensuite considérer un coût unitaire qui soit le même pour tous les algorithmes: c'est la comparaison entre symboles, et le coût de l'algorithme est donc le nombre total de comparaisons effectuées entre symboles. Nous revisitons ainsi, dans un tel modèle, à la fois unifié et réaliste, l'analyse probabiliste de trois principaux algorithmes: QuickSort, QuickSelect, et les algorithmes de dictionnaire fondés sur la structure de trie. Ce mini-cours est fondé sur des travaux communs avec Julien Clément, James Fill, et Philippe Flajolet. | Nicolas Schabanel [transparents] [résumé] Fabriquer du hasard avec des conjectures d’informatique théorique Pour pouvoir mener à bien des simulations sur des structures aléatoires, il est souhaitable de disposer d’une suite satisfaisant des propriétés a priori contradictoires: être alátoire (pour que la simulation soit valide), et être engendré par un processus déterministe, afin de pouvoir relancer son programme sur la même valeur pour le débugger par exemple. Nous verrons comment des travaux en cryptographie permettent de concilier ces deux objectifs a priori contradictoires en s’appuyant sur des conjectures d’informatique théoriques. Ces résultats reposent sur de jolies démonstrations mathématiques et d’intéressants arguments probabilistes que cet exposé passera en revue. | 15:00 | ||
15:15 | 15:15 | |||||
15:30 | 15:30 | |||||
15:45 | 15:45 | |||||
16:00 | 16:00 | |||||
16:15 | 16:15 | |||||
16:30 | Johan Oudinet [transparents] [résumé] Génération aléatoire de chemins
dans des automates Mes travaux portent sur la génération aléatoire de chemins dans des automates et je pourrai exposer mes derniers résultats sur la comparaison de variantes de méthodes de génération aléatoire dans un souci de tirer de longs chemins dans des automates de tailles conséquentes. | 16:30 | ||||
16:45 | Vlady Ravelomanana [transparents] [résumé] Random 2-XOR-SAT and MAX-2-XOR-SAT and their phase transitions We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y= 0 or x ⊕ y= 1. Formula of size m on n Boolean variables are chosen uniformly at random from among all Cmn(n−1) possible choices. In the first part of this talk, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of SAT/UNSAT transition. In the second part of the talk, we consider the optimization version, known as MAX-2-XORSAT, of the previous decision problem. The MAX-2-XORSAT problem asks for the maximum number of clauses which can be satisfied by any assignment of the variables in a 2-XOR formula. Let Xn,m be the minimum number of clauses that can not be satisfied in a formula with n variables and m clauses. We give precise characterizations of the random variable Xn,m for m = Θ(n). The results describe phase transitions in the optimization context similar to those encountered in decision problems. (Joint work with Hervé Daudé and Vonjy Rasendrahasina) | Cyril Nicaud [transparents] [résumé] Sous-groupes aléatoires d’un groupe libre Soit A un alphabet fini. Le groupe libre F(A) est l’ensemble des mots réduits composés de lettres de A et d’inverses (formels) de lettres de A. On s’intéresse dans cet exposé aux sous-groupes finiment engendrés de F(A), c’est-à-dire, aux sous-groupes engendrés par un ensemble fini de mots réduits, appelés les générateurs. Il y a toute une littérature sur les propriétés de tels sous-groupes pour la distribution uniforme sur les ensembles de k générateurs de longueur au plus n, où on s’intéresse à l’asymptotique en n quand k reste fixe. Avec Frédérique Bassino et Pascal Weil nous avons proposé une autre distribution. Les sous-groupes finiments engendrés peuvent être représentés, de façon unique, par des sortes d’automates finis. Cette représentation est utilisée aussi bien pour démontrer des résultats que pour coder les sous-groupes en machine. En prenant comme taille d’un sous-groupe le nombre d’états de sa représentation, on s’intéresse à la distribution uniforme sur les sous-groupes de taille fixée. Je parlerai au passage de comment on peut générer aléatoirement ces objets. Pour comparer les deux distributions, on s’intéressera à des propriétés algébriques, en cherchant à savoir si elles sont presque toujours ou presque jamais vérifiées. Le traitement du premier modèle fait intervenir certain types de mots (les mots de Smyrnov), et de l’analyse de singularité. Pour le deuxième modèle il faut étudier les propriétés d’injections partielles aléatoires, et la méthode du col se trouve particulièrement adaptée pour cette l’analyse. Ces différents travaux ont été effectués en collaboration avec Frédérique Bassino, Dominique Gouyou-Beauchamps, Armando Martino, Enric Ventura et Pascal Weil. | 16:45 | |||
17:00 | Guy Louchard [transparents] [résumé] A simple case of the Mahonian statistic: A saddle point approach Recently Canfield, Janson and Zeilberger analyzed the Mahonian distribution on multiset permutations: permutations on n objects can be viewed as words in the alphabet {1,…,n}. If we allow repetitions, we can consider all words with a1 occurences of 1, a2 occurences of 2, …, am occurences of m. Let Jm denote the number of inversions and N=a1+⋯+am . Let a*=maxj aj and N*=N−a*. Under the uniform model, the authors prove that, if N* → ∞ then the sequence of normalized random variables (Jm−E(Jm))/σ(Jm) tends to the standard normal distribution. They also conjecture a local limit theorem and prove it under additional hypotheses. In this talk, we analyze simple examples of the Mahonian statistic, for instance, we consider the case m=2,a1=an,a2=bn,n→∞. We analyze the central region j= E(Jm) +xσ and one large deviation j= E(Jm) +xn7/4. Continuing the approach we used previously for classical inversions in permutations, we use the Saddle point method : we obtain local limit theorems with some corrections of order 1/n. | 17:00 | ||||
17:15 | 17:15 | |||||
17:30 | Boite à idées [transparents] | 17:30 | ||||
17:45 | 17:45 | |||||
18:00 | 18:00 | |||||
18:15 | Noy / Fusy [transparents] | Kirone Mallick | Brigitte Vallée [transparents] | 18:15 | ||
18:30 | 18:30 | |||||
18:45 | 18:45 | |||||
19:00 | 19:00 | |||||
19:15 | 19:15 |
Dernière modification le vendredi 2 avril 2010 à 14:32:40.
Olivier Roussel, selon une maquette d'Emmanuel Thomé.
Olivier Roussel, selon une maquette d'Emmanuel Thomé.