MORCRETTE Basile
Supervision : Michèle SORIA
Co-supervision : FLAJOLET Philippe, DUMAS Philippe
Analytic Combinatorics and urn models
This thesis studies Polya urns through the analytic combinatorics point of view. Urns are conceptually very simple models of growth or extinction dynamics for which the limiting behaviors are extremely diverse. Those models are widely studied by probabilistic approach, but the precise understanding of the variety of limit laws is still an open question. Since 2005, the work of Flajolet et al. shows that an analytic combinatorics approach can be very fruitful for those questions: the study of the properties (nature, singularities) of generating functions linked to urns provides access to many precisions on limit laws. This thesis is a continuation of this work. First, the determination of the nature of the generating functions of urns by a high tech algorithm of computer algebra (automatic Guess'n'Prove) identifies which functions are algebraic. Then, we lead exact and asymptotic analysis for algebraic classes and precise properties on limiting behaviors are thus derived (moments structure, rate of convergence, local limit properties). Second, a study of some non algebraic urns is done through concrete examples linked to some models of social networks, or the combinatorics of some boolean formulas. Third, through the extension of classical models (unbalanced models, random entries for substitution rules), we show that the symbolic aspects of analytic combinatorics are thriving. More specifically, a general combinatorial study for non necessarily balanced urns is done for the first time and links any urn to a partial differential equation.
Defence : 06/26/2013
Jury members :
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]
2012-2013 Publications
-
2013
- B. Morcrette : “Combinatoire analytique et modèles d’urnes”, thesis, phd defence 06/26/2013, supervision Soria, Michèle, co-supervision : 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)