Etude probabiliste d'arbres issus de l'algorithmique
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
The aim of this thesis is the study of the behavior of trees used in analysis of algorithms. We use probabilistic techniques to study various random objects connected with trees. We formally define the trees we deal with and introduce our main results in chapter one. Each of the three other parts of the thesis contains a specific random phenomenon. We first establish a result on the asymptotics of the rescaled occupation measure of a branching random walk on binary search trees (BSTs). Under weak hypothesis on the increments, we show that this measure converges to a deterministic measure depending on the stable law whose domain of attraction contains the law of the increments. The proof is based on some fundamental properties of the structure of BST. One of them is the result by Louchard on the height of a typical node. This convergence allows to obtain results on two other objects associated to the BST : homogeneous fragmentations of ]0, 1[ and recursive trees. The second study is also on BSTs. We study the profile of the tree (number of leaves at each level) specifying the types of the leaves : arms are the leaves whose brother is an internal node and feet are the leaves whose brother is also a leaf. We use a vector whose coordinates are the level polynomials of arms and feet. The coefficient of order k of these polynomials is the number of arms and feet at level k in the BST of size n. Comparing the two projections of this vector on the eigenspaces of a so-called evolution matrix, we obtain an almost sure and a L2-convergence of a martingale vector, connected to the profile, to a vector associated to the limit of the Jabbour martingale. Finally, the last part deals with another kind of random trees : the suffix trees. These trees are defined from an infinite word and its randomness is given by the source that creates the word. Here we are concerned with -mixing sources. We prove that the fill-up level of a suffix tree with n keys, normalized by log n, converges almost surely to a constant depending on the source. By definition of the suffix trees, the study of this parameter happens to be a word apparition time issue. We obtain the convergence using results of Abadi and Vergne in this field.
Abstract FR:
Cette thèse porte sur l’étude du comportement d’arbres aléatoires issus de l’algorithmique. Nous utilisons des techniques probabilistes pour étudier des objets aléatoires liés aux arbres. Outre le chapitre 1, dans lequel sont définis formellement plusieurs types d’arbres aléatoires et où sont introduits les résultats principaux, la thèse est composée de trois parties qui portent chacune sur l’étude d’un phénomène aléatoire. Nous établissons dans un premier temps un résultat sur l’asymptotique de la mesure d’occupation d’une marche aléatoire branchante dont l’arbre sous-jacent est un arbre binaire de recherche (ABR). Avec des hypothèses très faibles sur les incréments des marches, nous montrons que cette mesure, une fois renormalisée, converge vers une mesure déterministe qui est liée à la loi stable dont le domaine d’attraction contient la loi des incréments. La preuve de ce résultat repose, entre autres, sur les propriétés fondamentales de la structure des ABRs comme le résultat de Louchard sur la profondeur typique d’un noeud. Cette convergence permet alors d’obtenir des résultats sur des objets liés à l’ABR : les fragmentations homogènes de l’intervalle ]0, 1[ et les arbres récursifs. La deuxième étude traite aussi des ABRs. On s’intéresse au profil de l’arbre (nombre de feuilles à chaque profondeur) en regardant les feuilles selon les types définis par Dekking : les bras, feuilles dont le frère est un noeud interne, et les jambes, feuilles dont le frère est aussi une feuille. On utilise un vecteur dont les coordonnées sont les polynômes appelés polynômes de niveau des bras et des jambes. Les coefficients d’indice k des polynômes de niveau sont respectivement le nombre de bras et de jambes à la hauteur k dans l’ABR de taille n. On obtient, en comparant les deux projections du vecteur sur les sous-espaces propres de la matrice d’évolution, une convergence L2 et presque sûre d’une martingale vectorielle, liée au profil, vers un vecteur associé à la limite de la martingale de Jabbour. Enfin, le dernier chapitre concerne un autre type d’arbres, les tries des suffixes. Ces arbres sont définis à partir d’un mot infini et leur aléa est donné par la source qui génère ce mot. Nous considérons ici une source dynamique -mélangeante. Nous montrons que la hauteur de saturation de l’arbre à n clefs, renormalisée par ln n, converge presque sûrement vers une constante liée à la source. L’étude de ce paramètre se traduit naturellement comme un problème de temps d’apparition de mots que nous résolvons grâce aux travaux de Abadi et Vergne sur le sujet.