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.

Les limites d'échelle de grands arbres aléatoires jouent un rôle central dans cette thèse.Nous nous intéressons plus spécifiquement au comportement asymptotique de plusieurs fonctions codant des arbres de Galton-Watson conditionnés. Nous envisageons plusieurs types de conditionnements faisant intervenir différentes quantités telles que le nombre total de sommets ou le nombre total de feuilles, avec des lois de reproductions différentes.Lorsque la loi de reproduction est critique et appartient au domaine d'attraction d'uneloi stable, un phénomène d'universalité se produit : ces arbres ressemblent à un même arbre aléatoire continu, l'arbre de Lévy stable. En revanche, lorsque la criticalité est brisée, la communauté de physique théorique a remarqué que des phénomènes de condensation peuvent survenir, ce qui signifie qu'avec grande probabilité, un sommet de l'arbre a un degré macroscopique comparable à la taille totale de l'arbre. Une partie de cette thèse consiste à mieux comprendre ce phénomène de condensation. Finalement, nous étudions des configurations non croisées aléatoires, obtenues à partir d'un polygône régulier en traçant des diagonales qui ne s'intersectent pas intérieurement, et remarquons qu'elles sont étroitement reliées à des arbres de Galton-Watson conditionnés à avoir un nombre de feuilles fixé. En particulier, ce lien jette un nouveau pont entre les dissections uniformes et les arbres de Galton-Watson, ce qui permet d'obtenir d'intéressantes conséquences de nature combinatoire.

No description available.

Nous nous intéressons à trois problèmes issus du monde des arbres aléatoires discrets et continus. Dans un premier lieu, nous faisons une étude générale des arbres de fragmentation auto-similaires, étendant certains résultats de Haas et Miermont en 2006, notamment en calculant leur dimension de Hausdorff sous des hypothèses malthusiennes. Nous nous intéressons ensuite à une suite particulière d’arbres discrets k-aires, construite de manière récursive avec un algorithme similaire à celui de Rémy de 1985. La taille de l’arbre obtenu à la n-ième étape est de l’ordre de n^(1/k), et après renormalisation, on trouve que la suite converge en probabilité vers un arbre de fragmentation. Nous étudions également des manières de plonger ces arbres les uns dans les autres quand k varie. Dans une dernière partie, nous démontrons la convergence locale en loi d’arbres de Galton-Watson multi-types critiques quand on les conditionne à avoir un grand nombre de sommets d’un certain type fixé. Nous appliquons ensuite ce résultat aux cartes planaires aléatoire pour obtenir la convergence locale en loi de grandes cartes de loi de Boltzmann critique vers une carte planaire infinie. / We study three problems related to discrete and continuous random trees. First, we do a general study of self-similar fragmentation trees, extending some results established by Haas and Miermont in 2006, in particular by computing the Hausdorff dimension of these trees under some Malthusian hypotheses. We then work on a particular sequence of k-ary growing trees, defined recursively with a similar method to Rémy’s algorithm from 1985. We show that the size of the tree obtained at the n-th step if of order n^(1/k), and, after renormalization, we prove that the sequence convergences to a fragmentation tree. We also study embeddings of the limiting trees as k varies. In the last chapter, we show the local convergence in distribution of critical multi-type Galton-Watson trees conditioned to have a large number of vertices of a fixed type. We then apply this result to the world of random planar maps, obtaining that large critical Boltzmann-distributed maps converge locally in distribution to an infinite planar map.

L’objet de cette thèse est d’étudier plusieurs modèles probabilistes reliant les marches aléatoires et les arbres aléatoires issus de processus de branchement critiques.Dans la première partie, nous nous intéressons au modèle de marche aléatoire à valeurs dans un réseau euclidien et indexée par un arbre de Galton–Watson critique conditionné par la taille. Sous certaines hypothèses sur la loi de reproduction critique et la loi de saut centrée, nous obtenons, dans toutes les dimensions, la vitesse de croissance asymptotique du nombre de points visités par cette marche, lorsque la taille de l’arbre tend vers l’infini. Ces résultats nous permettent aussi de décrire le comportement asymptotique du nombre de points visités par une marche aléatoire branchante, quand la taille de la population initiale tend vers l’infini. Nous traitons également en parallèle certains cas où la marche aléatoire possède une dérive constante non nulle.Dans la deuxième partie, nous nous concentrons sur les propriétés fractales de la mesure harmonique des grands arbres de Galton–Watson critiques. On comprend par mesure harmonique la distribution de sortie, hors d’une boule centrée à la racine de l’arbre, d’une marche aléatoire simple sur cet arbre. Lorsque la loi de reproduction critique appartient au domaine d’attraction d’une loi stable, nous prouvons que la masse de la mesure harmonique est asymptotiquement concentrée sur une partie de la frontière, cette partie ayant une taille négligeable par rapport à celle de la frontière. En supposant que la loi de reproduction critique a une variance finie, nous arrivons à évaluer la masse de la mesure harmonique portée par un sommet de la frontière choisi uniformément au hasard. / The aim of this Ph. D. thesis is to study several probabilistic models linking the random walks and the random trees arising from critical branching processes.In the first part, we consider the model of random walk taking values in a Euclidean lattice and indexed by a critical Galton–Watson tree conditioned by the total progeny. Under some assumptions on the critical offspring distribution and the centered jump distribution, we obtain, in all dimensions, the asymptotic growth rate of the range of this random walk, when the size of the tree tends to infinity. These results also allow us to describe the asymptotic behavior of the range of a branching random walk, when the size of the initial population goes to infinity. In parallel, we treat likewise some cases where the random walk has a non-zero constant drift.In the second part, we focus on the fractal properties of the harmonic measure on large critical Galton–Watson trees. By harmonic measure, we mean the exit distribution from a ball centered at the root of the tree by simple random walk on this tree. If the critical offspring distribution is in the domain of attraction of a stable distribution, we prove that the mass of the harmonic measure is asymptotically concentrated on a boundary subset of negligible size with respect to that of the boundary. Assuming that the critical offspring distribution has a finite variance, we are able to calculate the mass of the harmonic measure carried by a random vertex uniformly chosen from the boundary.

Made available in DSpace on 2016-04-29T13:32:32Z (GMT). No. of bitstreams: 1 Maria Cecilia de Vilhena Moraes Silva.pdf: 1246481 bytes, checksum: b36c2aeff72f55fcdd6467b0a7b3dc27 (MD5) Previous issue date: 2010-06-16 / Since they were created, psychological tests have been used in different contexts to support decisions that affect the life of many people. If they are to be used properly, it is critical to know both their underlying theoretical assumptions and their limitations. This thesis aims to bring to light such assumptions and to demonstrate that psychological tests , as a generic label, is not suited for the broad array of psychological assessment techniques available today. Based on the work of Pierre Bourdieu, who considers scientific knowledge as a social activity and the conformation of scientific fields as stemming from the configuration of the forces that conform it in a given historical period, this thesis investigates the trajectory of Alfred Binet and Francis Galton, two important actors of the psychological assessment field, considering the personal, social and historical context of their work, and the influence of their contributions to the subsequent conformation of this field. The differences between projective techniques and psychometrical tests are highlighted and the implications of considering both as psychological tests for the conformation of the psychological assessment field in Brazil, today, are discussed. A few issues regarding the education of qualified psychologists for the proper use of these techniques are also considered / Desde sua criação, os testes psicológicos têm sido usados em diferentes contextos, subsidiando decisões que afetam a vida de muitas pessoas. Seu uso adequado tem, como condição fundamental, o conhecimento de seus pressupostos teóricos e de suas limitações. O objetivo deste trabalho é explicitar tais pressupostos e demonstrar que o rótulo genérico testes psicológicos é inadequado para abrigar a diversidade de instrumentos do exame psicológico existentes. Com base em Pierre Bourdieu, considera-se o conhecimento científico como uma atividade social, sendo a conformação de um campo científico decorrente da configuração das forças que o compõem e de seus respectivos pesos em um dado momento histórico. Procura-se recuperar a trajetória de Alfred Binet e de Francis Galton, dois dos principais atores do campo do exame psicológico, abordando o contexto pessoal, social e histórico em que desenvolveram suas obras, e a influência de suas ideias na conformação posterior do campo. A partir disso, procura-se diferenciar técnicas projetivas e testes psicométricos, discutir as implicações de considerá-los sob o mesmo rótulo na conformação do campo do exame psicológico no Brasil de hoje e apontar aspectos importantes da formação do psicólogo para o uso adequado desses instrumentos

Cette thèse se compose de quatre chapitres:Le chapitre 1 étudie la distribution du temps de coalescence (plus récent ancêtre commun) de deux individus tirés au hasard (uniformly) dans la génération actuelle d'un processus de Bienaymé-Galton-Watson en temps continu.Dans le chapitre 2, nous obtenons une représentation de la diffusion de Feller logistique en termes des temps locaux d'un mouvement brownien réfléchi H avec une dérive qui est affine en le temps local accumulé par H à son niveau actuel.Le chapitre 3 considère la diffusion de Feller avec compétition générale. Nous donnons des conditions précises sur le terme de la concurrence, pour le but de décider si le temps d'extinction (qui est aussi la hauteur du processus) reste borné ou non lorsque la taille initiale de la population tend vers l'infini, et de même pour la masse totale du processus.Dans le chapitre 4, nous généralisons les résultats du chapitre 3 pour le cas du processus de branchement à espace d'état continu avec compétition à trajectoires discontinues. / This thesis consists of four chapters:Chapter 1 investigates the distribution of the coalescence time (most recent common ancestor) for two individuals picked at random (uniformly) in the current generation of a continuous time Bienaymé-Galton-Watson process.In chapter 2 we obtain a Ray-Knight representation of Feller's branching diffusion with logistic growth in terms of the local times of a reflected Brownian motion H with a drift that is affine in the local time accumulated by H at its current level.Chapter 3 considers the Feller's branching diffusion with general competition. We give precise conditions on the competition term, in order to decide whether the extinction time (which is also the height of the process) remains or not bounded as the initial population size tends to infinity, and similarly for the total mass of the process.In chapter 4 we generalize the results of chapter 3 to the case of continuous state branching process with competition which has discontinuous paths.

Cette thèse se divise en deux parties. Nous nous intéressons dans un premier temps à des fragmentations d'arbres aléatoires, et aux arbres des coupes associés. Dans le cadre discret, les modèles étudiés sont des arbres de Galton-Watson, fragmentés en enlevant successivement des arêtes choisies au hasard. Nous étudions également leurs analogues continus, l'arbre brownien et les arbres stables, que l'on fragmente en supprimant des points donnés par des processus ponctuels de Poisson. L'arbre des coupes associé à l'un de ces processus, discret ou continu, décrit la généalogie des composantes connexes créées au fur et à mesure de la dislocation. Pour une fragmentation qui se concentre autour de nœuds de grand degré, nous montrons que l'arbre des coupes continu est la limite d'échelle des arbres des coupes discrets correspondants. Dans les cas brownien et stable, nous montrons également que l'on peut reconstruire l'arbre initial à partir de son arbre des coupes et d'un étiquetage bien choisi de ses points de branchement. Nous étudions ensuite un problème portant sur les cartes aléatoires, et plus précisément sur la quadrangulation uniforme infinie du plan (UIPQ). De récents résultats montrent que dans l'UIPQ, toutes les géodésiques infinies issues de la racine sont essentiellement similaires. Nous déterminons la quadrangulation limite obtenue en ré-enracinant l'UIPQ ''à l'infini'' sur de l'une de ces géodésiques. Cette étude se fait en découpant l'UIPQ le long de cette géodésique. Nous étudions les deux parties ainsi créées via une correspondance avec des arbres discrets, puis nous obtenons la limite souhaitée par recollement. / This PhD thesis is divided into two parts. First, we study some fragmentations of random trees and the associated cut-trees. The discrete models we are interested in are Galton-Watson trees, which are cut down by recursively removing random edges. We also consider their continuous counterparts, the Brownian and stable trees, which are fragmented by deleting the atoms of Poisson point processes. For these discrete and continuous models, the associated cut-tree describes the genealogy of the connected components which appear during the cutting procedure. We show that for a ''vertex-fragmentation'', in which the nodes having a large degree are more susceptible to be deleted, the continuous cut-tree is the scaling limit of the corresponding discrete cut-trees. In the Brownian and stable cases, we also give a transformation which rebuilds the initial tree from its cut-tree and a well chosen labeling of its branchpoints. The second part relates to random maps, and more precisely the uniform infinite quadrangulation of the plane (UIPQ). Recent results show that in the UIPQ, all infinite geodesic rays originating from the root are essentially similar. We identify the limit quadrangulation obtained by rerooting the UIPQ at a point ''at infinity'' on one of these geodesics. To do this, we split the UIPQ along this geodesic ray. Using a correspondence with discrete trees, we study the two sides, and obtain the desired limit by gluing them back together.

Cette thèse s'articule autour de la problématique de l'extinction de populations comportant différents types d'individus, et plus particulièrement de leur comportement avant extinction et/ou en cas d'une extinction très tardive. Nous étudions cette question d'un point de vue strictement probabiliste, puis du point de vue de l'analyse des risques liés à l'extinction pour un modèle particulier de dynamique de population, et proposons plusieurs outils statistiques. La taille de la population est modélisée soit par un processus de branchement de type Bienaymé-Galton-Watson à temps continu multitype (BGWc), soit par son équivalent dans un espace de valeurs continu, le processus de diffusion de Feller multitype. Nous nous intéressons à différents types de conditionnement à la non-extinction, et aux états d'équilibre associés. Ces conditionnements ont déjà été largement étudiés dans le cas monotype. Cependant la littérature relative aux processus multitypes est beaucoup moins riche, et il n'existe pas de travail systématique établissant des connexions entre les résultats concernant les processus BGWc et ceux concernant les processus de diffusion de Feller. Nous nous y sommes attelés. Dans la première partie de cette thèse, nous nous intéressons au comportement de la population avant son extinction, en conditionnant le processus de branchement X_t à la non-extinction (X_t≠0), ou plus généralement à la non-extinction dans un futur proche 0≤θ<∞ (X_{t+θ}≠0), et en faisant tendre t vers l'infini. Nous prouvons le résultat, nouveau dans le cadre multitype et pour θ>0, que cette limite existe et est non-dégénérée, traduisant ainsi un comportement stationnaire pour la dynamique de la population conditionnée à la non-extinction, et offrant une généralisation de la limite dite de Yaglom (correspondant au cas θ=0). Nous étudions dans un second temps le comportement de la population en cas d'une extinction très tardive, obtenu comme limite lorsque θ tends vers l'infini du processus X_t conditionné par X_{t+θ}≠0. Le processus conditionné ainsi obtenu est un objet connu dans le cadre monotype (parfois dénommé Q-processus), et a également été étudié lorsque le processus X_t est un processus de diffusion de Feller multitype. Nous examinons le cas encore non considéré où X_t est un BGWc multitype, prouvons l'existence du Q-processus associé, examinons ses propriétés, notamment asymptotiques, et en proposons plusieurs interprétations. Enfin, nous nous intéressons aux échanges de limites en t et en θ, ainsi qu'à la commutativité encore non étudiée de ces limites vis-à-vis de la relation de type grande densité reliant processus BGWc et processus de Feller. Nous prouvons ainsi une liste exhaustive et originale de tous les échanges de limites possibles (limite en temps t, retard de l'extinction θ, limite de diffusion). La deuxième partie de ce travail est consacrée à l'analyse des risques liés à l'extinction d'une population et à son extinction tardive. Nous considérons un certain modèle de population branchante (apparaissant notamment dans un contexte épidémiologique) pour lequel un paramètre lié aux premiers moments de la loi de reproduction est inconnu, et construisons plusieurs estimateurs adaptés à différentes phases de l'évolution de la population (phase de croissance, phase de décroissance, phase de décroissance lorsque l'extinction est supposée tardive), prouvant de plus leurs propriétés asymptotiques (consistance, normalité). En particulier, nous construisons un estimateur des moindres carrés adapté au Q-processus, permettant ainsi une prédiction de l'évolution de la population dans le meilleur ou le pire des cas (selon que la population est menacée ou au contraire invasive), à savoir celui d'une extinction tardive. Ces outils nous permettent d'étudier la phase d'extinction de l'épidémie d'Encéphalopathie Spongiforme Bovine en Grande-Bretagne, pour laquelle nous estimons le paramètre d'infection correspondant à une possible source d'infection horizontale persistant après la suppression en 1988 de la voie principale d'infection (farines animales). Cela nous permet de prédire l'évolution de la propagation de la maladie, notamment l'année d'extinction, le nombre de cas à venir et le nombre d'animaux infectés, et en particulier de produire une analyse très fine de l'évolution de l'épidémie dans le cas peu probable d'une extinction très tardive.

In this work, we are interested in Growth of Galton-Watson trees under two different models: (1) Galton-Watson (GW) forests with lifetimes and/or immigrants, and (2) Galton-Watson forests with mutation, which we call Galton-Watson-Clone-Mutant forests, or GWCMforests. Under each model, we study certain consistent families (Fλ)λ≥0 of GW/GWCM forests and associated decompositions that include backbone decomposition as studied by many authors. Specifically, consistency here refers to the property that for each μ ≤ λ, the forest Fμ has the same distribution as the subforest of Fλ spanned by the blue leaves in a Bernoulli leaf colouring, where each leaf of Fλ is coloured in blue independently with probability μ/λ. In the first model, the case of exponentially distributed lifetimes and no immigration was studied by Duquesne and Winkel and related to the genealogy of Markovian continuous-state branching processes (CSBP). We characterise here such families in the framework of arbitrary lifetime distributions and immigration according to a renewal process, and show convergence to Sagitov’s (non-Markovian) generalisation of continuous-state branching renewal processes, and related processes with immigration. In the second model, we characterise such families in terms of certain bivariate CSBP with branching mechanisms studied previously by Watanabe and show associated convergence results. This is related to, but more general than Bertoin’s study of GWCM trees, and also ties in with work by Abraham and Delmas, who study directly some of the limiting processes.