MORCRETTE Basile
Direction de recherche : Michèle SORIA
Co-encadrement : FLAJOLET Philippe, DUMAS Philippe
Combinatoire analytique et modèles d'urnes
Cette thèse étudie les urnes de Polya à travers le prisme de la combinatoire analytique. Les urnes sont des modèles, conceptuellement très simples, de dynamique de croissance ou d'extinction dont les comportements limites sont extrêmement variés. Ces modèles sont largement étudiés par des approches probabilistes mais la compréhension précise des diverses lois limites reste une question ouverte. Les travaux de Flajolet et al. en 2005 ont illustré que pour ces questions, une approche par combinatoire analytique peut se révéler très fructueuse : l'étude des propriétés (nature, singularités) des séries génératrices associées aux urnes donne accès à des lois limites avec grande précision. Cette thèse s'inscrit dans la continuité de ces travaux et commence par identifier les séries des urnes de nature algébrique, grâce à un algorithme sophistiqué issu du calcul formel (Divination/Preuve automatique). Pour les classes d'urnes algébriques, nous menons des analyses, exacte et asymptotique, afin de connaître avec précision les comportements limites (structures des moments, vitesse de convergence, aspects limites locaux). Puis, l'étude d'urnes non algébriques est faite au travers d'exemples concrets portant sur la modélisation de réseaux sociaux, ainsi que sur la combinatoire des formules booléennes. Enfin, à travers des modèles d'urnes plus généraux (absence d'équilibre et présence d'aléa au sein des règles de substitution), nous montrons que l'approche symbolique de la combinatoire analytique est robuste. En particulier, une étude combinatoire générale des urnes sans condition d'équilibre est réalisée pour la première fois, unissant toute urne à une équation aux dérivées partielles.
Soutenance : 26/06/2013
Membres du jury :
Mme BÉRARD Béatrice (Université Pierre et Marie Curie)
M. BOSTAN Alin (Inria Saclay)
Mme BOUSQUET-MÉLOU Mireille (CNRS - Université de Bordeaux 1)
M. CHASSAING Philippe (Institut Élie Cartan - Université de Lorraine)
Mme CHAUVIN Brigitte (Université de Versailles Saint-Quentin-en-Yvelines) [Rapporteur]
M. DUMAS Philippe (Inria Saclay)
Mme SORIA Michèle (Université Pierre et Marie Curie)
Mme VALLÉE Brigitte (CNRS - Université de Caen)
M. Hsien-Kuei HWANG (Academia Sinica) [Rapporteur]
Publications 2012-2013
-
2013
- B. Morcrette : “Combinatoire analytique et modèles d’urnes”, soutenance de thèse, soutenance 26/06/2013, direction de recherche Soria, Michèle, co-encadrement : Flajolet, Philippe, Dumas, Philippe (2013)
-
2012
- B. Morcrette, Hosam M. Mahmoud : “Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology”, 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), vol. DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings, Montreal, Canada, pp. 219-232, (Discrete Mathematics and Theoretical Computer Science) (2012)
- B. Morcrette : “Fully Analyzing an Algebraic Polya Urn Model”, LATIN 2012 : 10th Latin American Theoretical INformatics Symposium, vol. 7256, Lecture Note in Computer Science, Arequipa, Peru, pp. 568-581, (Springer-Verlag Berlin Heidelberg) (2012)