Arbres booléens aléatoires et urnes de Polya : approches combinatoire et probabiliste
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
This thesis deals with two random objects: random Boolean trees and Pólya urns. These two objects, which are both related to theoretical computer science, are studied in this thesis via analytic combinatorics and probabilistic methods. In the first part of the thesis, we define and compare different probability distributions on the set of Boolean functions via their tree representation. We show that all these distribution weight mostly low complexity functions and that some of them are even degenerated, meaning that they only weight very few boolean functions. A Pólya urn is a discrete random process, that can be used to modelize numerous objects of theoretical computer science such as, m-ary search trees, 2-3 trees, AVL, among others. In the second part of this thesis, we study balanced, irreducible Pólya urns with nonnegative coefficients. Random variables W arise from the asymptotic behaviour of such an urn, and of its embedding in continuous time. We study them in discrete and continuous time via the underlying tree-structure of the urn, and prove that they are solutions of systems of equations in law. This new approach allows us to prove that the variables W are momentdetermined, and, above all, to study the variables W both for two-coloured and d-coloured Pólya urns.
Abstract FR:
Cette thèse étudie deux objets aléatoires discrets : les arbres booléens aléatoires et les urnes de Pólya. Ces deux objets, tous deux en lien avec l'informatique fondamentale, sont étudiés dans ce mémoire via des méthodes de combinatoire analytique et de probabilités. Dans la première partie de cette thèse, nous définirons et comparerons plusieurs distributions de probabilité sur l'ensemble des fonctions booléennes via leur représentation par des arbres booléens. Nous verrons que toutes ces distributions chargent préférentiellement les fonctions booléennes de faible complexité, et que certaines d'entre elles sont dégénérées au sens où elles ne chargent qu'un petit nombre de fonctions booléennes. Nous étudions dans la seconde partie de ce mémoire des urnes de Pólya équilibrées, irréductibles et à coefficients positifs. Le comportement asymptotique d'une telle urne, ainsi que celui de son plongement en temps continu, font intervenir des variables aléatoires W assez méconnues à ce jour. Nous étudions ces variables aléatoires W via la structure arborescente de l'urne et montrons qu'elles sont solution de systèmes d'équations en loi, ce qui nous permet notamment d'établir que ces variables aléatoires sont déterminées par leurs moments, et surtout d'aborder cette étude aussi bien pour des urnes à deux couleurs que pour des urnes à d couleurs.