The distribution of the distance to the root of the minimal subtree containing all the vertices of a given height

V. A. Vatutin

Teoriâ veroâtnostej i ee primeneniâ, Tome 38 (1993) no. 2, pp. 273-287

Résumé

Let $h(s)$ be the generating function of the number of direct descendants in a Galton–Watson branching process, $\mu (t)$ the number of particles in the process at time $t$, $\nu$ the total number of particles bornn in the process during its evolution, and let $\tau (t)$ be the distance to the nearest mutual ancestor of all the particles existing at time $t$. Assuming that $$ h'(1)=1,\qquad 0<B=h''(1)<\infty, $$ and the parameters $N$, $t\to\infty$ in such a way that $t({B/N})^{1/2}\to\beta\in(0,\infty)$, we find the limit $$ \lim\mathbf{P}\{t^{-1}\tau(t)\le a\mid\mu(t)>0,\nu=N\}=I_\beta(a),\qquad 0<a<1. $$ The result obtained is used to find the limiting (as $N\to\infty$) distribution of the distance to the root of the minimal subtree containing all the vertices of a given height in the case where the tree is chosen at random and equiprobably either from the set of all planted plane trees with $N$ nonrooted vertices or from the set of all labelled rooted trees with $N$ vertices.

Détail

Keywords: Galton–Watson branching process, limit theorems, distribution distance to the nearest mutual ancestor, planted plane trees, labelled trees.