Supervision: I started my PhD in September 2010 in the team Algorithms (INRIA Rocquencourt) under the supervision of Philippe Flajolet. Since his sudden death in March 2011 and the move of the Algo team to Palaiseau, I'm continuing my PhD under the supervision of Philippe Dumas (SpecFun, Inria Saclay/Palaiseau). My co-advisor is Michèle Soria at LIP6 (UPMC).
Key-words: Analytic combinatorics, limit laws, Pólya urns and applications, computer algebra algorithm, partial differential equation.
Abstract:
My thesis studies Pólya 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.
My research is a continuation of this work. First,
we determine the nature of the generating functions of urns by a high tech algorithm of computer algebra (automatic Guess'n'Prove) in order to identify 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.
Before the thesis:
Before beginning my PhD, I did my MPRI Master internship at the same place. I could understand first things about Urn Models. I invite you to read my Master Thesis and the slides of my oral presentation.
Before the discovery of the wonderful world of Combinatorics, I did an internship during my first year of Master at the Aachen University (Aix-la-Chapelle, Germany) RWTH
Aachen supervised by
Wolfgang Thomas on the subject dealing with Model-Checking, Monadic Second Order Logic and Infinite Graphs.
Talk
at RWTH Aachen, August 2008, MSO-Model-Checking over Infinite Graphs : Taking Caucal to the Limit slides.
Slides of the french talk for Master, and the Master report : Model-checking des MSO-formules sur des structures infinies.
August 2014 : Summer School in Nablus, Palestine : Introductive course on Analytic Combinatorics, Summer School "Random structures, Analytic and Probabilistic Approaches"
June 2013 : ANR Boole , Paris : ANR Boole
May 2013 : AofA 2013, Spain : On unbalanced urn models
November 2012 : Séminaire combinatoire du LIX, Ecole Polytechnique : Algebraic Analytic Urns
From Sept. 5 to Sept. 7, 2012 : French-British Workshop on Analytic Combinatorics, University of Oxford, UK. A gentle introduction to Analytic Combinatorics, for PhD students.
August 2012 : PCC 2012, University of Warwick, UK : Exactly Solvable Pólya Urn Models via Analytic Combinatorics slides
June 2012 : AofA 2012, Montreal, Canada : Exactly solvable balanced tenable urns with random entries via the analytic methodology slides
April 2012 : LATIN 2012, Arequipa, Peru : Fully Analyzing an Algebraic Pólya Urn Model slides
March 2012 : ALEA 2012, CIRM Luminy : Balanced Pólya Urns: who is algebraic ? slides
February 2012 : CALIN Seminar , LIPN (Paris 13) : Pólya Urn Models : an Analytics Combinatorics Approach
December 2011 : Philippe Flajolet and Analytic Combinatorics, Paris-Jussieu, 14-15-16 December 2011. Conference in the memory of Philippe Flajolet. Pólya Urn Models : The Analytic Approach slides
June 2011 : ANR Boole , Nantes : : Urnes de Pólya par la combinatoire analytique slides
June 2011 : AofA 2011, Bedlewo, Poland : Analysis of an algebraic class of Pólya urn models slides
March 2011 : ALEA 2011, CIRM Luminy : Urnes de Pólya : analyse d'une classe algébrique slides
September 2010 : Oral presentation Master 2 : Combinatoire analytique et modèles d'urnes slides
September 2008 : Oral presentation Master 1 : Model-checking des MSO-formules sur des structures infinies slides
August 2008 : RWTH Aachen : MSO-Model-Checking over Infinite Graphs : Taking Caucal to the Limit slides
-- Exactly solvable balanced tenable urns with random entries via the analytic methodology , B.Morcrette and Hosam M.Mahmoud pdf, accepted in AofA 2012 (Montreal, 17--22 juin 2012). 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms. DMTCS Proceedings, vol. AQ, pp. 219--232
-- Fully Analyzing an Algebraic Pólya Urn Model , B.Morcrette pdf , accepted in LATIN 2012 (16--20 April 2012) Latin American Symposium on Theoretical Informatics. LNCS 7256, pp. 568-581, Springer, 2012.
-- Internship report, Master 2 MPRI : Combinatoire analytique et modèles d'urnes , B.Morcrette P.Flajolet, Sept. 2010, pdf
-- Internship report, Master 1 MPRI : Model-checking des MSO-formules sur des structures infinies , B.Morcrette W.Thomas, Sept. 2008, pdf
During my PhD, I'm also teaching assistant at UPMC in Jussieu.
Between 2010 and 2013, I taught for First and Second year of university Students in Computer Science:
-- Recursive Programming in Scheme, see course's web page.
-- Discrete Structures (automata, logic), see course's web page.
-- Elementary Algorithmics (basic complexity, termination and correctness, sorts, trees, graphs)
In 2009-2010, I did oral interrogation for preparing students of Competitve exams for Grandes Ecoles (Classes préparatoires at Lycée Condorcet, Paris 9ème arrondissement).