No description available.

Dans cette thèse, on étudie des liens entre processus d'exploration et arbres aléatoires avec ou sans interaction, pour en déduire des extensions du théorème de Ray Knight. Dans la première partie nous décrivons une certaine bijection entre l'ensemble des processus d'exploration et l'ensemble des arbres binaires. On montre que l'arbre associé à un processus d'exploration défini avec les paramètres mu et lambda décrivant les taux de ses minimas et maximas locaux respectivement à n'importe quel instant considéré, est un arbre binaire aléatoire de taux de naissance mu et de taux de mort lambda. De cette correspondance, nous déduisons une représentation discrète d'un processus de branchement linéaire en terme de temps local d'un processus d'exploration. Après renormalisation des paramètres, nous en déduisons une preuve du théorème de Ray Knight généralisé donnant une représentation en loi d'un processus de Feller linéaire en terme du temps local du mouvement brownien réfléchi en zéro avec une dérive. Dans la deuxième partie, nous considérons un modèle de population avec compétition définie par une fonction polynomiale f(x) = x^{alpha}, alpha>0 et partant de m ancêtres à l'instant initial 0. On étudie l'effet de la compétition sur la hauteur et la longueur de la forêt d'arbres généalogiques quand m tend vers l'infini. On montre que la hauteur est d'espérance finie si alpha> 1, et est infinie dans le cas contraire, tandis que la longueur est d'espérance finie si alpha > 2, et est infinie dans le cas contraire. / In this thesis, we study connections between explorations processes and random trees, from which we deduce Ray Knight Theorem. In the first part, we describe a bijection between exploration processes and Galton Watson binary trees. We show that the tree we obtain under the curve of an exploration process whose maxima and minima rates are respectively lambda and mu, is a Galton Watson binary tree with birth rate mu and death rate lambda. From this correspondence, we establish a discrete Ray Knight representation of the process population size of a Galton Watson tree in term of local time of exploration process associated to this tree. After some renormalization, we deduce from this discrete approximation with a limiting argument, a generalized Ray Knight theorem giving a representation of a Feller branching process in term of local time of a reflected Brownian motion with a linear drift. In the second part, we consider a population model with competition defined with a function f(x) = x^{alpha}. We study the effect of the competition on the height and the length of the genealogical trees of a large population. We show that the expectation of the height has a finite expectation stays finite if alpha> 1 and is infinite almost surely if alpha le 1, while the length has a finite expectation if alpha > 2, and is infinite almost surely if alpha le 2. In the last part, we consider a population model with interaction defined with a more general non linear function f.

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.