|
Teoriya Veroyatnostei i ee Primeneniya, 1993, Volume 38, Issue 2, Pages 453–457
(Mi tvp3956)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Short Communications
Distribution of the height of a random tree with labeled edges
B. A. Sevast'yanov Steklov Mathematical Institute, Russian Academy of Sciences
Abstract:
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<x\}$ 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.
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.
Received: 20.05.1992
Citation:
B. A. Sevast'yanov, “Distribution of the height of a random tree with labeled edges”, Teor. Veroyatnost. i Primenen., 38:2 (1993), 453–457; Theory Probab. Appl., 38:2 (1993), 379–382
Linking options:
https://www.mathnet.ru/eng/tvp3956 https://www.mathnet.ru/eng/tvp/v38/i2/p453
|
Statistics & downloads: |
Abstract page: | 196 | Full-text PDF : | 51 | First page: | 10 |
|