Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

Marches aléatoires conditionnées, martingales et arbres m-aires de recherche

le 10 décembre 2008

Le mercredi 10 décembre 2008 à 15H00

à l'Université de Versailles Saint-Quentin-en-Yvelines UFR des Sciences Bâtiment Fermat - Amphithêatre F 45 avenue des Etats-Unis 78000 Versailles

Par Monsieur Jean-Maxime LABARBE Discipline : Mathématiques Laboratoire : LMV

Nous nous intéressons dans le chapitre 1 au comportement asymptotique des marches aléatoires conditionnées par le nombre de pics (un pic est un maximum  local). Nous montrons que, convenablement renormalisées, ces marches convergent en loi. Les trajectoires limites apparaissant sont les mêmes que dans le cas des marches non conditionnées, mais le nombre de pics imposés a une influence sur l'ordre de grandeur des marches. Nous étudions également le processus de comptage des pics et montrons que ce processus (normalisé) converge en loi vers un pont brownien indépendant de la trajectoire limite. Enfin, nous donnons quelques applications de nos résultats de convergence en loi, notamment en termes d'arbres planaires. Dans le chapitre 2, nous étudions l'arbre m-aire de recherche d'un point de vue probabiliste, sous le modèle de permutations aléatoires. Le résultat que nous obtenons est un résultat de convergence uniforme et presque sûre du profil de l'arbre m-aire de recherche (c'est-à-dire portant sur le nombre de feuilles d'un type donné à un niveau donné). Pour y parvenir, nous utilisons d'une part une technique de plongement de l'arbre m-aire de recherche dans un modèle d'arbres m-aires en temps continu, plus riche. D'autre part, nous codons le profil par une fonctionnelle appelée polynôme de niveau et mettons en évidence une nouvelle famille de martingales (indexées par un paramètre complexe z) associée à l'arbre m -aire de recherche. Ces martingales ont un lien, que nous explicitons, avec les martingales plus classiques du modèle en temps continu. Puis, nous obtenons leur convergence presque sûre et dans L1 pour un certain domaine du paramètre z. De plus, nous identifions la zone maximale réelle de convergence L1. Nous montrons également que ces martingales admettent une limite commune  satisfaisant, presque sûrement, une équation de point fixe stochastique. Le plongement et la structure de martingale nous permettent enfin d'établir l'expression asymptotique du polynôme de niveau puis celle du profil.

 

 

Abstract : Conditioned random walks, martingales and m-ary search trees.

Chapter one deals with the asymptotics of random walks with a given number of peaks (a pic is a local maximum). We show that, suitably rescaled, these random walks converge in distribution. The limiting trajectories are the same as for non conditioned walks but the number of peaks has an effect on the order of magnitude of the trajectories.The counting process of the peaks is also studied. It is shown that suitably normalized; it converges to a Brownian bridge which is independent of the limiting trajectory. Applications are provided, in particular in terms of plane trees. We study, in Chapter two, m-ary search trees under the random permutation model. We obtain a uniform almost sure result regarding the profil, i.e the number of nodes of a given type, at a given level. We use an embedding of the m-ary search tree into a continuous-time m-ary tree model on the one hand and we encode the profile with the help of the so-called level polynomial that leads to a study of martingales (with a complex parameter z) on the other hand. We give the connections between the martingales associated to each model. Then we obtain their convergences (a.s. and in L1) for z belonging to some open complex set. Moreover, we identify the optimal real area of L1 convergence. We also show that the limit martingales satisfy some almost sure versions of stochastic fixed point equations. Last, the embedding and the martingale structure provide the asymptotics of the level polynomial and of the profile.

Informations complémentaires

Quansheng LIU, Professeur des Universités à l'Université de Bretagne Sud - Rapporteur Abderrahmen TOUATI, Professeur des Universités à l'Ecole Supérieure des Statistiques et d'Analyse de l'Information, Tunisie - Rapporteur Jean-François MARCKERT, Chargé de Recherche au CNRS, à l'Université de Bordeaux 1 - Examinateur Catherine LAREDO, Directrice de Recherche à l'Institut National de la Recherche Agronomique, Jouy-en-Josas - Examinatrice Brigitte CHAUVIN, Professeur des Universités à l'Université de Versailles Saint-Quentin-en-Yvelines - Examinatrice Nicolas POUYANNE, Maître de Conférences, Habilité à diriger des recherches, à l'Université de Versailles Saint-Quentin-en-Yvelines - Examinateur Alain ROUAULT, Professeur des Universités à l'Université de Versailles Saint-Quentin-en-Yvelines - Directeur de Thèse