Distribution of the height of a random tree with labeled edges

B. A. Sevast'yanov

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

Résumé

A random genealogical tree of n generations of a supercritical Galton-Watson branching process with generating function $h(s)$, $h(0)=0$, $h'(1)=A>1$, is considered; the $t$th level of vertices of the tree corresponds to the particles of the $t$th generation. Edges of the tree are labelled by independent and identically distributed random variables $\{\xi_\alpha\}$ with distribution function $G(x)=\mathbf{P}\{\xi_\alpha\le x\}$. The weight of the path from the root to a vertex of the $n$th level is defined as the sum of labels $\xi_\alpha$ of all the edges of this path. The height $\eta_n$ of the tree is the maximum weight over all such paths. It is shown that the distribution function $F_n(x)=\mathbf{P}\{\eta_n$ satisfies the recursion relation $$ F_{n+1}(x) = h({F_n*G(x)}),\qquad n\ge1,\quad F_1(x)=h(G(x)). $$ It is proved that if $G(x)$ is a bounded lattice distribution with $G(x_0)=1$ and $q=G(x_0)-G(x_0-1)>0$, $Aq>1$ then $\lim_{n\to\infty} \mathbf{P}\{nx_0-\eta_n=kl\}$ exists for any $k=0,1,2,\ldots$, where $l$ is the lattice span.

Détail

Keywords: Galton–Watson branching process, random tree with labeled edges, the height of a random tree, supercritical process, Bellman–Harris branching process, branching random walk.