Nous supposons que pour ces arbres il existe un opérateur (*) qui possède un élément absorbant P, dans le sens où tout arbre de racine (*) et dont l'un des fils est P est équivalent sémantiquement à P (par exemple, 0 est absorbant pour x, (a+b)* est absorbant pour + sur les langages à deux lettres, etc). Dans la première partie, nous étudions des arbres dont les nœuds sont étiquetés par des opérateurs, qui représentent des expressions avec une sémantique, comme les expressions régulières qui représentent des langages, ou les expressions logiques qui représentent des fonctions booléennes. Roughly speaking, our approach succeed if $r<\mathfrak$ is a divergence measuring the dissimilarity between $\mu$ and $\nu$.Ĭette thèse s'articule autour de deux parties indépendantes, qui s'intéressent à des objets différents, mais qui se rassemblent dans la méthodologie appliquée pour les étudier : nous nous appuyons essentiellement dans les deux parties sur des outils mathématiques spécialisés dans l'étude des systèmes de séries génératrices. Indeed, if the growth-rate is too large, large deviations events are likely to be observed in the sampling of the normal individuals preventing us to distinguish them from special ones. In this work, we show that even in such a very structured two-types population, our ability to distinguish the two types and estimate $\mu$ and $\nu$ is constrained by a trade off between the growth-rate of the population and the similarity of $\mu$ and $\nu$. This kind of tree is characterized by a spine of special individuals whose BD $\nu$ is different from the other individuals in the tree (called normal whose BD is denoted $\mu$). More precisely, we consider a two-type MGW called spinal-structured trees. We investigate some aspects of the problem of the estimation of birth distributions (BD) in multi-type Galton-Watson (MGW) trees with unobserved types. This corresponds to a structural parameter of the tree that we call the peel number and we also consider a similar parameter which we call the leaf height
We also analyse the running time of a commonly-used algorithm that computes the independent set. We give a formula for the independence number of a conditional Galton-Watson tree in terms of the offspring generating function of the distribution. Finally, we study several parameters of a conditional Galton-Watson tree that are related to independent sets. The problem of computing the maximum of the multiplicities of the nodes turns out to be rather difficult, so we introduce a finer partition of the nodes and give an asymptotic calculation of the size of the largest equivalence class under this stricter definition of multiplicity.
#Galton watson tree free#
In the root estimation problem above, it was convenient to define the multiplicity of a node to be the size of the node's orbit under (a certain subgroup of) the free tree's automorphism group. Next we study the sizes of orbits of nodes in a conditional Galton-Watson tree under graph automorphism. We give such an estimator and determine its probability of being correct. The root estimation problem asks for a maximum-likelihood estimator for the root of the original tree. Next, the parent-child directions of the edges are erased, so that only the simple-graph structure of the tree remains.
A Galton-Watson tree is generated with a known offspring distribution, conditioned on its having n nodes. First we tackle the root estimation problem in Galton-Watson trees, whose setup is as follows. Each of these results involves, in some way, the structure or shape of the underlying tree. To answer the question you need to put some restrictions on the moments of $\xi_i^n$ or equivalently the tails of its mass function.This thesis presents three results concerning conditional Galton-Watson trees.
0 kommentar(er)
